3

我是一个新的 Prolog 开发人员，正在尝试让合并排序工作。查询

mergesort([2,1],T).

将产生

T=[1,2];
T=[1,2];
T=[1,2];
...

因此，尽管它似乎“正确”对序列进行了排序，但它并没有停止

另一方面，如果我有一个查询，例如

mergesort([2,1],[2,1])

它进入一个无限循环。我想知道为什么会这样？

append([H|T],LISTB,[H|LISTC]):-
    append(T,LISTB,LISTC).

split(LIST,L1,L2):-
    length(LIST,LENGTH),
    M is div(LENGTH,2),
    append(L1,L2,LIST),
    length(L1,L1LENGTH),
    (L1LENGTH =:= M).

merge(A,[],A).
merge([],B,B).
merge([A|TA],[B|TB],[A|MERGED]) :-
    A =< B,
    merge(TA,[B|TB],MERGED).
merge([A|TA],[B|TB],[B|MERGED]) :-
    B < A,
    merge([A|TA],TB,MERGED).

mergesort([],[]).
mergesort([X],[X]).
mergesort(LIST,OLIST):-
    split(LIST,L1,L2),
    mergesort(L1,OLIST1),
    mergesort(L2,OLIST2),
    merge(OLIST1,OLIST2,OLIST).
4

2 回答 2

6

（append([], L, L).失踪）

首先，减少输入的大小！您遇到的问题[2,1]已经可以观察到[2]甚至[]！

?- mergesort([],T).
   T = []
;  T = []
;  T = []
;  T = []
...

所以问题似乎是程序没有终止。或者它可能在十个答案后停止？有一种方法可以更好地测试：

?- 归并排序（[]，T），假。
*循环*

如果我这样做了，我会在你的程序中添加更多目标，以便生成的程序仍然循环：

追加（[]，L，L）。
append([H|T],LISTB,[H|LISTC]):- false ,
     append(T,LISTB,LISTC)。

拆分（列表，L1，L2）：-列表 = []，
    长度（列表，长度），
    M 是 div(LENGTH,2),
    附加（L1，L2，列表），
    长度（L1，L1LENGTH），
    （L1LENGTH =:= M）。

合并排序（[]，[]）：-假。
合并排序（[X]，[X]）：-假。
合并排序（LIST，OLIST）：- LIST = []，
    拆分（列表，L1，L2），L1 = []，L2 = []，
    合并排序（L1，OLIST1），假，
    合并排序（L2，OLIST2），
    合并（OLIST1，OLIST2，OLIST）。

我添加了目标false，所有目标都终止了，因此要么改进终止，要么保持原样。这个产生的程序片段被称为。L = []

因为这个程序循环，你的原始程序也会循环。因此，可见部分的某处一定有错误。mergesort/2递归规则适用于空列表真的有意义吗？

（（除此之外，拆分目前的效率非常低。））

于 2018-06-11T06:33:10.620 回答
1

我确定这是 hacky 解决方案，但它是一个解决方案

mergesort(LIST,OLIST):-
    split(LIST,L1,L2),
    mergesort(L1,OLIST1),
    mergesort(L2,OLIST2),
    merge(OLIST1,OLIST2,OLIST),
    !.
于 2018-06-11T03:39:44.827 回答