バックトラッキング完全解説：基本概念・実装・最適化・CSPと実用応用

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

はじめに — バックトラッキングとは何か

バックトラッキング（backtracking）は、探索や組合せ最適化、制約充足問題（CSP）などで広く用いられるアルゴリズム設計の基本手法の一つです。部分解を順次構築しつつ、それが解の条件（制約）を満たさないと判定された時点でその部分解を取り消して（後退して）別の選択肢を試す、という深さ優先探索ベースの手続きを指します。探索空間が指数的に増大する問題に対して「必要な部分だけ」を調べることで実用的に解を見つけることを目指す手法です。

基本的な考え方

  • 探索空間を「決定列（変数に値を割り当てる一連の操作）」として捉える。
  • 1つずつ変数に値を割り当て、部分割当が制約を満たすかチェックする（局所的な検査）。
  • 満たしていれば次の変数へ進み、満たしていなければその割当を取り消し（バックトラック）別の値を試す。
  • 全変数を割り当てられたら解を発見したことになる。

疑似コード（典型的な再帰実装）

function backtrack(変数のインデックス i, 割当 current):
  if i == n:
    解を出力または記録
    return
  for 値 v in 候補集合:
    if current に v を割り当てても制約を満たす:
      current[i] = v
      backtrack(i+1, current)
      current[i] = 未割当  // バックトラック（後退）

この単純形が様々な最適化手法（枝刈り、ヒューリスティック、制約伝播など）と組み合わされて運用されます。

計算量と理論的性質

バックトラッキングの計算量は一般に探索木の形状（分岐数 b と深さ d）に依存します。最悪ケースでは全ての組合せを試すため O(b^d) の指数時間になります。しかし実際には制約を満たさない部分解で早期に枝刈りできることが多く、実用上は劇的に高速化される場合があります。

重要な点は「最悪計算量が指数的である」ことを受け入れつつも、問題固有の制約利用やヒューリスティックにより平均的・実効的な性能を大幅に改善できる点です。

代表的な応用例

  • パズル類：ナンプレ（数独）、8クイーン、迷路探索など。
  • 組合せ生成：順列・組合せ列挙、部分集合列挙。
  • 制約充足問題（CSP）：スケジューリング、割当問題、論理式の充足（SAT とは異なるが類似手法で解く場合もある）。
  • 整数問題：部分和問題、ナップサックの一部インスタンス。
  • アルゴリズム的応用：探索木の枝刈りを使った分枝限定法（branch-and-bound）や、組合せ最適化問題への組み込み。
  • パーサ／正規表現実装：バックトラッキング型の正規表現エンジン（典型的には PCRE 等）ではマッチング時にバックトラックが起きる。

実践上の最適化（枝刈りと制約伝播）

バックトラッキングを実用的にするための代表的な手法を挙げます。

  • 早期枝刈り（Pruning）: 部分解が制約を破る段階でそれ以上探索しない。
  • 変数選択ヒューリスティック: MRV（最小残余値、最も候補が少ない変数を先に決める）などにより早く不適合を検出。
  • 値の選択ヒューリスティック: LCV（最も影響が少ない値を先に選ぶ）など。
  • 前方検査（Forward Checking）: ある変数に値を割り当てた際に残り変数の候補を制限し、候補が空になる場合は早期に戻る。
  • 制約伝播（Constraint Propagation）: AC-3 等のアルゴリズムで弧整合性を保ち、可能性を排除して枝を減らす。
  • メモ化・DP の併用: 部分問題が重複する場合は結果を保存して再計算を避ける。ただし副作用が多い制約付き探索では難しい場合がある。
  • 特化アルゴリズムとの併用: 例えば正確被覆問題（Exact Cover）はダンシングリンク（Dancing Links, Knuth）で高速化可能。

バックトラッキングと他手法の比較

  • 深さ優先探索（DFS）との関係: バックトラッキングは本質的に DFS による枝刈り付き探索。
  • 幅優先探索（BFS）や動的計画法（DP）: 最短経路や最小コスト問題では BFS や A*、DP の方が適切な場合が多い。バックトラッキングは組合せ列挙や制約充足に強みがある。
  • 分枝限定法（Branch-and-Bound）: バックトラッキングの枠組みで上界・下界を使った剪定を行うことで最適化問題に適用できる。

実装上の注意点と落とし穴

典型的な注意点は以下の通りです。

  • 再帰深度の問題: 深い探索では再帰の深さが問題になるため、再帰抑制や明示的なスタック実装に切替える必要がある場合がある。
  • 不要なコピーの排除: 状態（割当や候補集合）を毎回コピーすると遅くなる。差分更新と復元（undo）を使うと高速化できる。
  • 正規表現の「バックトラッキング」: PCREのようなバックトラッキング型正規表現エンジンでは、誤ったパターンや長い入力で「カタストロフィック・バックトラッキング（ReDoS）」を招き得る。正規表現設計に注意し、必要なら DFA ベースや possessive quantifiers、Atomic grouping を使う。

具体例：N-Queens（N-クイーン）問題

N-クイーン問題は典型的なバックトラッキングの教科書的例です。各行に1つずつクイーンを置くことで、列・斜めの衝突をチェックするだけでよく、部分解が衝突を起こした時点でその分岐を切ることで実用的な速度が出ます。ビット演算を用いた実装により、サイズがある程度大きくても高速に解けます（バックトラッキング＋ビットマスクによる最適化）。

バックトラッキングに関する高度なトピック

  • IDA*（Iterative Deepening A*）: 深さ制限付き探索を反復的に増やし、ヒューリスティックと組み合わせる手法。パス探索でのメモリ削減に有利。
  • 制約充足問題（CSP）のフレームワーク: Prolog や多くの CP ソルバはバックトラッキングを基盤にしつつ、強力な制約伝播エンジンを組み込んでいる。
  • 並列化: 独立したサブツリーを異なるスレッド／ノードで探索することでスケールアウト可能。ただし探索順序や共有解の管理が課題。

まとめ

バックトラッキングは「試してダメなら戻る」という単純だが強力な方針を持つ探索手法です。最悪は指数的ですが、問題固有の制約利用やヒューリスティック、制約伝播と組み合わせることで多くの実問題に対して有効です。また、正規表現やパーサなど実装の文脈では「バックトラッキング」が性能問題（ReDoS 等）に直結するため、用途と実装の違いを理解して適切に使うことが重要です。

参考文献

カテゴリー
IT
前の記事
反復深化探索（IDDFS/IDS）徹底ガイド：仕組み・計算量・完全性・最適性と実装のコツNew!!
2025年11月20日
次の記事
ダイクストラアルゴリズム徹底解説：非負グラフの最短経路を効率的に求める基本手法と実装ガイドNew!!
2025年11月20日