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: Thu, 18 Jan 2024 17:56:07 -0300 Organization: A noiseless patient Spider Lines: 209 Message-ID: <878r4mfjiw.fsf@example.com> References: <877cke4ny3.fsf@example.com> <87y1cujtsk.fsf@brilhante.top> <87ttni48z9.fsf@example.com> <87r0im428v.fsf@brilhante.top> <87edem3yds.fsf@example.com> <87edel4avz.fsf@brilhante.top> <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> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: dont-email.me; posting-host="8fe7ef72b8e463c996dd3ca4bf97eb74"; logging-data="2898193"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18Nzj0itgnM7Sqnv+9FaKfyoUiHtw9I4Pg=" Cancel-Lock: sha1:knfdDECpSgSIkbA+D07EdNryczY= sha1:nvVZEOuSz4YCBavVXHAhhHXsqao= Xref: csiph.com pt.comp.programacao:179 Daniel Cerqueira writes: > Patricia Ferreira writes: > >> Daniel Cerqueira 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 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.