Anany Levtinによるアルゴリズムの設計と分析の紹介で、バックトラッキングアルゴリズム設計手法を読んでいます。
バックトラッキング アルゴリズムの一般的な定義を理解し、それを 4 クイーン問題にマッピングするのに苦労しています。
より一般的な観点からのバックトラッキング アルゴリズムの設計手法については、ほとんどのバックトラッキング アルゴリズムは次の説明に適合します。
バックトラッキング アルゴリズムの出力は、n 個のタプル (x1、x2、x3、...、xn) と考えることができます。ここで、各座標 xi は、ある有限の線形順序集合 Si の要素です。たとえば、n-queens 問題の場合、各 Si は 1 から n までの整数のセットです。タプルは、いくつかの追加の制約 (たとえば、n-queens 問題における非攻撃要件) を満たす必要がある場合があります。
たとえば、4 クイーンの問題では、各 Si は {1, 2, 3, 4} に設定されます。
バックトラッキング アルゴリズムは、明示的または暗黙的に状態空間ツリーを生成します。そのノードは、アルゴリズムの以前のアクションによって定義された最初の "i" 座標を使用して、部分的に構築されたタプルを表します。そのようなタプル (x1, x2, x3,..xi) が解ではない場合、アルゴリズムは (x1, x2, x3...xi) の値と一致する Si+1 の次の要素を見つけ、制約の問題を解決し、(i+1) 番目の座標としてタプルに追加します。そのような要素が存在しない場合、アルゴリズムはバックトラックして xi の次の値を検討します。
上記のテキストに関する私の質問は
「バックトラッキングアルゴリズムは、明示的または暗黙的に状態空間ツリーを生成し、そのノードは、アルゴリズムの以前のアクションによって定義された最初の「i」座標を持つ部分的に構築されたタプルを表します。そのようなタプル(x1 , x2, x3,.. xi) が解ではない場合、アルゴリズムは (x1, x2, x3...xi) の値と問題の制約と一致する Si+1 の次の要素を見つけ、それをに追加しますその (i+1) 番目の座標としてのタプル。」?
具体的に言うと、作者が Si+1 の次の要素を見つけるアルゴリズムとはどういう意味ですか?
上記のステートメントを 4 クイーンの問題で説明してください。
要素が存在しない場合、アルゴリズムは xi の次の値を検討するために後戻りしますか? この文を 4 クイーン問題で説明してください。
ありがとう！