Prolog间接关系

Question

我刚刚开始学习 Prolog 并面临一个有线问题:

假设有人排两队等待:

left(a,b).
left(c,i).
left(i,j).
right(k,j).

代表这样的线:

line1:a,b  line2: c,i,j,k.

我想要看看这些人中是否有任何人是同一阵营的。我写的内容遵循以下规则:

nextto(X,Y):- left(X,Y);left(Y,X);right(X,Y);right(Y,X).
sameline(X,Y):- nextto(X,Y).
sameline(X,Y):- nextto(X,Z),sameline(Z,Y).

我将人与人之间的“左/右”关系转换为“nextto”关系。 当两个人实际上在同一行时，代码可以正常工作。但如果我尝试:

?- sameline(a,c)

其中“a”和“c”不在同一行。程序进入无限循环，直到耗尽本地堆栈。我假设它一直尝试在“X”和“Y”之间查找变量“Z”，如果找不到，程序将创建另一个“Z”来继续搜索。我见过使用递归调用的典型祖先示例:

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y). 

这是有道理的。但是我的代码与祖先示例有何不同？显然 nextto(a,j) 会返回 false，但为什么循环不会停止？

这是我学习 Prolog 的第二天，所以 Prolog 的高级使用可能没有帮助:(。

谢谢。

Answer 1

如果你跟踪:

?- sameline(a,c).

你会看到它陷入了循环a <-> b由于:

nextto(X,Y):- left(X,Y);left(Y,X);right(X,Y);right(Y,X).

在上面的规则中，您让 next(a,b)和next(b,a)成功，但你只需要一次就能成功，以免陷入循环:

在跟踪中你可以看到:

Redo: (8) sameline(a, c) ? creep    %OK trying to succeed sameline(a,c)
   Call: (9) nextto(a, _884) ? creep

上面继续:

Call: (10) left(a, _884) ? creep
   Exit: (10) left(a, b) ? creep     %Only b succeeds left(a,_)
   Exit: (9) nextto(a, b) ? creep
   Call: (9) sameline(b, c) ? creep  %OK trying to succeed recursively 

同一行(b,c)。

但这最终会调用:

Redo: (9) sameline(b, c) ? creep
   Call: (10) nextto(b, _884) ? creep
   Call: (11) left(b, _884) ? creep
   Fail: (11) left(b, _884) ? creep
   Redo: (10) nextto(b, _884) ? creep
   Call: (11) left(_882, b) ? creep
   Exit: (11) left(a, b) ? creep
   Exit: (10) nextto(b, a) ? creep
   Call: (10) sameline(a, c) ? creep   % Same thing we began due to cycle

为了解决这个问题，如果我正确理解你想要做什么，你应该定义:

nextto(X,Y):- left(X,Y);right(Y,X).
sameline(X,Y):- nextto(X,Y).
sameline(X,Y):- nextto(X,Z),sameline(Z,Y).

nextto/2 的定义强制遵循一条路径而不陷入循环。

示例:

?- sameline(c,X).
X = i ;
X = j ;
X = k ;
false.

?- sameline(c,i).
true ;
false.

?- sameline(a,c).
false.

---

编辑

如果您希望 nextto/2 处理循环，解决该问题的一种方法是保留您访问过的内容的列表:

sameline(X,Y):- sameline(X,Y,[X]).

nextto(X,Y):- left(X,Y);left(Y,X);right(X,Y);right(Y,X).
sameline(X,Y,_):- nextto(X,Y).
sameline(X,Y,L):- nextto(X,Z),\+member(Z,L),sameline(Z,Y,[Z|L]).