1

我试图在 Prolog 的图中找到一条路径。我设法用我在网上找到的一些片段来解决这个问题。但是，它会跟踪节点以避免两次访问它们，而我需要它不要两次访问同一边缘。这可能在大多数图中归结为相同的事情，但是因为我想用它来计算从边缘上的点到边缘上其他点的路径，我不希望它返回从一个点到相邻节点的路径到相反的节点（比如，如果我们有一条从节点 A 到节点 C 的边 AC，中间有一个点 B，那么 ACB 将不是一条可接受的路径，因为它经过 AC 两次）。

这是我当前的代码：

path(A,B,Nodes,Edges) :- path1(A,[B],Nodes,Edges).
path1(A,[A|P1],[A|P1],[]).
path1(A,[Y|P1],Nodes,Edges) :- 
   connected(X,Y,Edge), \+ memberchk(X,[Y|P1]), path1(A,[X,Y|P1],N1,E1), append(E1,[Edge],Edges).

connected(a,c,ac). % connected(Node1,Node2,Edge) need not represent an edge:
connected(a,b,ac). % it may also refer to a point on the edge.
connected(b,c,ac).

对于上面的示例，这将返回例如：

path(a,b,[a,b],[ac])
path(a,b,[a,c,b],[ac,ac])

现在我想我可以简单地替换\+ memberchk(X,[Y|P1])以\+ memberchk(Edge,S)确保相同的边缘不会两次出现在路径中，这将解决问题。但是，当我这样做时，Prolog 说没有路径。

有人可以向我解释这是哪里出错了吗？

4

1 回答 1

0

这个答案对我有很大帮助：显然这是因为您不能使用尚未实例化的路径来检查循环。它建议使用freeze\2，但我不知道如何在 JIProlog 中处理它。我会为此提出一个新问题。

于 2012-10-04T18:32:18.077 回答