0

Prolog での次の BubbleSort アルゴリズムの実装がどのように機能するかについて、私は疑問を持っています。

BubbleSortアルゴリズムがどのように機能するかは非常に明確であるため、私の疑いはPrologの1次ロジックと宣言的解釈にのみ関連しています。

これは私のコードです:

bubbleSort(List, SortedList) :- swap(List, List1),
                                !,
                                bubbleSort(List1, SortedList).

bubbleSort(SortedList, SortedList).

/* swap predicate swap the two element if X come after Y in lexicographical order */
swap([X,Y|Tail], [Y,X|Tail]) :- X @> Y.

/* If it is not true that X come after Y in lexicographical order let the head in its
   original position and call the swap predicate on the sublist */ 
swap([Z|Tail], [Z|Tail1]) :- swap(Tail, Tail1).

したがって、このプログラムの宣言的解釈については疑問があります。

プログラムのコアは、最終的に隣接する要素のスワップが実行される List のスキャンを実行するbubbleSort/2述語です。

したがって、次の場合、 swap/2述語は手続き型のように機能します。

1) サブリストの最初の要素 (X) がサブリストの 2 番目の要素 (Y) の後に辞書順で続く場合、それは適切ではないため、スワップを実行します。

2) それ以外の場合、X と Y は正しい順序であり、サブリストTailで te swap を実行しようとします

たとえば、次のクエリを実行するとします。

[trace]  ?- bubbleSort([3,2,1], Sorted).

私は得る：

Call: (7) bubbleSort([3, 2, 1], _G399) ? creep
Call: (8) swap([3, 2, 1], _G478) ? creep
Call: (9) 3@>2 ? creep
Exit: (9) 3@>2 ? creep
Exit: (8) swap([3, 2, 1], [2, 3, 1]) ? creep
Call: (8) bubbleSort([2, 3, 1], _G399) ? creep

ここでは、元のリストにあるbubbleSort/2の最初のバージョンを呼び出します。TRUE になるには、最初のバージョンのswap/2述語を呼び出して、リストの最初の 2 つの要素が互いに辞書順になっていないかどうかを確認します。この事実は TRUE であるため、これらの要素を交換します。swap/2述語が検証されたので、バックトラックして戻ってきて ( bubbleSort/2 を満たすために) bubbleSort2を再度呼び出して、順序付けする元のリストがスワップ後のリスト (最初と 2 番目の要素が含まれるリスト) であることを伝えます。入れ替わった）

再度、bubbleSort を呼び出すと、次のようになります。

Call: (8) bubbleSort([2, 3, 1], _G399) ? creep
Call: (9) swap([2, 3, 1], _G484) ? creep
Call: (10) 2@>3 ? creep
Fail: (10) 2@>3 ? creep
Redo: (9) swap([2, 3, 1], _G484) ? creep
Call: (10) swap([3, 1], _G480) ? creep
Call: (11) 3@>1 ? creep
Exit: (11) 3@>1 ? creep
Exit: (10) swap([3, 1], [1, 3]) ? creep
Exit: (9) swap([2, 3, 1], [2, 1, 3]) ? creep

そのため、リスト [2,3,1] でswap/2を満たそうとしますが、最初の 2 つの要素が互いに辞書順になっていないということは正しくないため、swap/2述語の最初のバージョンは失敗します。サブリスト **[3,1] で単純にswap/2を呼び出す 2 番目のバージョンを使用します。ここで、3 が 1 の後に続かないのは true であるため、スワップして [1,3] リストを取得します。

ここで最初の疑問があります。このサブリストを ([3,1] から [1,3] に) 交換した後、次の行で [2, 1, 3] というリストを取得します。

Exit: (9) swap([2, 3, 1], [2, 1, 3]) ? creep

なぜ？これは、swap(Tail, Tail1) 述語を満たした後であるためです。

swap([Z|Tail], [Z|Tail1]) :- swap(Tail, Tail1).

Tail1が[1,3]であるため、Z は古いヘッド 2 であり、[Z|Tail1] は[2,1,3]ですか?

ただし、リストの最後にある「より大きな」要素を取得したのは、バブルソートアルゴリズムの最初のスキャンを終了することです。

実行は同じ方法で続行されますが、次のプログラム実行の終了について疑問があります。

   Redo: (10) bubbleSort([1, 2, 3], _G399) ? creep
   Exit: (10) bubbleSort([1, 2, 3], [1, 2, 3]) ? creep
   Exit: (9) bubbleSort([2, 1, 3], [1, 2, 3]) ? creep
   Exit: (8) bubbleSort([2, 3, 1], [1, 2, 3]) ? creep
   Exit: (7) bubbleSort([3, 2, 1], [1, 2, 3]) ? creep
Sorted = [1, 2, 3].

そのため、最後に次のようにして、順序付けられたリストのbubbleSort/2述語を呼び出します。

 Redo: (10) bubbleSort([1, 2, 3], _G399) ? creep

[1,2,3] はList1です。

これで、 bubbleSort/2述語の2 番目のバージョンになりました。

bubbleSort(SortedList, SortedList).

ここで、ソートするリストとソートされたリストは同じです (つまり、元のリストが完全にソートされていることを意味します)。

それで、これは何ですか？検証されると、プログラムの実行を終了する必要があると言う基本的なケースは?

したがって、バックトラックを実行して、以前のすべてのbubbleSort/2が検証されたと言って、最初のbubbleSort/2呼び出しに到達し、これが検証済みであると言い、 [1,2,3] リストで並べ替えられたと言う

私の推論は正しいですか？これのより宣言的な解釈はありますか？

4

1 に答える 1

3

このアルゴリズムを理解するための鍵は、リストがソートされているときに swap/2が失敗するという事実だと思います-空のリストには一致しません。

ここから、2 番目の bubbleSort/2 ルールが必要になります。

于 2013-04-25T10:40:04.000 に答える