1

Dado a busca em largura nos grafos em prolog, um grafo aonde um nó se conecta ao outro atraves do fato conectado(a,b). conectado(b,c). conectado(b,e). e assim por diante, o algoritmo normalmente funcionaria retornando para o usuario a rota mais curta entre algum nó de partida, sendo o primeiro ou nao, e o nó destino, podendo tambem ser qualquer um. O algoritmo se pareceria com este:

/* 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) :- (conectado(A,Y);conectado(Y,A)),
       \+ member(Y,L),
      path1(Y,Z,[Y|L],P). /* encontra caminho parcial de */
                          /* Y a Z */

Porem eu busco algo diferente para a minha aplicacao, preciso nao receber o caminho mais curto entre o ponto de partida e o de destino, mas sim quero receber o caminho virtual que o algoritmo percorreu para obter esse resultado. Isto é, se ele teve que checar todos os nos da mesma largura, pra so depois aumentar a profundidade, ja que isto que o busca em largura faz obviamente, quero receber nao o caminho direto para o objetivo, mas o caminho figurativo que o algoritmo teve de fazer, isto é, que o caminho que ele me retorne contenha todos nos na mesma largura antes de passar para o proximo nivel, ao inves de nao inclui-los na resposta ao ver que existe um caminho mais curto. Basicamente eu nao quero receber o melhor caminho ideal de X até Y, e sim o caminho que o algoritmo busca em largura teve que percorrer no grafo para me retornar este caminho, como se fosse um debug

1 Resposta 1

0

A sua implementação não é de busca em largura, mas sim de profundidade. A resolução SLD do Prolog tem essa característica de sempre buscar as regras na ordem em que são apresentadas no programa, o que no seu caso faz com que conectados(A, Y) seja percorrido como num grafo.

Dito isso, eu vejo 3 maneiras de você conseguir o que deseja:

  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 os passos em um termo mutável.

Vamos começar pela alternativa #2 com a função format/2. Na minha versão, as arestas do grafo são armazenadas como caminho(A, B), e eu guardo a profundidade alcançada a partir da origem. Isso permitiria reconstruir uma árvore das tentativas.

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).

Na alternativa #3, vamos utilizar o predicado nb_setarg/3, que altera o argumento de uma struct de forma mutável, sem desfazer no backtrack.

Note que Debug recebe debug([]) inicialmente, mas como ele é modificado como parte da busca, o writeln(Debug) vai imprimir algo diferente do inicial -- uma operação que não é lógica!

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).

Você pode executar esse código no Swish (SWI-Prolog online) em um notebook, usando uma parte do metrô de SP como exemplo!

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .