Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pt.comp.programacao > #179
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Newsgroups | pt.comp.programacao |
| Subject | Re: Lisp, um mapa de trajeto |
| Date | 2024-01-18 17:56 -0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <878r4mfjiw.fsf@example.com> (permalink) |
| References | (16 earlier) <87h6jcj6uh.fsf@brilhante.top> <87wms6khgu.fsf@yaxenu.org> <87cytyjzhb.fsf@brilhante.top> <87v87qike6.fsf@example.com> <874jfajvgc.fsf@brilhante.top> |
Daniel Cerqueira <dan.list@brilhante.top> writes:
> Patricia Ferreira <pferreira@example.com> writes:
>
>> Daniel Cerqueira <dan.list@brilhante.top> writes:
>>
>>> De qualquer das maneiras, o este meu código não está a funcionar
>>> direito, em alguns casos.
>>
>> Pois é. Sua estratégia é realmente expressa por get-path-list. O
>> procedimento find-path é apenas um procedimento de apresentação --- se
>> get-path-list não encontrar o caminho, diga nil.
>>
>> O que há de errado com sua estratégia? Façamos a pergunta --- por que
>> get-path-list não encontra o caminho de F a G? São vizinhos; deveria
>> ser trivial. Mas G não é o /primeiro/ vizinho de F. O primeiro vizinho
>> de F é D. Como não há caminho entre D e G, seu procedimento pensa que
>> não há caminho. Em outras palavras, seu procedimento só faz uma
>> tentativa de várias possíveis --- se não houver caminho na primeira, seu
>> procedimento acha que não há caminho qualquer.
>
> Pois... eu sei que só está a resolver o primeiro caminho. Quando tento
> fazer com que resolva todos os caminhos, o meu código fica muito
> complicado; e ainda não consegui fazê-lo. Estava apenas a tentar usar
> cons e isso estava-me a dificultar um pouco.
>
> Acho que a essência deste exercício está-me a passar ao lado.
>
> Como resolverias este exercício? :-)
Eis uma tentativa pela receita HtDP. Um Vértice é um Símbolo. Um
Vizinhos é uma lista de Símbolos. Um Grafo é um de
- NIL
- (cons Vértice Vizinhos)
Por exemplo,
NIL ou (list B E))
são Vizinhos. Já A, B, C, ... são Vértices. E, assim,
((A (B E))
(B (E F)))
é um grafo. Precisamos de um procedimento neighbors que extrai os
Vizinhos de um vértice. Como é trivial, usemos /assoc/:
(defun neighbors (v g) (assoc v g))
Como já temos Grafo e Vértice, já podemos escrever a assinatura de
find-path. Ela consome dois vértices e um grafo e produz uma lista de
Vértice --- que é o caminho em si.
Vértice Vértice Grafo --> List-of Vértices
Usando sample-graph, temos os exemplos:
(find-path 'C 'D sample-graph) --> (C D)
(find-path 'E 'D sample-graph) --> (E C D) ou (E F D)
(find-path 'C 'G sample-graph) --> sem-caminho
O caso E--D já apresenta essa ambiguidade: tem dois caminhos possíveis.
O caso C--G não tem nenhum. É preciso decidir o que fazer em cada caso.
Dizer NIL quando sem-caminho vai ajudar a escrever um código mais curto
em Common Lisp. Quanto à ambiguidade, escolhamos por ora o primeiro
caminho que for encontrado.
O procedimento find-path tem que retornar uma List-of Vértices, então
não estamos incorretos se retornarmos NIL num esboço
(defun find-path (src dst g)
NIL)
A receita pra esse tipo de problema é considerar algumas possibilidades:
o caso base, o repartir do problema em um subproblema e o passo de
combinação da subsolução pra obter o problema original.
Quando dois Vértices são vizinhos, o caminho é trivial: os dois vértices
numa lista. Mas dá pra tornar esse problema ainda mais trivial que é
quando os dois Vértices são o mesmo Vértice, que é o que você fez em
get-path-list. Usemos isso também: a resposta aí é (cond end nil).
Se os argumentos são diferentes, precisamos considerar cada vizinho.
Considerar cada vizinho é um problema novo, mas /cada um/ desses
problemas é da mesma forma que o problema original. Se os vizinhos de
/src/ são v1, v2, então os subproblemas são
(find-path v1 end g)
(find-path v2 end g)
Agora, invocar a resolução desses subproblemas é um problema /novo/
porque envolve uma List-of Vértices. Esse /tipo/ diferente nos leva a
escrever um novo procedimento --- porque as assinaturas não casam. Que
tipo de resposta esse novo procedimento produz? Uma List-of Vértices,
logo NIL é um esboço de resposta.
;; Vizinhos Vértice Grafo --> List-of Vértice
;; interpretação: o primeiro caminho encontrado entre um Vértice de
;; origem (em Vizinhos) até o Vértice de destino no Grafo.
(defun find-path/list (ns dst g)
NIL)
Agora já podemos escrever find-path, assumindo que find-path/list está
pronta. Se houver um caminho de algum vizinho até DST, então a resposta
é uma lista não-vazia. Se não houver, é NIL. Assim, se find-path/list
retorna NIL, então não há caminho algum. Se ela retorna List-of
Vértice, então a resposta do problema original é
(cons SRC <RETORNO DE FIND-PATH/LIST).
(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)))))
Recapitule. Se SRC e DST são idênticos, caso base. Se forem
diferentes, então precisamos ver se existe caminho entre os vizinhos de
SRC até DST. Isso quem descobre é find-path/list. Se find-path/list
retornar uma coisa que não é NIL, então a solução do problema original é
simplesmente SRC na cabeça de SUBSOLUTION. Se não houver, então
respondemos NIL também.
Pra isso funcionar, só precisamos de find-path/list. É hora de recordar
o projeto que fizemos pra find-path/list, o que repetimos aqui pra não
ter que recuperar texto acima já passado.
;; Vizinhos Vértice Grafo --> List-of Vértice
;; interpretação: o primeiro caminho encontrado entre um Vértice de
;; origem (em Vizinhos) até o Vértice de destino no Grafo.
(defun find-path/list (ns dst g)
NIL)
Agora que find-path está escrita, fica muito mais fácil pensar em
find-path/list porque o que find-path/list faz é usar find-path até
encontrar um caminho, ou seja, find-path/list é trivial: basta percorrer
a lista de Vizinhos um a um. O caso base de find-path/list é quando não
há mais Vizinhos a considerar.
(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.
(*) Uma expressão mais típica
Usamos /if/ no código acima pra casar com a nossa redação em português,
mas não é a forma idiomática de escrever. Eis uma reescrita.
(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))))))
É a solução.
(*) Epílogo
Esse é o processo ensinado pelo HtDP. Mas não é fácil usar isso. Não
diria que realmente compreenda esse processo. Os autores anunciam
também --- especialmente nesses casos de recursão ``generativa'', que é
como eles chama esse tipo, o código muitas vezes exige um certo insight.
Em retrospectiva, posso fazer as seguintes observações. Observe que pra
escrever find-path/list, precisamos de find-path. Pra escrever
find-path, precisamos de find-path/list. Em outras palavras, temos uma
recursão mútua aí. Isso é comum de ocorrer em árvores. Por exemplo,
como se faz pra descer um sistema de arquivos? Dessa forma. Esse grafo
não é nada senão uma árvore. Ele não possui ciclos. Então é preciso
trabalhar de forma mais sistemática --- observando essas coisas. Como
diz Frederick P. Brooks, é preciso prestar atenção à estrutura de dados
primeiro. Os algoritmos em si serão óbvios depois. Essa noção está
explicitamente explorada pelo HtDP.
``Representation Is the Essence of Programming. Much more often,
strategic breakthrough will come from redoing the representation of
the data or tables. This is where the heart of a program lies. Show
me your flowcharts and conceal your tables, and I shall continue to be
mystified. Show me your tables, and I won’t usually need your
flowcharts; they’ll be obvious.'' -- ``The Mythical Man-Month'',
expanded anniversary edition (2nd edition), 1995, Addison-Wesley, ISBN
0-201-83595-9. Página 102.
(*) Novo problema
Encontremos todos os caminhos. Parece moleza. Experimenta.
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