<div class="notebook"> <div class="nb-cell markdown" name="md1"> Vamos começar criando um grafo, baseado na rede de metrô de São Paulo (e ignorando CPTM). </div> <div class="nb-cell program" data-background="true" name="p1"> % Rede de metrô em São Paulo, apenas com interconexões entre linhas. % http://www.metro.sp.gov.br/pdf/mapa-da-rede-metro.pdf estação(tucuruvi). estação(luz). estação(sé). estação(paraíso). estação(ana_rosa). estação(santa_cruz). estação(jabaquara). estação(barra_funda). estação(república). estação(brás). estação(itaquera). estação(vila_madalena). estação(consolação). estação(chácara_klabin). estação(vila_prudente). estação(são_mateus). estação(morumbi). estação(paulista). estação(capão_redondo). estação(santo_amaro). % Linha azul caminho(tucuruvi, luz). caminho(luz, sé). caminho(sé, paraíso). caminho(paraíso, ana_rosa). caminho(ana_rosa, santa_cruz). caminho(santa_cruz, jabaquara). % Linha vermelha caminho(barra_funda, república). caminho(república, sé). caminho(sé, brás). caminho(brás, itaquera). % Linha verde caminho(vila_madalena, consolação). caminho(consolação, paraíso). % caminho(paraíso, ana_rosa) já está presente na linha azul caminho(ana_rosa, chácara_klabin). caminho(chácara_klabin, vila_prudente). % Linha amarela caminho(morumbi, paulista). caminho(paulista, república). caminho(república, luz). % Conexão a pé caminho(paulista, consolação). % Linha prata caminho(vila_prudente, são_mateus). % Linha lilás caminho(capão_redondo, santo_amaro). caminho(santo_amaro, santa_cruz). caminho(santa_cruz, chácara_klabin). </div> <div class="nb-cell markdown" name="md2"> Abaixo o código da questão original do Stack Overflow, que não executa uma busca em largura, mas sim em profundidade. </div> <div class="nb-cell program" data-singleline="true" name="p2"> /* Chegar de A a Z, retornando caminho percorrido P, comecando de um caminho vazio */ path(A,Z,P) :- path1(A,Z,[],P). /* Se ja' cheguei ao destino, parar a busca e incluir destino na lista contendo o caminho percorrido */ path1(Z,Z,L,L). /* Se ainda nao cheguei no destino, encontrar caminho parcial de A para Y, adicionar `a lista contendo o caminho parcial e continuar a busca a partir de Y */ path1(A,Z,L,P) :- (caminho(A,Y);caminho(Y,A)), \+ member(Y,L), path1(Y,Z,[Y|L],P). /* encontra caminho parcial de */ /* Y a Z */ </div> <div class="nb-cell query" name="q1"> path(morumbi, tucuruvi, P). </div> <div class="nb-cell markdown" name="md3"> Vamos fazer algumas correções miúdas... </div> <div class="nb-cell program" data-singleline="true" name="p3"> conectado(A, B) :- caminho(A, B); caminho(B, A). path(estação(A), estação(Z), P) :- path_(A, Z, [A], P1), reverse(P1, P). path_(Z,Z,L,L). path_(A,Z,L,P) :- conectado(A, Y), \+ member(Y, L), path_(Y, Z, [Y|L], P). </div> <div class="nb-cell query" name="q2"> path(estação(morumbi), estação(tucuruvi), P). </div> <div class="nb-cell markdown" name="md4"> A pergunta pede para visualizar o caminho que o Prolog percorreu para encontrar o caminho final. Isso é possível de 3 maneiras: 1. Manualmente, usando `trace` para acompanhar todos os passos internos; 2. Com o bom e velho debug orientado a printf, imprimindo o caminho explorado até o momento; 3. Acumulando as mudanças em um termo mutável. Vamos começar pela alternativa #2. </div> <div class="nb-cell program" name="p4"> conectado(A, B) :- caminho(A, B); caminho(B, A). path(estação(A), estação(Z), P) :- path_(A, Z, [A], P1, 0), reverse(P1, P). path_(Z,Z,L,L, _). path_(A,Z,L,P, Depth) :- conectado(A, Y), \+ member(Y, L), format("#~d: caminho(~w, ~w)~n", [Depth, A, Y]), Depth1 is Depth+1, path_(Y, Z, [Y|L], P, Depth1). </div> <div class="nb-cell query" name="q3"> path(estação(morumbi), estação(tucuruvi), P). </div> <div class="nb-cell markdown" name="md5"> Vamos agora tentar armazenar as informações saídas no print (A, Y e Depth) em uma lista mutável. Essa informação é suficiente para construir uma árvore mostrando todas as tentativas, posteriormente. </div> <div class="nb-cell program" name="p5"> conectado(A, B) :- caminho(A, B); caminho(B, A). path(estação(A), estação(Z), P) :- Debug = debug([]), path(estação(A), estação(Z), P, Debug), writeln(Debug). path(estação(A), estação(Z), P, Debug) :- path_(A, Z, [A], P1, 0, Debug), reverse(P1, P). path_(Z,Z,L,L, _, _). path_(A,Z,L,P, Depth, Debug) :- conectado(A, Y), \+ member(Y, L), %%%% arg(1, Debug, Changes), Changes1 = [passo(Depth, A, Y)|Changes], nb_setarg(1, Debug, Changes1), %%%% Depth1 is Depth+1, path_(Y, Z, [Y|L], P, Depth1, Debug). </div> <div class="nb-cell query" name="q4"> path(estação(morumbi), estação(tucuruvi), P). </div> </div>