Пролог: порядок предложений для поиска пути в графе

Question

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

entry(a).
exit(e).
exit(f).

next(a, b).
next(b, c).
next(b, d).
next(c, e).
next(d, f).

/* Cycle */
next(c, d).
next(d, b). 

/* path(entrynode, exitnode, pathtrace) */
path(X, Y, P)       :- entry(X), path2(X, Y, P).
path2(X, Y, [Y])    :- next(X, Y), exit(Y).
path2(X, Y, [P|PS]) :- next(X, P), path2(P, Y, PS).

Мой предикат path2 прекрасно работает на нециклическом графе,Теперь я хочу распространить его на циклические.Все, что мне нужно сделать, это проверить, есть ли новый возможный узел в моем списке посещенных узлов.Для этого я бы добавил not(member(X, PS)) к моему последнему правилу.

Если я добавлю его перед рекурсией, он всегда вернет false.Если я добавлю его после рекурсии, Пролог сначала попытается найти пути и выйдет из стека.Он возвращает правильные ответы, но пытается найти больше и застревает.

Поэтому: где я должен добавить чек или что я сделал неправильно / что я могу сделать лучше?

Answer 1

Вам нужен дополнительный аргумент для вашего предиката path2/3, поскольку ваш третий аргумент - это путь , составленный , а не список посещенных узлов.Т.е. вы не можете просто добавить цель \+ member(X,Ps) к последнему правилу предиката, поскольку Ps связан рекурсивным вызовом.Попробуйте вместо:

path(X, Y, P) :-
    entry(X),
    path2(X, Y, [], P).

path2(X, Y, _Visited, [Y]) :-
    next(X, Y),
    exit(Y).
path2(X, Y, Visited, [P|PS]) :-
    next(X, P),
    \+ member(P, Visited),
    path2(P, Y, [P| Visited], PS).

Пример звонков:

| ?- path(X, Y, P).                        

P = [b,c,e]
X = a
Y = e ? ;

P = [b,c,d,f]
X = a
Y = f ? ;

P = [b,d,f]
X = a
Y = f ? ;

no