Направленный граф в Прологе

может кто-нибудь уточнить функциональность/условия путешествия (A, B, Visited, Path) и путешествия (A, B, P, [B | P]).. этот код находит путь между путем A и B на графике

edge(a,b).
edge(b,c).
edge(b,d).
edge(c,d).
edge(d,b).
edge(e,f).
edge(e,g).
edge(e,h).
edge(h,i).
edge(i,g).
edge(b,e).

connectedEdges(X,Y) :- edge(X,Y).
connectedEdges(X,Y) :- edge(Y,X). 

path(A,B,Path) :-
       travel(A,B,[A],Q), 
       reverse(Q,Path).

travel(A,B,P,[B|P]) :- 
       connectedEdges(A,B).

travel(A,B,Visited,Path) :-
       connectedEdges(A,C),           
       C \== B,
       \+member(C,Visited),
       travel(C,B,[C|Visited],Path).

path graph-theory prolog transitive-closure
person Community    schedule 16.10.2016    source источник
comment
Пожалуйста, не оскверняйте собственные посты.   -  person DJMcMayhem    schedule 18.10.2016

Ответы (1)


arrow_upward
1
arrow_downward

Начнем с первого правила travel/4:

travel(A,B,P,[B|P]) :- 
   connectedEdges(A,B).

«Если точки A и B напрямую связаны друг с другом, то мы нашли прямой подпуть и, следовательно, можем добиться успеха, добавив точку B к пути, который объединен со всеми точками, которые мы посетили до сих пор».

Другими словами, поскольку мы решили подзадачу (найдя прямое соединение с двумя узлами), мы можем по существу сказать, что P (все, что мы посетили до сих пор), является хвостом списка путей [B|P] (общее путь — это последний посещенный нами узел.... текущий узел назначения, предваряющий все предыдущие посещенные нами узлы).

Теперь о следующем правиле travel/4:

travel(A,B,Visited,Path) :-
   connectedEdges(A,C),           
   C \== B,
   \+member(C,Visited),
   travel(C,B,[C|Visited],Path).

Важно отметить, что это второе правило всегда будет использоваться в качестве альтернативы, независимо от того, сработало ли первое правило. Из-за этого факта этой реализации подразумевается, что этот код может найти несколько путей (если существует более одного).

Во всяком случае, в этом втором правиле мы находим любые узлы, которые подключены к A, кроме B. Почему? Это потому, что первое правило выше уже пробовало это; в этом правиле мы ищем альтернативы. Если этот узел C еще не был посещен, мы просто пытаемся перейти от этой точки (C) к месту назначения. Затем мы рекурсивно запрашиваем/вызываем travel/4 еще раз, пока не найдем полный путь(и).

Еще раз обратите внимание, что эта реализация может найти 0, 1 или более 1 решения для данного запроса.

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

person eazar001    schedule 16.10.2016