Пролог Бесконечный цикл на круговых фактах - PullRequest
Новая
       46

Пролог Бесконечный цикл на круговых фактах

2 голосов
/ 25 марта 2019

Вот круглая часть моих фактов (определите отношения между людьми): 

connection(harry, ron).
connection(ron, harry).
connection(hermione, harry).

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

Этот код работает в бесконечном цикле в описанной выше ситуации: 

connected(A, B) :-
   connection(A, B).
connected(A, B) :- 
   connection(A, C),
   connected(C, B).

Я хочу, чтобы рекурсия остановилась, когда встретится с предыдущими поисками.Например: 

?- connected(hermione, X).
X = harry ;
X = ron.

Спасибо!

Ответы [ 2 ]

3 голосов
/ 25 марта 2019

Механизм исполнения Пролога не интуитивно понятен. Он сочетает в себе рекурсию (как вы знаете из других языков) с возвратом. Но есть хороший выход. Вы можете рассмотреть небольшие программы вместо вашей оригинальной программы.

Чтобы лучше понять действительный цикл, вот минимальный фрагмент программы, называемый , который является причиной отсутствия завершения. В этом есть дополнительная фальшивка: некоторые цели false. С этими целями количество выводов уменьшается (или остается неизменным). Таким образом, когда результирующая программа зацикливается, это также является причиной, по которой ваша исходная программа зацикливается. 

connection(harry, ron).
connection(ron, harry).
<s>connection(herminone, harry) :- <b>false</b></s>.

<s>connected(A, B) :- <b>false</b>, connection(A, B)</s>.
connected(A, B) :-
    connection(A, C),
    connected(C, B), <b>false</b>.

?- connected(A, B).

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

?- connected(tom, B).
   false.

Чтобы решить эту проблему, проще всего использовать closure/3 примерно так: 

connected(A, B) :-
   closure(connection, A, B).
1 голос
/ 16 апреля 2019

Вы можете попробовать таблинг. Многие системы Prolog имеют директиву table / 1. Вы просто должны поместить его перед предикатом, который хотите табулировать. 

:- table connected/2.
connected(A, B) :-
   connection(A, B).
connected(A, B) :- 
   connection(A, C),
   connected(C, B).

Если вы затем запустите запрос, рекурсия автоматически остановится. Вот пример запуска с вкладкой SWI-Prolog: 

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.4)

?- connected(hermione, X).
X = harry ;
X = ron.
...