Prolog

Question

我正在查看 this 问题，其中我们在 Prolog 中创建一个谓词，它在有向图中找到两个节点 ("metro stations") 之间的路径。原代码建议如下

path(Start, Dest, [[Start,Dest]]) :- connected(Start, Dest).
path(Start, Dest, [[Start, Waypoint]|Path]) :- dif(Dest, Waypoint), 
    connected(Start, Waypoint), path(Waypoint, Dest, Path).

但是，为了处理循环并消除包含它们的列表，我尝试沿着递归存储我已经停止的站点，并检查我没有重复它们中的任何一个。这是我想出的代码（请注意，我没有列出列表，而是列出了电台本身）

alldifferent(_,[]).
alldifferent(X,[L|Ls]) :- dif(X,L), alldifferent(X,Ls).

pathaux(Start, Dest, [Start,Dest],Q) :- connected(Start, Dest), alldifferent(Start,Q).
pathaux(Start, Dest, [Start, Waypoint|Path],Q) :- dif(Dest, Waypoint),
    connected(Start, Waypoint), 
    pathaux(Waypoint, Dest, Path, [Start|Q]), alldifferent(Start,Q).

path(X,Y,Z) :- pathaux(X,Y,Z,[]).

但是，当我添加创建循环的规则时

connected(ataba,naguib).
connected(naguib,sadat).
connected(sadat,opera).
connected(opera,dokki).
connected(opera,ataba). //Note this one

我得到了一个无限递归！怎么会？以及如何解决这个问题？

Answer 1

how come?

首先考虑一下你原程序non-termination的原因：


<s>path(Start, Dest, [[Start,Dest]]) :- <b>false</b>, connected(Start, Dest)</s>.
path(Start, Dest, [[Start, Waypoint]|Path]) :-
   dif(Dest, Waypoint), 
   connected(Start, Waypoint),
   path(Waypoint, Dest, Path), <b>false</b>.

仅此片段就负责 non-termination。如果这没有终止，您的原始程序也会终止。

现在，转到您的其他程序。顺便说一句，您对 alldifferent/2 的定义通常写为 maplist(dif(X), Xs).


<s>pathaux(Start, Dest, [Start,Dest],Q) :- <b>false</b>, connected(Start, Dest), alldifferent(Start,Q)</s>.
pathaux(Start, Dest, [Start, Waypoint|Path],Q) :-
   dif(Dest, Waypoint),
   connected(Start, Waypoint), 
   pathaux(Waypoint, Dest, Path, [Start|Q]), <b>false</b>,
   <s>alldifferent(Start,Q)</s>.

path(X,Y,Z) :- pathaux(X,Y,Z,[]).

你发现不同了吗？列表有点不同，还有一个辅助参数，但是在片段中，没有人使用这个参数。所以大致相同。因此：

这个新定义与您原来的程序一样糟糕（或更糟）！

最通用的解决方案是 here. See failure-slice 有关此技术的更多信息，以定位 non-termination 的实际原因。

Prolog - 检测有向图中连接节点的谓词

Prolog - Predicate To Detect Connected Nodes In a Directed Graph

transitive-closure