Определить граф в Prolog: edge и path, найти, существует ли путь между двумя вершинами

Я очень новичок в Prolog. Я определил в graph.pl следующий график:

И вот мой код Пролога:

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).

Я понимаю это так: существует путь между вершиной X и вершиной Y, только если существует ребро между вершиной X и вершиной Z И есть путь между вершинами Z и vertex Y (некоторая рекурсия).

Правильно ли это для представленного графика? Когда я спрашиваю Пролог о пути между вершиной A и вершиной F, он дает мне true... который даже не прав! Что может быть неправильным в этом коде?

Ответы

Ответ 1

Циклы на графике. Вам нужно отслеживать, какие узлы вы посещаете, и проверить их. Попробуйте это, используя хелперный предикат с аккумулятором для отслеживания посещенных узлов:

path(A,B) :-   % two nodes are connected, if
  walk(A,B,[]) % - if we can walk from one to the other,
  .            % first seeding the visited list with the empty list

walk(A,B,V) :-       % we can walk from A to B...
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - we haven't yet visited X, and
  (                  % - either
    B = X            %   - X is the desired destination
  ;                  %   OR
    walk(X,B,[A|V])  %   - we can get to it from X
  )                  %
  .                  % Easy!

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

Ответ 2

Формат, который вы используете (edge /2), имеет смысл для изучения Prolog, и вы должны следовать советам mbratch о учебнике.

На самом деле, есть хорошие альтернативы, которые уже доступны, в некоторых случаях с полезными предикатами, готовыми к работе: например, в библиотеке (ugraph), reachable/3. Теперь, с вашими данными, этот предикат path/2

path(X,Y) :-
    findall(A-B, edge(A,B), Es),
    vertices_edges_to_ugraph([],Es,G),
    reachable(X,G,Path),
    member(Y,Path).

делает

?- path(a,X).
X = a ;
X = b ;
X = c ;
X = d ;
X = e.

Посмотрим, что это значит:

findall(A-B, edge(A,B), Es)

поместите в Es все ребра с обозначением, требуемым библиотекой,

vertices_edges_to_ugraph([],Es,G)

строит в G соответствующий граф

reachable(X,G,Path)

составить список Путь всех вершин, достижимых (duh) из X

member(Y,Path)

посмотрим, присутствует ли Y в пути.

Поскольку я запросил у Y бесплатно, я получаю все достижимые вершины из X, что я привязан к a.

Ответ 3

Если вам интересно узнать, существует ли путь к файлу — но необязательно в фактическом пути — вычислять транзитное закрытие бинарного отношения edge/2.

К счастью для вас, transitive-closure общая идиома в prolog!

Чтобы выразить нерефлексивное транзитивное замыкание edge/2, используйте meta-predicate closure/3 — определено в более раннем вопросе Определение рефлексивного транзитивного закрытия ":

?- closure(edge, X, Y).
   X = a, Y = e
;  X = a, Y = d
;  X = a, Y = c
;  ...

Обратите внимание, что closure/3 имеет очень хорошие свойства завершения.

Если все кластеры edge/2 являются основными фактами, closure(edge, _, _) завершается повсеместно! Посмотрите:

?- closure(edge, _, _), false.
false.

Ответ 4

Он проверяет цикл! Я выполнил пример с помощью команды trace. перед вами и увидел, что программа вернется к проблеме, чтобы найти путь от a до f после циклического перемещения. path (a, f) требует, чтобы путь (e, f) был истинным, следуя короткой нотации, мы должны быть правдой:

(d, f), (c, f), (b, f), затем (a, f) снова.

Чтобы решить цикл, вам нужен механизм для предотвращения цикла. Моя первая идея состояла бы в том, чтобы сохранить список node -names, а также проверить, если список не содержит текущий X при проверке пути.