Path: csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Patricia Ferreira Newsgroups: pt.comp.programacao Subject: Re: Lisp, um mapa de trajeto Date: Tue, 06 Feb 2024 18:13:14 -0300 Organization: A noiseless patient Spider Lines: 116 Message-ID: <8734u5l2j9.fsf@example.com> References: <87o7dn3636.fsf@brilhante.top> <874jff1dbm.fsf@yaxenu.org> <87a5p638mt.fsf@brilhante.top> <87bk9mzg3b.fsf@example.com> <87bk9l9mki.fsf@brilhante.top> <87r0ign4zd.fsf@yaxenu.org> <87h6jcj6uh.fsf@brilhante.top> <87wms6khgu.fsf@yaxenu.org> <87cytyjzhb.fsf@brilhante.top> <87v87qike6.fsf@example.com> <874jfajvgc.fsf@brilhante.top> <878r4mfjiw.fsf@example.com> <87v87oi0pw.fsf@brilhante.top> <87wms4f4m3.fsf@example.com> <87il3kyn4g.fsf@brilhante.top> <8734u97q1z.fsf@brilhante.top> <8734u9buk3.fsf@example.com> <875xz26hny.fsf@brilhante.top> <87zfwelgwi.fsf@example.com> <871q9p6evs.fsf@brilhante.top> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: dont-email.me; posting-host="2a610029aef620f662cfef3aded6a9f0"; logging-data="1121612"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX183XHQSDka2W4T8Z+32khyeJmNoe2YX10s=" Cancel-Lock: sha1:j19gtuH0taDve4ZzsWa88pHBvuQ= sha1:DidIRj1ixtzO8BHglQa2KxaFhlY= Xref: csiph.com pt.comp.programacao:225 Daniel Cerqueira writes: > Patricia Ferreira writes: > >> Daniel Cerqueira writes: >> >>> Patricia Ferreira writes: >>> >>>> >>>> [...] >>>> >>>>>>>>> (*) Novo problema >>>>>>>>> >>>>>>>>> Encontremos todos os caminhos. Parece moleza. Experimenta. >>> >>> Descobri a solução. Em Common Lisp (não em Scheme) :-P >>> >>> Vai aqui o código completo. As funções "no", "vizinhos", "caminho" e >>> "caminho/lista", são as que tinhamos descoberto anteriormente. >>> >>> Esta solução (tal como a tua), vai removendo elementos de GRAPH para >>> encontrar caminhos alternativos. O truque desta solução é que ao >>> remover, remove de GRAPH um elemento igual ao penúltimo elemento de um >>> dado caminho LIST. Assim mantem-se o DST de um caminho em GRAPH. >>> >>> Se, após a remoção, o caminho alternativo der NIL, não existe mais >>> caminhos possíveis no GRAPH, desde SRC até DST. >>> >>> Este código está completo. Podes copiar, colar, avaliar/compilar, e >>> correr. A função que descobre todos os caminho é "caminhos". >>> >>> >>> (defparameter graph >>> '((A (B E)) >>> (B (E F)) >>> (C (D)) >>> (D ()) >>> (E (C F)) >>> (F (D G)) >>> (G ()))) >>> >>> (defun no (node graph) >>> "Retorna um nó NODE de um grafo GRAPH." >>> (assoc node graph)) >>> >>> (defun vizinhos (node graph) >>> "Retorna os vizinhos de NODE de um grafo GRAPH." >>> (cadr (no node graph))) >>> >>> (defun caminho (src dst graph) >>> "Retorna um caminho desde SRC até DST de um GRAPH." >>> (cond >>> ((eq src dst) (cons dst nil)) >>> (t >>> (let ((caminho-de-lista-de-vizinhos (caminho/lista (vizinhos src graph) dst graph))) >>> (cond >>> ((null caminho-de-lista-de-vizinhos) nil) ; se chegou a um beco sem saída, isto é, um vizinho nil, retorna nil >>> (t (cons src caminho-de-lista-de-vizinhos))))))) >>> >>> (defun caminho/lista (list dst graph) >>> "Retorna um caminho desde uma lista LIST até DST de um GRAPH. Retorna NIL caso não haja qualquer caminho." >>> (cond >>> ((null list) nil) ; fim da list >>> (t >>> (let ((caminho-de-atomo (caminho (car list) dst graph))) >>> (cond >>> ((consp caminho-de-atomo) caminho-de-atomo) ; caminho de o primeiro vizinho (depende de função anterior) >>> (t (caminho/lista (cdr list) dst graph))))))) ; ver restante da list >>> >>> (defun remover-penultimo (list graph) >>> "Remove de GRAPH um nó igual ao penultimo átomo de LIST." >>> (remove-if #'(lambda (el) (eq (nth (- (length list) 2) list) (car el))) graph)) >>> >>> (defun cortar-grafo (graph previous-paths) >>> "Corta no grafo GRAPH o(s) nó(s) igual(ais) ao penultimo átomo de cada caminho de PREVIOUS-PATHS." >>> (cond >>> ((null previous-paths) graph) >>> (t (cortar-grafo >>> (remover-penultimo (car previous-paths) graph) >>> (cdr previous-paths))))) >>> >>> (defun caminhos-alternativos (src dst graph previous-paths) >>> "Retorna um caminho desde SRC até DST de um GRAPH, que seja diferente dos caminhos de PREVIOUS-PATHS." >>> (let ((novo-caminho (caminho src dst (cortar-grafo graph previous-paths)))) >>> (cond >>> ((null novo-caminho) previous-paths) >>> (t (caminhos-alternativos src dst graph (push novo-caminho previous-paths)))))) >> >> Não compreendo a necessidade de /push/ aqui. > > Por o argumento de caminhos-alternativos ser uma lista de lista, o push > é uma maneira de adicionar uma lista a esta lista de listas. Você não pode usar cons pra isso? >>> (defun caminhos (src dst graph) >>> "Retorna todos os caminhos desde SRC até DST de um GRAPH. Retorna NIL caso não haja caminho." >>> (let ((um-caminho (caminho src dst graph))) >>> (cond >>> ((null um-caminho) nil) >>> ((eq src dst) (list (list src))) >>> (t (caminhos-alternativos src dst graph (list um-caminho)))))) >> >> A expressão está bem melhor. É engraçado como código tem uma certa >> forma. Um especialista em xadrez olha pra um tabuleiro e rapidamente >> nota se alguma coisa não faz sentido. > > Tenho más notícias.... esta solução continua a não retornar todos os > caminhos. Por exemplo: (caminhos 'b 'd graph) retorna apenas 2 caminhos, > quando deveria retornar 3 caminhos. > > Após ter enviado este artigo, comecei a trabalhar numa solução que > solucionasse isto de maneira definitiva. Já tenho a solução, que vou > postar num artigo próprio. Okay!