Prolog:毕达哥拉斯三重奏

Question

我有这个代码使用一个上限变量N,它应该终止为毕达哥拉斯三元组的X和Y. 然而它只有在达到上限时才会冻结.不知道如何使用切割来阻止回溯.代码是:

is_int(0).
is_int(X) :- is_int(Y), X is Y+1.
minus(S,S,0).
minus(S,D1,D2) :- S>0, S1 is S-1, minus(S1,D1,D3), D2 is D3+1.

pythag(X,Y,Z,N) :- int_triple(X,Y,Z,N), Z*Z =:= X*X + Y*Y.

int_triple(X,Y,Z,N) :- is_int(S), minus(S,X,S1), X>0, X<N,
                                  minus(S1,Y,Z), Y>0, Y<N.

将被称为,例如,

?- pythag(X,Y,Z,20).

Answer 1

首先,让我们测试您的解决方案:

?- pythag(X,Y,Z,20).
X = 4,
Y = 3,
Z = 5 ;
X = 3,
Y = 4,
Z = 5 ;
X = 8,
Y = 6,
Z = 10 ;
X = 6,
Y = 8,
Z = 10 ;
X = 12,
Y = 5,
Z = 13 ;
X = 5,
Y = 12,
Z = 13 ;
X = 12,
Y = 9,
Z = 15 ;
X = 9,
Y = 12,
Z = 15 ;
X = 15,
Y = 8,
Z = 17 ;
X = 8,
Y = 15,
Z = 17 ;
X = 16,
Y = 12,
Z = 20 ;
X = 12,
Y = 16,
Z = 20 ...

看起来很完美!所有答案都是正确的答案!......包括最后一个解决方案.之后,你的程序循环.

在我们尝试确定问题之前,请坚持一下:您必须非常耐心地通过12(即:12)答案才能找到该循环.你认为这种方法对更大的案例也适用吗？在你放弃之前,你愿意看多少答案？有没有更简单的方法来找出问题？

这里有一个有趣的观察结果:找到的答案(几乎)与循环程序无关!那就是:通过查看答案,你得到(经常 - 就像在这种情况下)没有关于循环的实际原因的线索!那么为什么不关闭所有答案并专注于相关部分!事实上,我们可以这样做:

?- pythag(X,Y,Z,20), false.
** LOOP **

现在,由于目标,所有答案都已删除false.剩下的只是最终结果:终止,或非终止,或一些错误.没有其他的.这应该有助于我们对终止一点点的观察 - 没有更多的盲目回答在屏幕上滚动.请注意,这并不能解决一般问题.毕竟,有长的,我们愿意等待？1s？1米？

通过查看相关的故障切片可以最好地理解非终止的实际原因.这是程序的一个片段,其非终止意味着整个程序没有终止.有关详细信息,请参阅此答案.以下是查询程序的相关故障切片pythag(X,Y,Z,20), false:

pythag(X,Y,Z,N) :-
   int_triple(X,Y,Z,N), false,
   Z*Z =:= X*X + Y*Y.

int_triple(X,Y,Z,N) :-
   is_int(S), false,
   minus(S,X,S1), X>0, X<N,
   minus(S1,Y,Z), Y>0, Y<N.

is_int(0) :- false.
is_int(X) :-
   is_int(Y), false,
   X is Y+1.

请注意,您的程序还剩下很多东西.例如,实际的等式消失了(这或多或少是逻辑部分......).不过,这个片段是相关的.只要你不改变该片段中的某些内容,问题就会持续存在!这是一个纯粹的单调程序,因为这个...

这是我的首选解决方案:它使用length/2和between/3两个经常支持Prolog序言的谓词.

pythag2(X,Y,Z,N) :-
   length(_, N),
   between(1,N,X),
   between(1,N,Y),
   between(1,N,Z),
   Z*Z =:= X*X + Y*Y.