Простой поиск графиков в Прологе

Question

Я пытаюсь написать простой график поиска в SWI-Prolog. Я придумал следующую программу:

adjacent(1,4). adjacent(4,2). adjacent(3,6).
adjacent(6,4). adjacent(7,10). adjacent(4,9).
adjacent(5,10). adjacent(7,10). adjacent(7,12).
adjacent(6, 11). adjacent(13,11). adjacent(9,14).
adjacent(14,12). adjacent(10,15). adjacent(9,12).

connected(X,Y) :- adjacent(X,Y); adjacent(Y,X).

path(A,B,[A|B]) :-
    connected(A,B).
path(A,B,[A|R]) :-
    \+member(R,A),
    connected(A,C),
    A \== C,
    path(C,B,R).

Но эта программа вызывает переполнение стека. Что я делаю не так и как это можно исправить?

Answer 1

Вы пытаетесь использовать возвращенный путь также в качестве проверки для избежания циклов. Это не сработает при поиске пути, потому что путь еще не создан при отрицании.

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

Кроме того, я думаю, что вы должны проверить A \ == B вместо A \ == C. У вас нет петель на узлах, поэтому последнее никогда не произойдет. Случай A == B обрабатывается в первом предложении, поэтому вы не хотите делать это снова во втором предложении.

Вы также получили аргументы члена в обратном направлении и должны исправить список в первом предложении, как писал Мартин.

Продвинутый способ избежать бесконечных циклов без лишних аргументов - использовать freeze / 2 для отрицания.

Также взгляните на то, как отладка работает в Прологе, которая может помочь вам лучше понять вещи.

Answer 2

Основная проблема здесь - членский тест: подпись member(Element,List); Вы, кажется, предполагаете, что аргументы противоположны.

Кроме того, ваш первый предикат пути предназначен для тестирования двухэлементного списка, однако B действительно объединяется с остальным списком (который затем не подключен).

Если вы исправите их, вы обнаружите, что это может работать только для полностью созданных экземпляров переменных, поскольку отрицание не работает хорошо для несвязанных переменных.