Re: Lisp, um mapa de trajeto

From	Daniel Cerqueira <dan.list@brilhante.top>
Newsgroups	pt.comp.programacao
Subject	Re: Lisp, um mapa de trajeto
Date	2024-02-04 11:42 +0000
Organization	A noiseless patient Spider
Message-ID	<87il345ubu.fsf@brilhante.top> (permalink)
References	(16 earlier) <87wms4f4m3.fsf@example.com> <87il3kyn4g.fsf@brilhante.top> <87y1c1qvu3.fsf@example.com> <87ttmp5sit.fsf@brilhante.top> <871q9thzxp.fsf@example.com>

Show all headers | View raw

Patricia Ferreira <pferreira@example.com> writes:

> Daniel Cerqueira <dan.list@brilhante.top> writes:
>
>> Patricia Ferreira <pferreira@example.com> writes:
>>
>>> Daniel Cerqueira <dan.list@brilhante.top> writes:
>>>
>>>> Patricia Ferreira <pferreira@example.com> writes:
>>>>
>>>>> Daniel Cerqueira <dan.list@brilhante.top> writes:
>>>>>
>>>>>> Patricia Ferreira <pferreira@example.com> writes:
>>>>>>
>>>>>>> Daniel Cerqueira <dan.list@brilhante.top> 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?

Sim, não é moleza. Ainda não vi a fundo a tua solução, porque ainda
estou a tentar fazer a minha solução.

O que está faltando? Não sei. Mas só há duas soluções: ou se vai
removendo elementos do sample-graph (a tua solução), ou se cria e usa
uma lista de paths a serem evitados quando se está a calcular um
caminho, para se poder encontrar outros paths diferentes (a minha
solução).

Eu não queria fazer isto, mas vou ter de fazê-lo. Tenho de alterar o
código para que não consuma o sample-graph, evitando usar o cdr e
passando a usar o nth+um-integer-de-posição. Assim dá para percorrer o
grafo, mantendo este sempre no estado inicial, para assim poder comparar
o caminho que se está a obter, com os caminhos já obtidos da lista de
exclusão. É necessário o nth porque tenho de comparar o caminho desde o
ínicio, não um cdr (ou cddr, cdddr, etc.) desse caminho.

Isto é necessário na minha solução.

Back to pt.comp.programacao | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Ada-Europe conference - 31 Jan Journal Track Extended Deadline dirk@orka.cs.kuleuven.be. (Dirk Craeynest) - 2024-01-08 10:44 +0000
  Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Patricia Ferreira <pferreira@example.com> - 2024-01-08 13:05 -0300
    Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline dirk@orka.cs.kuleuven.be. (Dirk Craeynest) - 2024-01-09 09:53 +0000
      Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Patricia Ferreira <pferreira@example.com> - 2024-01-09 09:31 -0300
        Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-10 13:18 +0000
          Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Ninguém <usenet@rasparta.org> - 2024-01-10 15:18 +0000
            fiat lux! (Was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) Patricia Ferreira <pferreira@example.com> - 2024-01-10 16:57 -0300
              Re: fiat lux! Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 16:42 +0000
                Re: fiat lux! Ninguém <usenet@rasparta.org> - 2024-01-11 22:21 +0000
                Re: fiat lux! Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 14:23 +0000
                Re: fiat lux! "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-16 14:05 +0000
                Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-16 11:45 -0300
                Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:24 -0300
                Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:02 -0300
          Lisp (was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-10 16:00 +0000
            Re: Lisp Patricia Ferreira <pferreira@example.com> - 2024-01-10 17:00 -0300
              Re: Lisp Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 16:30 +0000
          Lisp, um mapa de trajeto (Was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) Patricia Ferreira <pferreira@example.com> - 2024-01-10 16:37 -0300
            Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 17:04 +0000
              Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:37 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 18:22 +0000
                Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-12 18:51 +0000
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 22:29 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 20:27 -0300
                E-mail (was: Re: Lisp, um mapa de trajeto) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-13 10:34 +0000
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-13 13:04 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 17:02 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 12:07 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 10:39 -0300
                Re: Lisp, um mapa de trajeto "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-14 15:51 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 13:27 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 22:21 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 00:24 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-15 15:23 +0000
                Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 10:33 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 17:01 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 22:26 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 20:50 -0300
                Re: Lisp, um mapa de trajeto "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-13 11:04 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 09:46 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-13 13:32 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 16:59 -0300
                Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 10:11 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 11:01 -0300
                Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 14:18 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 11:33 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 12:02 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 10:51 -0300
                Encriptação (was: Re: Lisp, um mapa de trajeto) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-14 15:44 +0000
                Re: Encriptação Patricia Ferreira <pferreira@example.com> - 2024-01-14 13:30 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 22:25 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 00:25 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-15 15:43 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 14:00 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-16 18:10 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-16 22:06 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-17 14:10 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 08:29 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 18:03 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 15:47 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-17 15:51 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 08:29 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 17:57 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 15:09 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 19:24 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 17:56 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-19 10:39 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-19 08:38 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-20 13:38 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-20 11:42 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-23 17:29 +0000
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 11:19 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 09:29 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 13:14 +0000
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-05 15:43 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-05 18:50 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-06 10:55 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-06 18:13 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-06 11:11 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 14:52 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 18:09 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 20:48 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-04 11:42 +0000

csiph-web