1

我正在尝试在 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).

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

4

2 回答 2

3

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

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

另外，我认为您应该检查 A \== B 而不是 A \== C。节点上没有循环，因此后者永远不会发生。case A == B 在第一个子句中处理，因此您不想在第二个子句中再次这样做。

正如 Martin 所写的，您还获得了 member 的参数，并且需要修复第一个子句中的列表。

在没有额外参数的情况下避免无限循环的一种高级方法是在否定上使用 freeze/2。

还可以看看 Prolog 中的调试是如何工作的，这可能有助于您更好地理解事物。

于 2009-10-22T16:53:03.193 回答
2

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

此外，您的第一个路径谓词旨在测试一个二元素列表，但是，B 确实与其余列表（然后未连接）统一。

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

于 2009-10-22T14:42:51.607 回答