Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pt.comp.programacao > #224
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Newsgroups | pt.comp.programacao |
| Subject | Re: Lisp, um mapa de trajeto |
| Date | 2024-02-06 11:11 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87wmrh4zlf.fsf@brilhante.top> (permalink) |
| References | (16 earlier) <87v87oi0pw.fsf@brilhante.top> <87wms4f4m3.fsf@example.com> <87il3kyn4g.fsf@brilhante.top> <8734u97q1z.fsf@brilhante.top> <8734u9buk3.fsf@example.com> |
Patricia Ferreira <pferreira@example.com> writes:
[...]
>>>>>> (*) Novo problema
>>>>>>
>>>>>> Encontremos todos os caminhos. Parece moleza. Experimenta.
Aqui está a minha solução a este problema. Com uma nova abordagem.
Esta solução é mais intensa na memória, mas estou a falhar em encontrar
uma solução mais suave para a memória do computador.
Aqui as funções "no", "vizinhos", "caminho" e "caminho/lista" são as
funções que já descobrimos nos exercícios anteriores.
A técnica aqui reside em criar uma lista de grafos, em que tem todos os
grafos na qual falta apenas um nó dos nós iniciais. Esta é a parte
intensiva para a memória.
Depois calculo todos os caminhos usando este /multiverso de grafos/ e
vou armazenando os caminhos únicos numa váriavel (local). Para depois
retornar esta variável.
Aqui a função que retorna todos os caminhos é "caminhos".
Patrícia, se descobrires outra abordagem que retorne todos os caminhos,
quero ouvir sobre ela. Uma maneira simples de testar, se retorna todos
os caminhos, é calcular os caminhos desde B até D, tendo de retornar 3
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* ((lista-de-vizinhos (vizinhos src graph))
(caminho-de-lista-de-vizinhos (caminho/lista lista-de-vizinhos 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-no (number graph)
"Remove um nó de GRAPH por posição NUMBER (primeira posição é o zero)"
(remove-if #'(lambda (el) (eq el (nth number graph))) graph))
(defun grafo-multiverso (graph &optional number)
"Retorna uma lista com todas as variações de GRAPH em que falta, em cada grafo, um nó."
(cond
((null number) (cons graph (grafo-multiverso graph 0)))
((eq number (length graph)) nil)
(t (cons (remover-no number graph) (grafo-multiverso graph (1+ number))))))
(defun caminho-map (src dst graph-multiverse result)
"Retorna todos os caminhos (RESULT) únicos desde SRC até DST, da lista de grafos GRAPH-MULTIVERSE. Retorna RESULT caso não haja qualquer caminho."
(let ((caminho (caminho src dst (car graph-multiverse))))
(cond
((null graph-multiverse) result)
((or
(null caminho)
(consp (member caminho result :test #'equal)))
(caminho-map src dst (cdr graph-multiverse) result))
(t (caminho-map src dst (cdr graph-multiverse) (push caminho result))))))
(defun caminhos (src dst graph)
"Retorna todos os caminhos de GRAPH, desde SRC até DST. Retorna NIL se não há qualquer caminho."
(caminho-map src dst (grafo-multiverso graph) nil))
Back to pt.comp.programacao | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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