这个prolog排序程序是否仅仅因为其复杂性而溢出堆栈 - 或者因为它是错误的？

Question

在上一篇文章中,我最终想出了如何编写gprolog程序来检查一个列表是否是另一个列表的排列.据我所知,它有效.

现在,我正在创建一个mysort谓词,它将排列谓词与这个谓词结合起来(据我所知也是如此):

sorted([]).   
sorted([L]) :- !.  
sorted([L|[T|TT]]) :- L @=< T, sorted([T|TT]).

由于我的原始perm谓词设计!为在得到答案后立即终止,我做了一些修改以允许mysort检查可能性.这是mysort,它的特殊性backtrack_perm,与旧的重叠perm(我只是稍作改动backtrack_perm):

perm([],[]).
perm([LH|LT],R) :-
   backtrack_perm([LH|LT],R),
   !.

perm_recurse([],X). 
perm_recurse([LH|LT],R) :-
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X,Y),
   !. 

mysort(L,M) :-
   backtrack_perm(L,M),
   sorted(M),
   !.  

backtrack_perm([],[]).
backtrack_perm([LH|LT],R) :-
   length([LH|LT],A),
   length(R,B),
   A == B,
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X, Y).  

虽然它的组件看起来像上面提到的那样正常,但是mysort在某些输入上会导致堆栈溢出,例如mysort([5,3,2],X).在已经排序的列表中,例如mysort([2,3,5],X),甚至是部分类似的列表mysort([3,2,5],X),跟踪可能很长,但它确实得到了答案.正因为如此 - 并且因为一个较小的完全向后的列表就像[2,1]工作正常 - 我认为问题只是过程本身太空/耗时所有这些排列.

如果没有步进过深地进入较长的痕迹,这将是安全的假设,这样的话？或者Prolog /计算机应该能够毫无问题地处理这个问题,这意味着我需要重新考虑算法？

Answer 1

@Will Ness已经给你一个很好的定义了perm/2.但是让我们来看看你的节目.事实上,你有非常奇怪的行为:有时似乎有效,有时则不行.我们怎样才能缩小范围呢？跟踪似乎不是一种选择,因为您已经体验过自己.

这是一种特殊的调试技术,称为切片.我会通过插入目标来修改你的程序,看看发生了什么false.生成的程序称为故障切片.我将使用查询:

?- mysort([1],[2|_]).
Fatal Error: global stack overflow

显然,具有单个1as元素的列表不能对应于以2.开头的列表.理想情况下,这应该失败.它不可能那么复杂.它可以？

@larsmans已经给了你一个暗示,但我会自己尝试一下.我将在false您的计划中添加以下目标.通过这种方式,某些部分永远不会被调用,它们会被打破.某些谓词根本不会被调用,所以我将不再显示它们:

?- mysort([1],[2|_]).

mysort(L,M) :-
   backtrack_perm(L,M), false,
   sorted(M),
   !.  

backtrack_perm([],[]) :- false.
backtrack_perm([LH|LT],R) :-
   length([LH|LT],A),
   length(R,B), false,
   A == B,
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X, Y).  

从某种意义上讲,这个故障片与您的程序一样糟糕:同样,它不会终止.但它更小.要解决这个问题,你必须在该片段中做一些事情.因为,只要该部分保持不变,问题就会持续存在.

在这种情况下,它的目标length(R,B)是罪魁祸首:变量B首次出现在这里,因此它是未实例化的.而且还R没有实例化.什么是目标的答案length(R, B).试试看!

| ?- length(R, B).

B = 0
R = [] ? ;

B = 1
R = [_] ? ;

B = 2
R = [_,_] ? ;

B = 3
R = [_,_,_] ? ;

B = 4
R = [_,_,_,_] ? ;

B = 5
R = [_,_,_,_,_] ? ...

所以答案无限多.因此,您的程序不会终止.

此问题可以通过更换容易地固定length(R, B), A == B通过length(R, A).

| ?- mysort([9,1,2,3,4,5,6,7,8],L).

L = [1,2,3,4,5,6,7,8,9]

(21841 ms) yes

更多的评论:!你的程序中有红色削减,它们可能会给你带来很多麻烦.然后,执行时间不是那么好:排序9个元素的21秒听起来不是很酷.但请记住,您的描述基本上是这样说的:我想要一种排列,即提升.你不要说更多.鉴于信息十分稀缺,Prolog至少能够找到正确的答案.它甚至可以节省空间.

如何将此程序变为更有效的程序,请参阅此答案.