Перечисление всех прогулок в графе

Question

Учитывая представление термина ребра графа, то есть:

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

Я хотел бы построить предикат path/1, который успешно выполняется, если его единственный аргумент является допустимым путем в этом графе (чтоесть, для каждых двух смежных слагаемых X, Y, edge(X, Y).Учитывая переменную, она должна перечислять все прогулки (которые могут иметь повторяющиеся узлы).Моя первая попытка:

path([X, Y]) :- edge(X, Y).
path([X, Y, Z | T]) :-
  path([Y, Z | T]),
  edge(X, Y).

Он работает как задумано, за исключением случая, когда ему предоставляется ациклический граф - path находит все решения и затем останавливается, не в состоянии построить какой-либо другой путь.С другой стороны, замена первого и второго слагаемых приведет к пропуску многих прогулок из-за DFS-природы разрешения Пролога.

Моя вторая попытка:

path(P) :- length(P, L), L >= 2, (path(P, L) *-> true ; (!, fail)).

path([X, Y], 2) :- edge(X, Y).
path([X, Y, Z | T], L) :-
  L >= 3,
  L1 is L - 1,
  edge(X, Y),
  path([Y, Z | T], L1).

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

Answer 1

Учитывая ваше определение графа:

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

Что-то похожее должно сделать вас:

path(P) :-
  node(X),
  walk(X,_,P)
  .

walk(A,B,P) :-
  walk(A,B,[],V),
  reverse(V,R),
  P = [A|R]
  .               

walk( A, B, T, V ) :-
  edge(A,X),              
  not( member(X,T) ),
  (
    ( B = X , V = [B|T] )
  ;
    walk( X, B, [A|T], V )
  )
  . 

%
% enumerate the distinct nodes in edge/2 via backtracking
%
node(N) :-
  setof( X , edge(X,_);edge(_,X) , Ns ),
  node( Ns , N )
  .

node( [N|_] , N ).
node( [_|Ns] , N ) :- ( Ns , N ).

Answer 2

Тестируя ваше первое решение, после нахождения трех путей ([a,b], [a,c], [a,b,c]) оно зацикливается. Один очень быстрый способ избежать этого - использовать табулирование, которое доступно в XSB, SWI и YAP. В случае SWI просто добавьте :- table path/1. в качестве первой директивы, чтобы избежать циклов. В противном случае вам нужно запомнить весь путь, и есть множество ответов, на которые вы можете посмотреть (например, this ).