В Prolog, почему добавление «Edge (x, y):- Edge (y, x)». Одно работает для преобразования направленного определения графика в неориентированный график

Question

Я только изучаю Пролог, просматриваю конспекты лекций, и все в них написано следующее:

дано следующее определение ориентированных графов:

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

Если бы мы хотели сделать это неориентированным графом, определяяedge(X, Y) :- edge(Y, X). сам по себе не работает, и я не могу понять, почему.От X до Y есть ребро, если от Y до X есть ребро.Кажется, это имеет смысл для меня.

Примечания на самом деле не поясняют, почему бы и нет, но определяют, что правильным решением будет:

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

к тому, что у нас уже было.

Может кто-нибудь объяснить мне это, пожалуйста и спасибо?<3

Answer 1

Потому что правила не работают так же, как факты, и если вы используете один и тот же предикат, вы скатываетесь в бесконечный цикл.

Давайте возьмем пример ?-edge(5,2).В конце концов мы позвоним...

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

Хорошо, что происходит, когда мы звоним edge(2,5)?

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

...Ой-ой.Логический круг.

Когда используешь edge1, вы просто создаете оболочку для своего предиката, чтобы избежать рекурсивного определения.

Answer 2

В вашей программе есть несколько потенциальных источников незавершения завершения.

Во-первых, с правилом edge(X, Y) :- edge(Y, X). ваша программа будет никогда прекратить.Независимо от того, где вы добавляете это правило в свою программу.Что часто весьма раздражает, так это то, что ваша программа по-прежнему выдает много ответов, что в некоторой степени предполагает, что она работает.Однако это никогда не прекратится.

Лучший способ понять это — рассмотреть слегка модифицированную программу, называемую срез сбоя.Эта модифицированная программа будет иметь много общих свойств с вашей программой.Не все, но некоторые.Мы добавим цели false в вашу программу.Если полученная программа зациклится, исходная программа также зациклится.

path(X, Y) :- edge(X, Y), ЛОЖЬ.
путь(X, Y) :- ЛОЖЬ, ребро(X, Z), путь(Z, Y).

край(а, б):- ЛОЖЬ.
edge(X, Y) :- edge(Y, X).

Во-вторых, в вашей улучшенной программе есть еще один источник незавершенности завершения.Вот связанный срез сбоя:

путь(X, Y) :- ЛОЖЬ, край1(X, Y).
path(X, Y) :- edge1(X, Z), path(Z, Y), ЛОЖЬ.

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

edge(a, b).

edge1/2 теперь всегда содержит циклы, поэтому этот фрагмент будет зацикливаться path(a, Y).и в более общем плане также path(X, Y), false.

Чтобы решить эту проблему, вам придется переписать path/2.

Вы можете переписать это в общем виде, используя closure0/3 и path/4!

Так path/2 можно определить как:

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