Обход графа (с возможными циклами) и возврат пути в Прологе

Question

Мне дан список дуг:

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

Я написал набор предложений, которые сообщат мне, есть ли путь от узла X к узлу Y.Циклы могут возникать, и я это учел.

path(X,Y) :-
    arc(X,Y).
path(X,Y) :-
    arc(X,Z),
    path(Z,Y,[X]).

path(X,Y,P) :-
    arc(X,Y).
path(X,Y,P) :-
    \+ member(X,P),
    arc(X,Z),
    append([X],P,L),
    path(Z,Y,L).

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

Я предполагаю, что мой базовый случай будет выглядеть как path2(X,Y,[X,Y]) :- arc(X,Y)., но это не сработает с моей программой.Что-то не так с моим решением для предыдущей части, или я просто пропускаю небольшую модификацию?Любая помощь будет оценена.Спасибо!

Answer 1

Закрыть ... но учтите:

path(Start, End, Path) :-
    path(Start, End, [], Path).

Вызов path/3 с начальным и конечным узлом создаст путь между ними, если таковой существует, и возврат, чтобы дать вам альтернативные маршруты.Ни один узел не посещается дважды.[] является списком узлов аккумуляторов , поэтому мы можем проверить, что мы не будем двигаться по кругу при построении пути.

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    Mid == End, !,
    append(Acc, [Now, End], Path).

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    \+ member(Mid, Acc),
    path(Mid, End, [Now|Acc], Path).

Эти предикаты выполняют реальную работу.Первый - это базовый случай, когда конечный узел достигается с помощью другого вызова arc/2;в этом случае путь был построен.Второй пересекает (направленный) граф, но только для узлов, которые еще не были посещены.

Все пути могут быть найдены одновременно, используя findall/3 через:

findall(Path, path(Start,End,Path), Paths).

Для связанных значений Start и End для узловых узлов.

Answer 2

Перейдите на более высокий уровень и используйте переходное замыкание ¹ в качестве основного идиома!

%        <i>your</i> binary predicate arc/2 gets used here
%         |
%         v
?- <a href="https://stackoverflow.com/q/30328433/4609915">path</a>(arc, Path, From, To).
   From = To       , Path = [To]
;  From = a, To = b, Path = [a,b] 
;  From = a, To = c, Path = [a,b,c]
;  From = a, To = d, Path = [a,b,c,d]
;  From = a, To = e, Path = [a,b,c,d,e]
;  From = a, To = f, Path = [a,b,c,d,e,f]
;  From = b, To = c, Path = [b,c]
;  From = b, To = d, Path = [b,c,d]
;  From = b, To = e, Path = [b,c,d,e]
;  From = b, To = f, Path = [b,c,d,e,f]
;  From = c, To = d, Path = [c,d]
;  From = c, To = b, Path = [c,d,b]
;  From = c, To = e, Path = [c,d,e]
;  From = c, To = f, Path = [c,d,e,f]
;  From = d, To = b, Path = [d,b]
;  From = d, To = c, Path = [d,b,c]
;  From = d, To = e, Path = [d,e]
;  From = d, To = f, Path = [d,e,f]
;  From = e, To = f, Path = [e,f]
;  false.

---

^{Сноска 1: В соответствии с универсальным мета-предикатом path/4.}

Answer 3

Ответ, данный sharky, похоже, не работает для меня, но следующий мод делает и кажется мне более простым.:

path(Now, End, Acc, [Now,End]) :-
    arc(Now, End),
    \+ member(Now, Acc),
    \+ member(End, Acc).

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    \+ member(Mid, Acc),
    path(Mid, End, [Now|Acc], Path).

Скажи мне, если я что-то упустил.