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 20:48:34 -0300 Organization: A noiseless patient Spider Lines: 167 Message-ID: <871q9thzxp.fsf@example.com> References: <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> <87y1c1qvu3.fsf@example.com> <87ttmp5sit.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="b81c3683401a7274d948adffbc0003e3"; logging-data="3511776"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18ifzyWrV8I3b7YV1kNOhtEpqTz8bvS/Zc=" Cancel-Lock: sha1:NvQihy+gpR2wN1NbDVnM84LGl9Y= sha1:L+lnD3ehDKlMmZ7ny50M+n2uYSw= Xref: csiph.com pt.comp.programacao:218 Daniel Cerqueira writes: > Patricia Ferreira writes: > >> 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. > > exclude-paths parece-me um bom nome. > > O push é porque a variável exclude-lists é do tipo lista de listas, e > faço um push de um path, para assim saber que esse path já foi obtido (e > tentar outro). > > Ainda preciso de arranjar a minha solução, mas é uma maneira mais > eficiente que calcular todos os paths com remoção de vizinhos. > > Não é óbvio de entender a minha solução; por isso também irei tentar > fazer com que seja mais fácil a sua leitura. Combinado. Então vou esperar. E a minha ``mais ou menos óbvia''? Deu pra entender? Eu teria pensado que haveria uma solução mais fácil de fazer, dado que conseguimos escrever find-path. Mas você viu o trabalho que nós dois tivemos em ambos os casos? Por isso eu disse---parece moleza. Só faltou dizer---mas não é (pra mim, pelo menos). Mas não queria te influenciar. O fato é---o problema não é trivial (pra mim). O que está me faltando?