1

有人可以详细说明 travel(A,B,Visited,Path) 和 travel(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).
4

1 回答 1

1

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

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

“如果 A 点和 B 点直接相互连接，那么我们就找到了一条直接子路径，因此可以通过将 B 点添加到与我们迄今为止访问过的所有点统一的路径中来成功。”

换句话说，由于我们已经解决了一个子问题（通过找到到 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) 前往目的地。travel/4然后我们再次递归查询/调用，直到找到完整的路径。

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

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

于 2016-10-16T18:10:30.530 回答