Избегать бесконечной рекурсии, но по-прежнему использовать только несвязанную передачу параметров

У меня есть следующая рабочая программа: (Ее можно протестировать на этом сайте: 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 и в несвязанной переменной Track. Как называются эти 2 разные формы передачи параметров?

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

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


recursion undirected-graph graph-algorithm prolog bound-variable
person Crouching Kitten    schedule 11.10.2016    source источник
comment
Края ненаправленные? Я знаю, что это может показаться немного расточительным, но моделирование неориентированной кромки как двух направленных кромок, поэтому edge(a, b). edge(b,a). вместо просто edge(a,b). имеет некоторые желательные свойства.   -  person    schedule 11.10.2016
comment
@Boris: Спасибо, я обновил свой вопрос. Да, это не направлено. Итак, теперь я добавил связанный предикат, который имеет свойство коммутативности.   -  person Crouching Kitten    schedule 11.10.2016
comment
Когда вы имеете в виду несвязанный способ, вы имеете в виду вызов main (a, e, Trace) с переменной trace?   -  person coder    schedule 12.10.2016
comment
@coder: нет, функциональность такая же, как сейчас. Я просто хочу сделать код менее избыточным и избавиться от параметра Visited (третий). Но когда я использовал только Track, проверка на not (member (X, Track)), похоже, не сработала.   -  person Crouching Kitten    schedule 12.10.2016
comment
Ну, он не может работать с Track, потому что Track не создается (это переменная), и вы не можете проверить, существует ли что-то в переменной (поскольку это переменная, это может быть что угодно). Чтобы избавиться от посещенных, может быть, есть другие способы, но ничего очевидного ...   -  person coder    schedule 12.10.2016

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

person Community    schedule 12.10.2016
comment
Спасибо, так что трек вроде как в будущем. Да, я видел, что когда я удалил окончательный вариант и запросил больше ответов, он тоже начал выводить неверные. - person Crouching Kitten; 12.10.2016
comment
@CrouchingKitten Да, я думаю, что связанная мной программа не имеет этой проблемы (в ней явно указано, что From и To должны быть разными!). С другой стороны, вопрос, который я связал, является обобщением того, что вы пытались сделать, и он может быть полезен, если вы потратите время на то, чтобы выяснить, что он делает. - person ; 12.10.2016