请在Bubblesort Prolog程序中说明削减幅度吗？ [英] Please explain the cut in the Bubblesort Prolog program?

问题描述

我目前正在研究Bratko Prolog一书，并且正在研究冒泡排序程序。我似乎无法弄清楚为什么需要削减（！）。假设没有晋级机会，Prolog会退后一步，怎么可能找到不好的答案？因为如果我不做任何准备，Prolog首先会给我正确的答案，然后还会给出其他错误的答案。

如我所见，如何交换返回一个非排序列表？以及未排序的列表怎么可能达到目标 bubblesort（排序，排序）。

除非当然，第一个列表也正在更改...无法理解。

Prolog BubbleSort程序：

  gt（X，Y）：-X> Y. 
 
 bubbleort（List，Sorted）：-
 swap（List，List1），！，％在List中有用的交换吗？ 
 bubbleort（List1，Sorted）。 
 bubbleort（排序，排序）。 ％否则，列表已经排序
 
 swap（[X，Y | Rest]，[Y，X | Rest]）：-％交换前两个元素
 gt（X，Y）。 
 swap（[Z | Rest]，[Z | Rest1]）：-％尾部
 swap（Rest，Rest1）中的元素交换。 
  

不删节就给我：

 ？-bubbleort（[5,7,3,6,8,9,2,6]，已排序）。 
 
排序= [2、3、5、6、6、7、8、9]； 
 
排序= [2，3，5，6，7，6，6，8，9]; 
 
排序= [2、3、5、6、7、8、6、9]； 
 
排序= [2、3、5、6、7、8、9、6]; 
  

我认为我以某种方式得到了它，但是我不确定。可能是在某个时刻，它在 swap（List，List1）上回溯到第二个冒泡排序谓词并达到了目标，这意味着两个Sorted是

用英语，这是否意味着冒泡排序需要继续进行交换，直到不再可能进行交换，然后才需要终止？还是这意味着每次成功完成交换后，都没有回溯成功的经验？

解决方案

使目标 swap（List，List1）失败的几种可能性。 List 是长度为0或1的列表；或者它不包含两个紧随其后的元素，且第二个元素小于第一个元素。

剪切位置的放置方式是，它们都剪切 swap / 2 和 bubblesort / 2 的替代方案。

这是一个很好的示例，在这里深切（切入 swap / 2 ）仍然有效有点不错。但是，这种情况很少见。大多数时候，削减幅度太大。如果已经给出了第二个参数，则此类程序中的绝大多数使用起来非常脆弱，甚至更难使用。他们通常不是坚定不移。

啊，我差点没想到：即使在这个程序中，我们也有 bubblesort（ nonlist，L）成功，或 bubblesort（[1 | nonlist]，L）可能不希望这样做，并导致微妙的编程错误。 / p>

该程序不能呈现理想的逻辑编程风格还有另一个原因： bubblesort / 2 单独阅读时说：一切都是排序列表`。要理解这一点，我们必须同时阅读两个规则，并将其范围缩小到所有内容，但... 。

用英语，这是否意味着冒泡排序需要继续进行交换，直到不可能再进行交换，然后才需要终止？还是说每次成功完成一次交换，都没有回溯成功的地方？

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

非常不直观的细节（不是剪切所特有的）是，除了数字以外，该程序还可以成功执行 bubblesort（[1,1 + 1]，L）这样的表达式再次可能会导致细微的差异。

I'm currently working trough the Bratko Prolog book and I am looking at the bubble-sort Program. I can't seem to figure out why the cut(!) is necessary. Say the cut isn't there, and Prolog would backtrack, how could it possibly find bad answers? Because if I leave the cut out of it, Prolog begins by giving me the correct answer but then also gives alternative bad answers.

As I see it, how can swap ever return a non sorted list? And how is it possible that a non sorted list ever hits the goal bubblesort(Sorted, Sorted).

Unless of course the first List is also being changed... Can't get my head around it.

Prolog BubbleSort program:

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).

Leaving the cut of out it gives me:

?- 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] ;

I think that somehow I get it, but I am not sure. Could it be that at a certain moment, it backtracks over swap(List, List1) going to the second bubble-sort predicate and hitting the goal, meaning the two lists Sorted are equal?

In English, does this mean that bubble-sort needs to continue doing swaps until no more swaps are possible, but then needs to terminate? Or does it mean that every-time a successful swap has been done, there's no use backtracking over that success?

解决方案

There are several possibilities to make the goal swap(List, List1) fail. Either List is a list of length 0 or 1 ; or it does not contain two immediately succeeding elements where the second is smaller than the first.

The cut is placed in such a manner that it both cuts swap/2 and the alternative of bubblesort/2.

This is a good example, where a "deep cut" (cutting deep into swap/2) still works somewhat nicely. However, such situations are very rare. Most of the time, the cut cuts too much. The largest majority of such programs is very brittle to use, even more so, if the second argument is given already. They are often not steadfast.

Ah, I almost missed it: Even in this program, we have bubblesort(nonlist,L) succeeding, or bubblesort([1|nonlist],L) which probably is not intended and leads to subtle programming errors.

There is also another reason why this program does not present the ideal logic programming style: The second rule of bubblesort/2 when read alone says: Everything is a sorted list`. To understand this, we have to read both rules at the same time and narrow it down to Everything but ....

In English, does this mean that bubble-sort needs to continue doing swaps until no more swaps are possible, but then needs to terminate? Or does it mean that every-time a successful swap has been done, there's no use backtracking over that success?

It is the first procedural meaning that applies here. And certainly, backtracking over the success to the second clause of bubblesort/2 would be an error.

A further quite unintuitive detail which is not specific to the cut, is that in addition to numbers, the program also succeeds for expressions like bubblesort([1,1+1],L) which again might lead to subtle differences.

这篇关于请在Bubblesort Prolog程序中说明削减幅度吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！