0

バックトラッキングアルゴリズムを開始するには、i=0に対して次の擬似コードを呼び出すことができます。X[1..0]は空のタプルを表します。

ALGORITHM Backtrack(X[1..i])
   //Gives a template of a generic backtracking algorithm
   //Input: X[1..i] specifies first i promising components of a solution.
   //Output: Alll the tuples representing the problem's solutions
   If X[1..i] is a solution write X[1..i]
   else
     for each element x belongs to Si+1 consistent with X[1..i] and constraints do
        X[i+1] <- x
        Backtrack(X[1..i+1])

上記の論理を理解するのに苦労しています。私はステップスルーで4クイーンの問題を理解しようとしましたが、そうではありませんでした。4クイーンの問題のステップで上記のロジックを理解するためにあなたの助けをお願いします。

ありがとう！

4

1 に答える 1

1

このPDFファイル（25ページ）をご覧ください。バックトラックを使用した4つのクイーンソリューションに関する画像を使用して、説明をステップ実行するステップがあります。

http://ce.sharif.edu/courses/90-91/2/ce417-1/resources/root/Lectures/Chapter-6.pdf

簡単に言えば：

アルゴリズムは、すべての制約と一致する配列Xの各要素の割り当てを見つけようとしています。

バックトラッキングでこれを行うには、再帰関数を使用します。各ステップで、現在の変数（ドメインセットS i + 1 ）で使用可能なすべての値を調べ、制約と一致している場合は、解に到達するまで再帰的に次の変数に進みます。

于 2012-05-04T12:56:23.657 に答える