Em Prolog, por que não adicionar "Edge (x, y):- Edge (y, x)." Somente trabalhe para converter uma definição de gráfico direcionado em um gráfico não direcionado

Question

Estou aprendendo Prolog e revisando notas de aula e todas as notas dizem o seguinte:

dada a seguinte definição para gráficos direcionados:

path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

Se quiséssemos fazer deste um gráfico não direcionado, definindoedge(X, Y) :- edge(Y, X). sozinho não funciona e não consigo descobrir por quê.X para Y tem uma aresta se Y para X tiver uma aresta.Parece fazer sentido para mim.

As notas não esclarecem realmente por que não, mas definem que a solução adequada seria:

edge1(X, Y) :- edge(X, Y).
edge1(X, Y) :- edge(Y, X). 

ao que já tínhamos.

Alguém pode me explicar isso, por favor e obrigado?<3

Answer 1

Porque as regras não funcionam da mesma forma que os fatos, e você entrará em um loop infinito se usar o mesmo predicado.

Vamos dar o exemplo ?-edge(5,2).Acabaremos ligando -

edge(5,2) :- edge(2,5).

OK, o que acontece quando ligamos edge(2,5)?

edge(2,5) :- edge(5,2).

...Ah, ah.Círculo lógico.

Ao usar edge1, você está simplesmente criando um wrapper para seu predicado escapar da definição recursiva.

Answer 2

Existem várias fontes potenciais de não rescisão em seu programa.

Primeiro, com a regra edge(X, Y) :- edge(Y, X). seu programa irá nunca terminar.Independentemente de onde você adicionar esta regra ao seu programa.O que muitas vezes é bastante irritante é que o seu programa ainda produzirá muitas respostas, o que de certa forma sugere que ele funciona.No entanto, isso nunca irá parar.

A melhor maneira de entender isso é considerar um programa ligeiramente modificado, chamado fatia de falha.Este programa modificado compartilhará muitas propriedades com o seu programa.Não todos eles, mas alguns.Vamos adicionar metas false em seu programa.Se o programa resultante fizer um loop, o programa original também fará um loop.

path(X, Y) :- edge(X, Y), falso.
caminho (X, Y): - falso, aresta (X, Z), caminho (Z, Y).

borda (a, b): - falso.
edge(X, Y) :- edge(Y, X).

Em segundo lugar, há outra fonte de não rescisão no seu programa melhorado.Aqui está a fatia de falha relacionada:

caminho (X, Y): - falso, borda1(X, Y).
path(X, Y) :- edge1(X, Z), path(Z, Y), falso.

edge1(X, Y) :- edge(X, Y).
edge1(X, Y) :- edge(Y, X).

edge(a, b).

edge1/2 agora sempre contém ciclos, então este fragmento fará um loop para path(a, Y).e mais geralmente também path(X, Y), false.

Para resolver este problema, você terá que reescrever path/2.

Você pode reescrever isso de maneira genérica usando closure0/3 e path/4!

Então path/2 pode ser definido como:

path(X, Y) :-
   closure(edge, X, Y).