バックトラッキング

バックトラッキング （backtracking）は、制約充足問題の解を探索する戦略の一種で、力まかせ探索を改良したもの。「バックトラック」という用語は、アメリカの数学者デリック・ヘンリー・リーマーが1950年代に作った造語である。

解説

制約充足問題は完全な解の存在する問題であり、要素の順序は問題とはならない。一連の変数が与えられ、指定された制約を満足するようにそれらに値を設定しなければならない。バックトラッキングでは、変数の値の組み合わせを試行錯誤して解を探す。バックトラッキングの効果は部分的組み合わせを排除する実装にあり、それによって実行時間を短縮する。

バックトラッキングは組み合わせ最適化と密接に関連している。

実装

バックトラッキングのアルゴリズムは、単に正しい解を得るまで可能な組み合わせを試していくだけであり、一種の深さ優先探索である。探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。その組み合わせを試しても解でなかった場合、さらに探索木を戻り、新たな組み合わせを試す。探索木を全部サーチしたとき、探索は失敗して終了する。

バックトラックは一般に再帰呼び出し関数として実装される。一回の呼び出しでは1つの変数に値を設定（束縛）して、それ以外を自由な変数として再帰的に呼び出す。バックトラッキングは深さ優先探索に似ているが、メモリ使用量が少なく、現在の解の状態を1つだけ保持し、更新していくだけである。

探索を高速化するため、値を選択して再帰呼び出しをする前に、アルゴリズムはその値を矛盾する未設定領域から削除する（前方チェック）か、全制約をチェックしてその新たな値による影響を求める（制約伝播）。これは、0/1 ナップサック問題やNクイーンの解を求める方法としては最も効率が良く、動的計画法よりもよい結果が得られる。

ヒューリスティクス

処理を高速化するための一般的なヒューリスティクスがいくつか知られている。変数の処理の順番は決まっていないので、最も制約がきつい変数（つまり、値の範囲が狭いもの）から探索を始めるのが効率的であり、それによって探索木を早く刈り取ることができる（早期の選択の影響を最大限有効利用できる）。

設定する値を選ぶとき、多くの実装ではなるべく他の値を制限しない値を選ぶ。そのような選択をする背景には a) 解の発見に結びつく可能性が高いこと、b) 未解決の制約がなくなったときに解が見つかっていること、がある。

洗練されたバックトラッキングの実装では、束縛関数をしばしば使用する。それにより、現在の部分解で解を得られるかどうかをチェックする。従って、解に結びつかない部分解を検出する束縛関数によって検索効率を改善することができる。束縛関数は頻繁に動作するため、その計算コストはなるべく小さいのが望ましい。さもなくば、アルゴリズムの全体としての効率は改善されない。効率的な束縛関数は他のヒューリスティック関数を作るのと同様の方法で作成される。すなわち、問題の規則（制約）の一部をゆるめるのである。

バックトラッキングを制約プログラミング言語で使用する場合、言語機構そのものも制約情報の更新をしなければならないため、奇妙なオーバーヘッドが発生する。そのような言語では、PlannerやPrologのように、単純な深さ優先探索を使うのが適切である。

バックアップで必要最小限の値をリカバリするためだけでなく、値の更新履歴を記録するため、バックトラッキングの実装では一般に「変数の航跡（英語: variable trail）」を保持する。効率的な実装では、バックトラッキングは1つの操作で全変化を消去するため、選択点のない連続した変化についての変数の航跡を生成しない。

変数の航跡以外の手法として、変数に加えられた最新の変化のタイムスタンプを保持する手法がある。タイムスタンプは選択点のタイムスタンプと比較される。選択点のタイムスタンプがその変数のタイムスタンプより後であれば、その選択点がバックトラックされる場合にその変数をリバートする必要はない（その変数は、その選択点以前に変更されているため）。

応用

バックトラッキングの最も広範囲な利用法として、正規表現の実行がある。例えば、"a*a" という単純なパターンはバックトラッキングしない場合に "a" にマッチしない（最初のパスで "a" が "a*" に食われてしまい、後続の "a" にはマッチさせるべき文字列が残らないため）。

バックトラッキングはプログラミング言語の実装にも使われている（Planner や Prolog）し、構文解析などにも利用される。その利用は人工知能分野で議論となり、アクターモデルの開発につながった。

関連項目

• アリアドネの糸 (論理学)

外部リンク

• プログラム言語演習II 宮寺庸造（東京学芸大学）
• アルゴリズム講座/実践編/バックトラック
• 制約充足問題における体系的探索手法の効率化についての検討 永井保夫（東京情報大学）