共通するパターン

バックトラッキングを使ったアルゴリズムはどれも、特定の制約を満たす再帰的に定義された構造の構築を目標として決断の列 (decision sequence) を作っていきます。目標となる構造そのものが求める決断の列であることもありますが、常にそうだというわけではありません。これまでの例でいうと:

• \(n\) クイーン問題では、目標は各列におけるクイーンの配置の列であり、どの二つのクイーンもお互いを攻撃できてはいけないという制約がありました。アルゴリズムは各列について、クイーンをどこに置くかを決断します。

• ゲーム木の問題では、目標は合法な手の列であり、選択する手はプレイヤーにとって良いものでなければならないという制約がありました。アルゴリズムは各ゲームの状態について、良い手がどれであるかを決断します。

• 部分和の問題では、目標は入力要素の部分列であり、和が特定の値にならなくてはならないという制約がありました。アルゴリズムは各入力要素について、その要素を出力の配列に入れるかどうかを決断します。

(部分和の問題 "\(\textsc{SubsetSum}\)" の目標が部分集合 (subset) ではなく列 (sequence) を求めることなのはどうしてでしょうか？ これは意図的にこうしたのでした。入力の集合が (実装の詳細が不明なデータ構造ではなくて) 配列で与えられると再帰的アルゴリズムの説明と解析が簡単になるのでそうしたというだけのことです)

バックトラッキングを使ったアルゴリズムの再帰呼び出しでは、過去の決断と矛盾しないちょうど一つの決断をする必要があります。そのため再帰呼び出しの引数には未処理の入力データだけではなくて、これまでの決断の結果をわかりやすくまとめたデータも含まれます。これまでの例でいうと:

• \(n\) クイーン問題では、空の列の数だけではなくてこれまでに配置されたクイーンの位置もアルゴリズムに渡す必要がありました。この問題では、面白くないのですが、これまでの決断を完全な形で覚えなければなりません。

• ゲーム木の問題では、現在のゲームの状態と次に手を打つプレイヤーをアルゴリズムに渡すだけで済みました。あるゲームの状態からどちらのプレイヤーが勝つかはそれまでのプレイヤーの打った手に依存していないために、それまでの決断を覚えておく必要は全くありません¹。

• 部分和の問題では、アルゴリズムの入力は残っている整数と残りの和の値二つでした。この残りの和の値は元々の問題で目標となっていた和の値からこれまでに選ばれた要素の和を引いたものです。実際にどの要素が選ばれたかは重要ではありませんでした。

バックトラッキングを使ったアルゴリズムを設計するときには、アルゴリズムの途中で必要となるそれまでの決断についての情報が何かを最初に明らかにしておく必要があります。この情報が自明でない場合には、アルゴリズムが解こうとしているよりも一般的な問題を解かなければなりません。この種類の一般化はこれまでに出てきています: ソートされていない配列の中央値を線形時間で見つけるときには、任意の \(k\) に対して \(k\) 番目に小さい要素を見つけるアルゴリズムを考える必要がありました。

解くべき再帰的な問題を特定したら、最後にはその問題を再帰的な総当たりで解きます。つまり、次の決断についての選択肢のうちこれまでの決断と矛盾しないものを全て試し、残りは再帰の妖精に任せます。この部分に賢さはありません。 "明らかに" 馬鹿げた選択肢を飛ばすということはせず、全て試します。このアルゴリズムの高速化は後で触れます。

1. この独立性の条件を満たさないゲームはたくさんあります。例えば一般的なチェスとチェッカーのルールでは同じ盤面が三回続いた場合には引き分けとしてもよいことになっており、中国式の囲碁ではそれまでの盤面を繰り返すような手を禁止しています。このようなゲームについては、ゲームの状態に現在の盤面だけではなくそれまでの全ての打ち手の記録が含まれます。^[return]