prolog - Bubblesort Prolog プログラムのカットについて説明してください。

Question

私は現在、Bratko Prolog の本に取り組んでおり、バブルソート プログラムを見ています。なぜ cut( !) が必要なのか理解できないようです。カットがそこになく、Prolog がバックトラックするとしたら、どうして悪い答えを見つけることができるでしょうか? 切り抜きをすると、Prolog は最初に正しい答えを返しますが、代わりに間違った答えも返すからです。

私が見ているように、どのようにしてスワップがソートされていないリストを返すことができますか? そして、ソートされていないリストがゴールに到達する可能性はありますかbubblesort(Sorted, Sorted)。

もちろん、最初のリストも変更されている場合を除きます...それを理解することはできません。

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)、2 番目のバブル ソート述語に移動してゴールに到達することをバックトラックして、ソートされた 2 つのリストが等しいのではないでしょうか?

英語では、これはバブルソートがスワップを実行できなくなるまでスワップを続行する必要があるが、その後終了する必要があるという意味ですか? それとも、スワップが成功するたびに、その成功を後戻りしても意味がないということですか?