Prolog 中的简单图形搜索 [英] Simple graph search in Prolog

问题描述

我正在尝试在 SWI-Prolog 中编写一个简单的图形搜索.我想出了以下程序:

I'm trying to code a simple graph search in SWI-Prolog. I came up with the following program:

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).

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

But this program causes a stack overflow. What am I doing wrong and how can it be fixed?

推荐答案

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

You are trying to use the returned path also as a check for avoiding loops. That won't work when searching for a path because the path is not yet instantiated at the negation.

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

The simplest solution is to add another input argument where you collect the nodes already visited and check these to avoid repetition.

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

Also, I think you should check A \== B instead of A \== C. You don't have loops on nodes, so the latter will never happen. The case A == B is handled in the first clause, so you don't want to do that again in the second clause.

你也得到了成员的参数向后，需要修复第一个子句中的列表，正如马丁写的那样.

You also got the arguments of member backwards and need to fix the list in the first clause, as Martin has written.

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

An advanced way to avoid infinite loops without an extra argument is to use freeze/2 on the negation.

另外看看在 Prolog 中调试是如何工作的，这可能会帮助你更好地理解事情.

Also take a look at how debugging works in Prolog, that might help you understand things better.

这篇关于Prolog 中的简单图形搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！