1

我目前正在阅读 Bratko Prolog 书，并且正在研究冒泡排序程序。我似乎无法弄清楚为什么 cut( !) 是必要的。假设剪辑不存在，Prolog 会回溯，它怎么可能找到错误的答案？因为如果我把它删掉，Prolog 会首先给我正确的答案，然后也会给出替代的错误答案。

如我所见，交换如何返回未排序的列表？一个未排序的列表怎么可能达到目标bubblesort(Sorted, Sorted)。

当然，除非第一个 List 也被更改......我无法理解它。

Prolog BubbleSort 程序：

gt(X,Y) :- X > Y.

bubblesort(List, Sorted) :-
  swap(List, List1), !,           % A useful swap in List?
  bubblesort(List1, Sorted).
bubblesort(Sorted, Sorted).       % Otherwise list is already sorted

swap([X,Y|Rest], [Y,X|Rest]) :-   % Swap first two elements
  gt(X,Y).
swap([Z|Rest], [Z|Rest1]) :-      % Swap elements in tail
  swap(Rest, Rest1).

离开它给了我：

?- bubblesort([5,7,3,6,8,9,2,6], Sorted).

Sorted = [2, 3, 5, 6, 6, 7, 8, 9] ;

Sorted = [2, 3, 5, 6, 7, 6, 8, 9] ;

Sorted = [2, 3, 5, 6, 7, 8, 6, 9] ;

Sorted = [2, 3, 5, 6, 7, 8, 9, 6] ;

我想不知何故我明白了，但我不确定。难道是在某个时刻，它回溯swap(List, List1)到第二个冒泡排序谓词并达到目标，这意味着两个列表排序是相等的？

用英语来说，这是否意味着冒泡排序需要继续进行交换，直到无法再进行交换，然后才需要终止？或者这是否意味着每次成功进行交换时，回溯该成功是没有用的？

4

2 回答 2

5

有几种可能使目标swap(List, List1)失败。要么List是长度为 0 或 1 的列表；或者它不包含两个紧随其后的元素，其中第二个小于第一个。

剪切的放置方式使其既剪切swap/2又替代bubblesort/2。

这是一个很好的例子，“深切”（切入swap/2）仍然可以很好地工作。但是，这种情况非常罕见。大多数时候，削减太多。大多数此类程序使用起来非常脆弱，如果已经给出了第二个参数，则更是如此。他们往往不坚定。

啊，我差点错过了：即使在这个程序中，我们也bubblesort(nonlist,L)成功了，或者bubblesort([1|nonlist],L)可能不是故意的，导致细微的编程错误。

这个程序没有呈现理想的逻辑编程风格还有另一个原因：bubblesort/2单独阅读时的第二条规则说：一切都是排序列表`。要理解这一点，我们必须同时阅读这两个规则并将其缩小到Everything but ...。

用英语来说，这是否意味着冒泡排序需要继续进行交换，直到无法再进行交换，然后才需要终止？或者这是否意味着每次成功进行交换时，回溯该成功是没有用的？

这是适用于此的第一个程序含义。当然，回溯到第二个子句的成功bubblesort/2将是一个错误。

另一个并非特定于剪辑的非常不直观的细节是，除了数字之外，该程序还成功地处理了类似的表达式bubblesort([1,1+1],L)，这又可能导致细微的差异。

于 2013-11-19T19:50:55.970 回答
2

我只想补充一点，if-then-else是一种比!/0表达意图更合适的语言结构（我知道你在这里不是!/0自己选择的）：

bubblesort(List0, List) :-
        (   swap(List0, List1) ->
            bubblesort(List1, List)
        ;   List0 = List
        ).

您也可以更改->为*->以查看替代解决方案swap/2，即，如果您将其更改为：

bubblesort(List0, List) :-
        (   swap(List0, List1) *->
            bubblesort(List1, List)
        ;   List0 = List
        ).

然后你得到例如：

?- bubblesort([5,7,3,6,8,9,2,6], Ascending).
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] ;
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] ;
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] .

如您所见，正如您已经预料的那样，所有这些列表都是非递减的。

于 2013-11-19T22:54:31.887 回答