Пролог порядка пунктов приводит к сбою поиска пути

Question

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

Узлы и соседние узлы определены следующим образом:

node(a).
node(b).
node(c).
node(d).
node(e).

edge(a,b).
edge(b,c).
edge(c,d).
edge(b,d).

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

Исходный алгоритм, приведенный ниже, работает нормально:

path2(X,Y) :-
    pathHelper(X,Y,[X]).

pathHelper(X,Y,L) :-
    neighbor(X,Y),
    \+ member(Y,L).
pathHelper(X,Y,H) :-
    neighbor(X,Z),
    \+ member(Z,H),
    pathHelper(Z,Y,[Z|H]).

Это прекрасно работает

[debug]  ?- path2(a,X).
X = b ;
X = c ;
X = d ;
X = d ;
X = c ;
false.

, однако, при изменении порядка двух предложений во втором определении, например, как показано ниже

pathHelper(X,Y,L) :-
    \+ member(Y,L),
    neighbor(X,Y).

При попытке выполнить то же самое здесь, swipl возвращает следующее:

[debug]  ?- path2(a,X).
false.

Запрос больше не работает и возвращает только false. Я пытался понять это с помощью команды trace, но все еще не могу понять, что именно не так.

Другими словами, я не понимаю, почему порядок neighbor(X,Y) и \+ member(Y,L) имеет решающее значение здесь. Имеет смысл иметь neighbor(X,Y) сначала с точки зрения эффективности, но не с точки зрения корректности для меня.

Answer 1

Теперь вы сталкиваетесь с не очень четкими границами чистого Пролога и его нелогичного окружения. Добро пожаловать в реальный мир .

Вернее, не приветствуется! Вместо этого давайте попробуем улучшить ваше определение. Ключевая проблема -

\+ member(Y, [a]), Y = b.

, которая завершается ошибкой, в то время как

Y = b, \+ member(Y,[a]).

завершается успешно. Нет логики c, чтобы оправдать это. Это просто операционный механизм встроенного Пролога (\+)/1.

К счастью, мы можем улучшить это. Введите non_member/2.

non_member(_X, []).
non_member(X, [E|Es]) :-
   dif(X, E),
   non_member(X, Es).

Сейчас,

?- non_member(Y, [a]).
dif(Y,a).

Отметьте этот ответ, он говорит: Да, Y не является элементом [a], если Y отличается от a. Подумайте о многих решениях, включенных в этот ответ, таких как Y = 42 или Y = b и еще бесконечно много таких решений, которые не a. Бесконечно много решений, записанных в девяти символах!

Теперь и non_member(Y, [a]), Y = b, и Y = b, non_member(Y, [a]) успешны. Таким образом, их обмен влияет только на время выполнения и потребление пространства. Если мы на это, обратите внимание, что вы проверяете отсутствие членства в двух пунктах. Вы можете учесть это. Для общего решения c этого см. closure / 3 . При этом вы просто говорите: closure(neighbor, A,B).

Также рассмотрите случай, когда у вас есть только edge(a,a). Ваше определение не подходит для path2(a,X). Но разве это не должно быть успешным?

И название path2/2 не совсем подходит, скорее зарезервируйте это слово для фактического пути .

Answer 2

Сомнение, которое у вас есть, связано с тем, как пролог справляется с отрицанием. Пролог использует отрицание как провал. Это означает, что, если пролог должен отменить цель g (указать ее not(g)), он пытается доказать g, выполнив ее, а затем, если g не удается, not(g) (или * 1006) *, то есть отрицание g) успешно и наоборот.

Имейте в виду также, что после выполнения not(g), если у цели есть переменные, они не будут созданы. Это потому, что пролог должен создавать экземпляр переменных со всеми терминами, которые приводят к сбою g, и это, вероятно, бесконечный набор (например, для списка not(member(A,[a]) должен создавать экземпляр переменной A со всеми элементами, которые не находятся в список).

Давайте рассмотрим пример. Рассмотрим эту простую программу:

test:-
    L = [a,b,c],
    \+member(A,L),
    writeln(A).

и запустите ее с ?- trace, test. Прежде всего вы получите предупреждение Singleton variable in \+: A по причине, которую я объяснил ранее, но давайте проигнорируем ее и посмотрим, что произойдет.

Call:test
 Call:_5204=[a, b]
 Exit:[a, b]=[a, b]
 Call:lists:member(_5204, [a, b])
 Exit:lists:member(a, [a, b]) % <-----
 Fail:test
false

В выделенной строке вы видите, что для переменной A создается значение a, и поэтому member/2 завершается успешно, поэтому \+ member(A,L) ложно.

Итак, в В вашем коде, если вы напишите pathHelper(X,Y,L) :- \+ member(Y,L), neighbor(X,Y)., это предложение будет всегда не выполнено, потому что Y недостаточно инстанцировано. Если вы поменяете местами два термина, Y будет размолоть, и поэтому member/2 может потерпеть неудачу (и \+member завершится успешно).