在序言简单的图搜索(Simple graph search in Prolog)

我试图代码SWI-Prolog的一个简单的图形搜索。 我想出了以下程序：

adjacent(1,4). adjacent(4,2). adjacent(3,6).
adjacent(6,4). adjacent(7,10). adjacent(4,9).
adjacent(5,10). adjacent(7,10). adjacent(7,12).
adjacent(6, 11). adjacent(13,11). adjacent(9,14).
adjacent(14,12). adjacent(10,15). adjacent(9,12).

connected(X,Y) :- adjacent(X,Y); adjacent(Y,X).

path(A,B,[A|B]) :-
    connected(A,B).
path(A,B,[A|R]) :-
    \+member(R,A),
    connected(A,C),
    A \== C,
    path(C,B,R).

但此方案导致堆栈溢出。 我在做什么错的，怎么能解决吗？

Answer 1:

您正在尝试使用返回的路径也作为避免环路检查。 搜索的路径时，因为路径还没有在否定实例化是行不通的。

最简单的解决办法是增加在那里你收集已访问过的节点另一输入参数，并将这些检查，以避免重复。

另外，我觉得你应该检查A \ ==乙，而不是A \ == C.你不必对节点的循环，所以后者将永远不会发生。 案例A == B是第一条在处理，所以你不想第二子句中再次做到这一点。

你也得到了成员的争论向后，需要解决的第一条在列表中，马丁写了。

先进的方式，以避免无限循环没有额外的说法是对否定使用冻结/ 2。

另外看看在调试Prolog的是如何工作的，可以帮助你了解事情做得更好。

Answer 2:

这里的主要问题是构件测试：签名member(Element,List) ; 你似乎假定参数是另一种方式“轮。

此外，你的第一个路径谓词是为了测试两个元素的列表，但是，B真的，其余的名单相结合（当时未连接）。

如果你解决这些，你会发现，这只能为完全实例变量的工作，因为否定没有为绑定变量很好地工作。

文章来源: Simple graph search in Prolog