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: Sat, 03 Feb 2024 14:52:20 -0300 Organization: A noiseless patient Spider Lines: 143 Message-ID: <87y1c1qvu3.fsf@example.com> References: <87edem3yds.fsf@example.com> <87edel4avz.fsf@brilhante.top> <874jfhvwb9.fsf@example.com> <87a5p83yxq.fsf@brilhante.top> <87mst8rpjj.fsf@example.com> <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> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: dont-email.me; posting-host="aad133e4c5be3d1a82e952397156fd9c"; logging-data="3398103"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/bQr0Av5iNJjOXBOgbjOuK5dIycCOhB1w=" Cancel-Lock: sha1:mDrMrqEsIT/WYO/L8JSmXXdUh+Q= sha1:m1jl8xLYm+gQvZGtX2+tDi+oUTs= Xref: csiph.com pt.comp.programacao:216 Daniel Cerqueira writes: > Patricia Ferreira writes: > >> Daniel Cerqueira writes: >> >>> Patricia Ferreira writes: >>> >>>> Daniel Cerqueira writes: >>>> >>>>> Como resolverias este exercício? :-) >>>> >>>> (defun find-path (src dst graph) >>>> (cond >>>> ((eq src dst) (cons src nil)) >>>> (t >>>> (let ((subsolution (find-path/list (neighbors src graph) dst graph))) >>>> (if subsolution >>>> (cons src subsolution) >>>> nil))))) >>>> >>>> (defun find-path/list (ns end graph) >>>> (cond >>>> ((null ns) nil) >>>> (t (let ((subsolution (find-path (car ns) end graph))) >>>> (if subsolution >>>> subsolution >>>> (find-path/list (cdr ns) end graph)))))) >>>> >>>> CL-USER> (find-path 'A 'G sample-graph) >>>> (A B E F G) >>>> CL-USER> (find-path 'C 'D sample-graph) >>>> (C D) >>>> CL-USER> (find-path 'C 'A sample-graph) >>>> NIL >>>> >>>> Solucionado. >>> >>> Estou (e passei estes últimos dias) a olhar espantado quanto ao >>> maravilhoso engenho deste algoritmo.... >> >> Somos dois. Mas me parece mais adequado observá-lo nesta forma: >> >> (defun find-path/list (ns end graph) >> (cond >> ((null ns) nil) >> (t (or (find-path (car ns) end graph) >> (find-path/list (cdr ns) end graph))))) >> >> (defun find-path (src dst graph) >> (cond >> ((eq src dst) (cons src nil)) >> (t (and (find-path/list (neighbors src graph) dst graph) >> (cons src (find-path/list (neighbors src graph) dst graph)))))) >> >>>> (*) Novo problema >>>> >>>> Encontremos todos os caminhos. Parece moleza. Experimenta. >>> >>> Vou demorar algum tempo a resolver este último problema. Primeiro quero >>> entender melhor a solução que des-te. >>> >>> E vou resolver sim esse novo problema ;-) >> >> Tem uma solução que julgo mais ou menos óbvia, mas me pergunto se é uma >> solução natural aí no caso. Vou deixar você trabalhar por aí antes de >> apresentar. Torço pra que você encontre a solução que eu acho que >> deveria existir e não consigo encontrar. > > Bem, acho que encontrei a solução adquada. Alguns dos meus algoritmos > fazem duas vezes a mesma operação, por isso só falta optimiza-los para > nestas vezes, guardar o valor numa variável. > > Aqui vai a minha resposta: > > (defun cdrs (lists) > (mapcar #'cdr lists)) > > (defun cars (lists) > (mapcar #'car lists)) > > (defun diff (path-a path-b) > (cond > ((null (member (car path-a) path-b)) path-a) > (t (diff (cdr path-a) path-b)))) > > (defun neighbors-exclude (exclude-lists list) > (diff list (cars exclude-lists))) > > (defun find-path2 (src dst exclude-lists graph) > (cond > ((eq src dst) (cons dst nil)) > ((null > (find-path/list2 > (neighbors-exclude (cdrs exclude-lists) (neighbors src graph)) > dst (cdrs exclude-lists) graph)) > nil) > (t (cons > src > (find-path/list2 > (neighbors-exclude (cdrs exclude-lists) (neighbors src graph)) > dst (cdrs exclude-lists) graph))))) > > (defun find-path/list2 (ns end exclude-lists graph) > (cond > ((null ns) nil) > ((null (find-path2 (car ns) end exclude-lists graph)) > (find-path/list2 (cdr ns) end exclude-lists graph)) > (t (find-path2 (car ns) end exclude-lists graph)))) > > (defun paths (src dst graph &optional exclude-lists) > (cond > ((null (find-path2 src dst exclude-lists graph)) nil) > (t (cons > (find-path2 src dst exclude-lists graph) > (paths src dst graph > (push (find-path2 src dst exclude-lists graph) exclude-lists)))))) Por que push aqui quando você já está usando cons quando quer construir uma lista? Será que você tá usando exclude-lists de forma global? Não faz sentido, já que você passando ela como argumento pra /paths/. > A função a ser executada é a função ``paths''. Consegues verificar-me se > funciona corretamente? Aparentemente sim, mas você parece entrar num laço infinito com (paths 'a 'a sample-graph). Como funciona? Não é óbvia a estratégia. Parece que find-path2 seria a solução pra um qualquer caminho---seria a solução anterior. Mas, não---você teve que alterá-la substancialmente pra poder obter a nova. Tenho dificuldade de entendê-la. Não só estamos preocupados com exclude-lists, mas também em excluir vizinhos. Essa exclude-lists talvez fosse melhor chamada de exclude-paths. A solução que julguei ``mais ou menos óbvia'' foi a que sugeri em mensagem anterior hoje---computa-se um caminho a partir do primeiro vizinho; remove-se o vizinho do grafo e computa-se de novo. Repita até não haver mais caminho---sinal de que não há mais vizinhos que nos leve ao destino.