Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pt.comp.programacao > #225

Re: Lisp, um mapa de trajeto

From Patricia Ferreira <pferreira@example.com>
Newsgroups pt.comp.programacao
Subject Re: Lisp, um mapa de trajeto
Date 2024-02-06 18:13 -0300
Organization A noiseless patient Spider
Message-ID <8734u5l2j9.fsf@example.com> (permalink)
References (16 earlier) <8734u97q1z.fsf@brilhante.top> <8734u9buk3.fsf@example.com> <875xz26hny.fsf@brilhante.top> <87zfwelgwi.fsf@example.com> <871q9p6evs.fsf@brilhante.top>

Show all headers | View raw

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:
>>>
>>>>
>>>> [...]
>>>>
>>>>>>>>> (*) 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!

Back to pt.comp.programacao | Previous | Next — Previous in thread | Next 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