Loading article…
バックトラッキングは、制約充足問題や列挙問題などの計算問題の解を見つけるためのアルゴリズムの一種で、解の候補を段階的に構築し、候補が有効な解に完成できないと判断した時点で候補を放棄（「バックトラック」）します。[ 1 ]
バックトラッキングの典型的な教科書的な例は、8クイーンパズルです。これは、標準的なチェス盤上に8つのチェスのクイーンを配置し、どのクイーンも他のクイーンを攻撃しないようにするすべての配置を求める問題です。一般的なバックトラッキングのアプローチでは、部分的な候補は、盤の最初のk行にk個のクイーンを配置したもので、すべて異なる行と列に配置されます。互いに攻撃し合う2つのクイーンを含む部分的な解は破棄されます。
バックトラッキングは、「部分的な候補解」という概念が許容され、かつ、それが有効な解に完成できるかどうかを比較的迅速に判定できる問題にのみ適用できます。例えば、順序付けされていないテーブルから特定の値を探す場合には役に立ちません。しかし、適用可能な場合、バックトラッキングは、 1回の判定で多くの候補を排除できるため、すべての完全な候補を総当たりで列挙するよりもはるかに高速になることがよくあります。
バックトラッキングは、クロスワードパズル、言語算術、数独、その他多くのパズルなどの制約充足問題を解決するための重要なツールです。[ 2 ]ナップサック問題やその他の組み合わせ最適化問題の構文解析には、バックトラッキングが最も便利な手法となることがよくあります。[ 3 ]また、プログラミング言語Icon、Planner 、 Prologで使用されるプログラム実行戦略でもあります。
バックトラッキングは、解決すべき問題、部分候補の性質、そしてそれらを完全な候補に拡張する方法を定義する、ユーザーが提供する「ブラックボックス手順」に依存します。したがって、これは特定のアルゴリズムというよりはメタヒューリスティック です。ただし、他の多くのメタヒューリスティックとは異なり、有限の問題に対するすべての解を一定時間内に見つけることが保証されています。
「バックトラック」という用語は、1950年代にアメリカの数学者DHレーマーによって造語されました。 [ 4 ]先駆的な文字列処理言語SNOBOL（1962年）は、組み込みの汎用バックトラッキング機能を提供した最初の言語だったかもしれません。
バックトラッキングアルゴリズムは、部分的な候補の集合を列挙します。これらの候補は、原理的には様々な方法で補完することができ、与えられた問題に対する考えられるすべての解が得られます。補完は、候補拡張の一連のステップによって段階的に行われます。
概念的には、部分候補はツリー構造のノード、すなわち潜在的探索ツリーとして表現される。各部分候補は、単一の拡張ステップで異なる候補の親であり、ツリーの葉はそれ以上拡張できない部分候補である。
バックトラッキングアルゴリズムは、この探索木を根から深さ優先で再帰的に走査します。各ノードcにおいて、アルゴリズムはc が有効な解に完成できるかどうかをチェックします。完成できない場合は、 cを根とするサブツリー全体がスキップ（剪定）されます。そうでない場合は、アルゴリズムは (1) c自体が有効な解であるかどうかをチェックし、有効な場合はそれをユーザーに報告します。(2) cのすべてのサブツリーを再帰的に列挙します。これら 2 つのテストと各ノードの子は、ユーザーが指定した手順によって定義されます。
したがって、アルゴリズムが実際に走査する探索木は、潜在的な探索木の一部にすぎません。アルゴリズムの総コストは、実際の探索木のノード数に、各ノードの取得と処理にかかるコストを乗じた値になります。潜在的な探索木を選択し、枝刈りテストを実装する際には、この点を考慮する必要があります。
バックトラッキングを特定の問題クラスに適用するには、解決すべき問題の特定のインスタンスのデータPと、root、reject、accept、first、next、output の6 つの手続きパラメータを提供する必要があります。これらの手続きは、インスタンスデータP をパラメータとして受け取り、以下の処理を実行する必要があります。
バックトラッキングアルゴリズムは、問題をbacktrack ( P , root ( P )) という呼び出しに還元します。ここで、backtrack は次の再帰的な手順です。
手続きbacktrack(P, c)は、 reject(P, c)ならばreturn、 accept(P, c)ならばoutput(P, c)です。 s ← first(P, c) while s ≠ NULL do backtrack(P, s) s ← next(P, s)
拒否手順は、 cの拡張がPの有効な解ではないことが確実な場合にのみtrueを返すブール値関数である必要があります。手順が明確な結論に達することができない場合は、false を返す必要があります。誤ったtrue の結果は、バックトラック手順が有効な解を見逃す原因となる可能性があります。この手順は、探索ツリー内のcのすべての祖先tに対してreject ( P , t ) がfalse を返したと想定できます。
一方、バックトラッキングアルゴリズムの効率は、reject関数がルートにできるだけ近い候補に対して常にtrueを返すかどうかに依存します。reject関数が常にfalseを返す場合、アルゴリズムはすべての解を見つけますが、それは総当たり探索と同等になります。
受理手続きは、cが問題インスタンスPに対する完全かつ有効な解である場合はtrueを返し、そうでない場合はfalseを返す必要があります。部分候補cとそのツリー内のすべての祖先が拒否テストに合格していると仮定しても構いません。
上記の一般的な擬似コードは、有効な解が常に探索ツリーの葉であるとは想定していません。つまり、Pに対する有効な解がさらに拡張されて他の有効な解が得られる可能性を認めています。
バックトラッキングアルゴリズムでは、firstとnextの手順を使用して、ツリーのノードcの子、つまりcと拡張ステップが 1 つ異なる候補を列挙します。first ( P , c )の呼び出しは、 cの最初の子を何らかの順序で返します。next ( P , s )の呼び出しは、ノードsの次の兄弟を同じ順序で返します。要求された子が存在しない場合、両方の関数は一意の「NULL」候補を返します。
root、first、nextの各関数は、部分候補の集合と潜在的な探索木を定義します。これらの関数は、問題Pのすべての解が木の中に必ず出現し、かつ部分候補が複数回出現しないように選択する必要があります。さらに、効率的かつ効果的な拒否述語を許容する必要があります。
上記の擬似コードは、与えられたインスタンスPの解となるすべての候補に対して出力処理を呼び出します。このアルゴリズムは、最初の解が見つかった後、または指定された数の解が見つかった後、あるいは指定された数の部分候補をテストした後、または指定された量のCPU時間が経過した後に停止するように変更できます。
バックトラッキングを用いてパズルや問題を解決する例としては、以下のようなものがあります。
以下は、制約充足問題にバックトラッキングを用いる例です。
一般的な制約充足問題は、任意の制約（ブール関数）Fを満たす整数のリストx = ( x [1], x [2], …, x [ n ])を見つけることから成ります。各整数は、ある範囲{1, 2, …, m } に属します。
この種の問題の場合、インスタンスデータP は整数mとn、および述語Fになります。この問題に対する典型的なバックトラッキング解法では、部分候補を、 0 からnまでの任意のkに対して整数c = ( c [1], c [2], …, c [k])のリストとして定義し、最初のk 個の変数x [1], x [2], …, x [ k ]に割り当てます。ルート候補は空のリスト () になります。最初の手順と次の手順は次のようになります。
関数first(P, c)は k ← length(c) k = nの場合は NULL を返し、そうでない場合は (c[1], c[2], ..., c[k], 1)を返す
関数next(P, s)は k ← 長さ s[k] = mの場合は NULL を返し、そうでない場合は (s[1], s[2], ..., s[k − 1], 1 + s[k])を返す。
ここで長さ( c )はリストcの要素数です。
呼び出しreject ( P , c )は、制約Fがcのk個の要素から始まるn個の整数のリストでは満たされない場合にtrueを返す必要があります。バックトラッキングを効果的に行うには、少なくとも一部の候補cについては、m n − k n個のタプルをすべて列挙することなく、この状況を検出する方法が必要です。
例えば、Fが複数のブール述語の論理積、F = F [1] ∧ F [2] ∧ … ∧ F [ p ]であり、各F [ i ] が変数x [1]、…、 x [ n ]のごく一部にのみ依存する場合、reject手順は変数x [1]、…、x [ k ]にのみ依存する項F [ i ] を単純にチェックし、それらの項のいずれかがfalse を返す場合にtrueを返すだけで済みます。実際には、reject はx [ k ]に依存する項のみをチェックすればよく、 x [ 1]、…、x [ k − 1]にのみ依存する項は検索ツリーのさらに上位で既にテストされているためです。
拒否が上記のように実装されていると仮定すると、受け入れ（P、c）はcが完全であるかどうか、つまりn個の要素を持っているかどうかだけをチェックすればよい。
一般的には、変数のリストは最も重要なもの（つまり、値の選択肢が最も少ないもの、または後続の選択に大きな影響を与えるもの）から始まるように並べるのが良いでしょう。
また、部分候補を拡張する際に、次の関数が既に割り当てた変数の値に基づいて、どの変数を割り当てるべきかを選択できるようにすることもできる。制約伝播の手法を用いることで、さらなる改善が可能となる。
バックアップ時に使用する最小限の復旧値を保持することに加え、バックトラッキングの実装では、値の変更履歴を記録するために変数トレイルを保持するのが一般的です。効率的な実装では、選択ポイントがない場合、連続する2つの変更の間に変数トレイルエントリを作成しないようにします。これは、バックトラッキングによってすべての変更が単一の操作として消去されるためです。
変数の履歴を記録する代わりに、変数に最後に変更が加えられた時刻のタイムスタンプを保持する方法があります。このタイムスタンプは、選択ポイントのタイムスタンプと比較されます。選択ポイントに関連付けられた時刻が変数のタイムスタンプよりも後であれば、選択ポイントを遡って確認する際に変数を元に戻す必要はありません。なぜなら、変数は選択ポイントが発生する前に変更されているからです。