Prolog中的有向图

Question

有人可以详细说明 travel(A,B,Visited,Path) 和 travel(A,B,P,[B|P]) 的 functionality/conditions .. 这段代码找到了两者之间的路径图中的路径 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).

Answer 1

让我们从第一个 travel/4 规则开始：

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

"If points A and B are directly connected to each other, then we have found a direct sub-path, and hence can succeed by adding point B to the path which is unified with all the points we have visited thus far."

换句话说，由于我们已经解决了一个子问题（通过找到与 2 个节点的直接连接），我们基本上可以声明 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) 前往我们的目的地。然后我们再次递归 query/call travel/4，直到我们找到完整的路径。

再次注意，此实现可能会为给定查询找到 0 个、1 个或 1 个以上的解决方案。

概括地说，调用第一个规则来找到点之间的直接连接。调用第二个规则来查找点之间的间接连接。

Prolog中的有向图

Directed Graph In Prolog

path

prolog

graph-theory

transitive-closure