Warum in Prolog, warum nicht "Kante (x, y):- Kante (y, x) hinzugefügt". Allein arbeiten Sie für die Konvertierung einer gerichteten Diagrammdefinition in eine ungerichtete Grafik

Question

Ich lerne gerade Prolog und überprüfe Vorlesungsnotizen. In allen Notizen steht Folgendes:

gegeben die folgende Definition für gerichtete Graphen:

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

Wenn wir dies zu einem ungerichteten Graphen machen wollten, definierenedge(X, Y) :- edge(Y, X). allein funktioniert nicht, und ich kann nicht herausfinden, warum.X zu Y hat eine Kante, wenn Y zu X eine Kante hat.Scheint für mich Sinn zu ergeben.

In den Anmerkungen wird nicht wirklich klargestellt, warum nicht, aber es wird definiert, dass die richtige Lösung wie folgt wäre:

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

zu dem, was wir bereits hatten.

Kann mir das bitte jemand erklären, danke?<3

Answer 1

Da die Regeln nicht gleich wie Fakten funktionieren, und Sie spirlen in eine unendliche Schleife, wenn Sie dasselbe Prädikat verwenden.

Nehmen wir das Beispiel?-edge(5,2).Wir werden am Ende anrufen -

generasacodicetagpre.

ok, was passiert, wenn wir edge(2,5) anrufen?

generasacodicetagpre.

... uh oh oh.Logikkreis.

Bei Verwendung von edge1 erstellen Sie einfach einen Wrapper für Ihr Prädikat, um der rekursiven Definition zu entkommen.

Answer 2

Es gibt mehrere potenzielle Ursachen für die Nichtbeendigung Ihres Programms.

Erstens mit der Regel edge(X, Y) :- edge(Y, X). Ihr Programm wird es tun niemals beenden.Unabhängig davon, wo Sie diese Regel zu Ihrem Programm hinzufügen.Was oft ziemlich irritierend ist, ist, dass Ihr Programm immer noch viele Antworten liefert, was ein wenig darauf hindeutet, dass es funktioniert.Allerdings wird es nie aufhören.

Der beste Weg, dies zu verstehen, besteht darin, ein leicht modifiziertes Programm namens a zu betrachten Fehlerscheibe.Dieses modifizierte Programm teilt viele Eigenschaften mit Ihrem Programm.Nicht alle, aber einige.Wir werden Ziele hinzufügen false in Ihr Programm integrieren.Wenn das resultierende Programm eine Schleife durchläuft, wird auch das Originalprogramm eine Schleife durchlaufen.

path(X, Y) :- edge(X, Y), FALSCH.
Pfad(X, Y) :- FALSCH, Kante(X, Z), Pfad(Z, Y).

Kante(a, b) :- FALSCH.
edge(X, Y) :- edge(Y, X).

Zweitens gibt es in Ihrem verbesserten Programm eine weitere Quelle der Nicht-Kündigung.Hier ist der zugehörige Fehler-Slice:

Pfad(X, Y) :- FALSCH, Kante1(X, Y).
path(X, Y) :- edge1(X, Z), path(Z, Y), FALSCH.

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

edge(a, b).

edge1/2 enthält jetzt immer Zyklen, sodass dieses Fragment eine Schleife durchführt path(a, Y).und allgemeiner auch path(X, Y), false.

Um dieses Problem zu lösen, müssen Sie neu schreiben path/2.

Sie können dies auf generische Weise umschreiben, indem Sie verwenden closure0/3 Und path/4!

Also path/2 kann definiert werden als:

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