在Prolog中的简单图搜索

我想在SWI-Prolog中编码一个简单的图搜索。我想出了以下程序：在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).

但是这个程序会导致堆栈溢出。我做错了什么，如何解决？

来源

2009-10-22 ziggystar

我的序言有些生疏，请问您能否就每个部分的意图添加一些评论？ – fortran 2009-10-22 14:39:28

'path（A，B，Path）： - path（adjacent，Path，A，B）.' using ['path/4']（http://stackoverflow.com/q/30328433）。 – false 2016-04-08 09:34:32

您正尝试使用返回的路径作为避免循环的检查。这在搜索路径时不起作用，因为路径尚未在否定处实例化。

最简单的解决方案是添加另一个输入参数，您可以在其中收集已访问的节点并检查这些节点以避免重复。

此外，我认为你应该检查A \ == B而不是A \ == C.你没有节点上的循环，所以后者将永远不会发生。案例A == B在第一个条款中处理，因此您不希望在第二个条款中再次这样做。

您也得到了反向成员的论点，需要修正第一个子句中的列表，正如Martin写的。

避免无限循环而没有额外参数的高级方法是对否定使用freeze/2。

另外看看如何在Prolog中进行调试，这可能会帮助你更好地理解事物。

来源

2009-10-22 16:53:03 starblue

这里的主要问题是成员测试：签名是member(Element,List);你似乎认为论点是相反的。

此外，你的第一个路径谓词是为了测试一个双元素列表，然而，B真正与其余列表（然后没有连接）统一。

如果您修复这些问题，您会发现这只适用于完全实例化的变量，因为否定对于未绑定的变量不起作用。

来源

2009-10-22 14:42:51

在Prolog中的简单图搜索

回答

相关问题