2

我在这个网站上阅读了其他类似的问题和答案，但似乎无法找到我的特定问题的答案。我正在尝试在 Prolog 中编码一个迷宫。从区域 0 可以自由移动到区域 1 或区域 3。从区域 3 可以自由移动到区域 0、区域 4 或区域 5 等。我想找到长度为 7 的所有路径从开始到结束（从 0 到 14）。我在 SWI-Prolog 中以下列方式对问题进行了编码：

    region(0).
    region(1).
    region(2).
    region(3).
    region(4).
    region(5).
    region(6).
    region(7).
    region(8).
    region(9).
    region(10).
    region(11).
    region(12).
    region(13).
    region(14).
    region(15).

    connection(0,1).                %connection exists between these two regions
    connection(0,3).        
    connection(1,2).
    connection(1,8).
    connection(1,7).
    connection(3,4).
    connection(3,5).
    connection(7,9).
    connection(7,5).
    connection(7,8).
    connection(5,6).
    connection(8,10).
    connection(8,11).
    connection(11,12).
    connection(11,13).
    connection(13,15).
    connection(13,14).

    double_link(X,Y) :-
       region(X),
       region(Y),
       ( connection(X,Y) | connection(Y,X) ). %can go from region X to region Y, and vice versa

    path(X,Y) :-
       double_link(X,Y).
    path(X,Y) :-
       double_link(X,Z),
       path(Z,Y).

当我执行时，path(14,0).我得到true. 但是，当我执行 path(0,14). 时，我用完了本地堆栈空间。我不知道怎么可能。谢谢你的帮助！

4

2 回答 2

4

你说：

当我执行时，path(14,0).我得到true.

这是一半的真相！哦，甚至比这还少！事实上，你得到true的不是一次而是多次！

?- path(14,0).
true ;
true ;
true ;
true ;
true ;
true ...

有一种简单的方法可以避免打字;或SPACE一直打字。只需使用目标false。

    ?- 路径（14,0），假
    **循环**

现在，您还可以将此类false目标添加到您的程序中。这样，您就排除了程序的某些部分；如果剩下的部分还在循环，你就知道那里一定有问题。这就是我得到的：

区域（0）：-假。
% ...
区域（12）：-错误。
地区（13）。
地区（14）。
区域（15）：-错误。

连接（0,1）：-假。
% ...
连接（13,15）：-假。
连接（13,14）。

双链接（X，Y）：-
   区域（X），
   区域（Y），
   （连接（X，Y）；连接（Y，X））。

path(X,Y) :- false ,
    double_link(X,Y)。
路径（X，Y）：-
   双链接（X，Z），
   路径（Z，Y），假。

因此，在剩下的部分中，必须解决该循环。它现在应该是不言自明的，不是吗？

于 2014-08-26T15:56:18.253 回答
2

出现问题是因为您可以在迷宫中转圈。例如，在您的迷宫中，您有连接0 - 1 - 7 - 5 - 3 - 0。您没有采取任何措施来确保搜索不会盲目地跟随那些圈子。

通常的方法是向包含已访问区域（最初为空）的路径谓词添加一个参数。X然后，您必须确保您何时前往X不在该列表中的新位置（例如，使用nonmember(X,Visited)）。

于 2014-08-26T14:31:20.770 回答