Предотвращение бесконечной рекурсии, но все еще использование только несвязанной передачи параметров

Question

У меня есть следующая рабочая программа: (Она может быть протестирована на этом сайте: http://swish.swi-prolog.org/, я удалила прямую ссылку на сохраненную программу, потому что я заметила, что любой может ее редактировать.)

Он ищет путь между двумя точками в неориентированном графе. Важной частью является то, что результат возвращается в области действия "основного" предиката. (В переменной Track)

edge(a, b).
edge(b, c).
edge(d, b).
edge(d, e).
edge(v, w).

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

path(X, X, _, []) :-
    connected(X, _).

path(X, Y, _, [X, Y]) :-
    connected(Y, X).

path(X, Z, Visited, [X|Track]) :-
    connected(X, Y),
    not(member(X, Visited)),
    path(Y, Z, [X|Visited], Track).

main(X, Y) :-
    path(X, Y, [], Track),
    print(Track),
    !.

Результаты:

?- main(a, e).
[a, b, d, e]
true

?- main(c, c).
[]
true

?- main(b, w).
false

Мои вопросы:

1. Список посещенных узлов передается предикатам двумя различными способами. В связанной переменной Visited и в переменной unbound Track. Как называются эти 2 различные формы передачи параметров?

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

Большое спасибо!

Answer 1

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

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

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

foo([]).
foo([X|Xs]) :-
    foo(Xs).

Это хорошо, если только вам не нужно знать, какие элементы вы уже видели, прежде чем попасть сюда:

bar(List) :-
    bar_(List, []).

bar_([], _).
bar_([X|Xs], Acc) :-
    /* Acc is a list of all elements so far */
    bar_(Xs, [X|Acc]).

Это примерно так же, как то, что вы делаете в своем коде. И если вы посмотрите на это, в частности:

path(X, Z, Visited, /* here */[X|Track]) :-
    connected(X, Y),
    not(member(X, Visited)),
    path(Y, Z, [X|Visited], /* and here */Track).

Последний аргумент path/4 имеет один элемент больше на глубину, один меньше в дереве доказательств! И, конечно же, третий аргумент - это более длинный аргумент (он растет по мере того, как вы спускаетесь по дереву доказательства).

Например, вы можете изменить список, добавив еще один аргумент в глупую bar предикат выше:

list_reverse(L, R) :-
    list_reverse_(L, [], R).

list_reverse_([], R, R).
list_reverse_([X|Xs], R0, R) :-
    list_reverse_(Xs, [X|R0], R).

Я не знаю какого-либо специального имени для последнего аргумента, который свободен в начале и содержит решение в конце. В некоторых случаях это может быть выходной аргумент, потому что он предназначен для захвата выходных данных после некоторого преобразования входных данных. Во многих случаях лучше избегать думать об аргументах как о строго вводимых или выводимых аргументах. Например, length/2:

?- length([a,b], N).
N = 2.

?- length(L, 3).
L = [_2092, _2098, _2104].

?- length(L, N).
L = [],
N = 0 ;
L = [_2122],
N = 1 ;
L = [_2122, _2128],
N = 2 . % and so on

Примечание: в вашем коде немало незначительных проблем, которые не являются критичными, и предоставление такого большого количества советов не является хорошей идеей в Stackru. Если вы хотите, вы можете отправить это как вопрос на Code Review.

Изменить: вы должны обязательно изучить этот вопрос.

Я также предоставил несколько более простое решение здесь. Обратите внимание на использование term_expansion/2 для создания направленных ребер из неориентированных ребер во время компиляции. Более важно: вам не нужно основное, просто вызовите нужный предикат с верхнего уровня. Когда вы отбрасываете срез, вы получите все возможные решения, когда один или оба ваших аргумента From и To являются свободными переменными.