共通するパターン

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

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

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

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

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


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