アルゴリズムパラダイムの系統（探索・最適化・近似の地図）

なぜ「パラダイムの地図」が要るのか

個別のアルゴリズムは数百あっても、その背後にある設計パラダイムは十指に収まります。実務で問われるのは「ダイクストラを覚えているか」ではなく、初見の問題に対してどの設計枠を当てるべきかを構造から判断できるかです。本稿は全探索・分割統治・動的計画法・貪欲法・乱択・近似・分枝限定を1枚の系統図に並べ、分岐の判断軸を明示します。

地図の起点は1つだけです。あらゆる組合せ問題は、原理上は全探索（総当たり）で解ける。残りのパラダイムはすべて「全探索のままでは指数時間で破綻するので、問題の構造を使って探索空間を削る／コストを下げる」派生として理解できます。つまりパラダイムの系統とは、全探索から枝を刈っていく順序の系図です。計算量記法に不安があれば計算量と Big-O 記法を先に押さえてください。

起点としての全探索と、その2つの限界

全探索は、解の候補空間を漏れなく列挙して条件を満たすものを選ぶ手法です。正しさは自明で、必ず最適解に到達します。問題は2つだけ。

• 空間が指数的: 部分集合は 2^n、順列は n! 通りあり、n がわずかに増えるだけで計算不能になる。
• 重複計算が多い: 同じ部分問題を何度も解き直すことがある。

この2つの限界のどちらを叩くかで、派生の方向が分かれます。空間を構造的に分割して征服するのが分割統治、重複計算を記憶で消すのが動的計画法、正しい一手を事前に確定して列挙そのものを省くのが貪欲法、列挙を続けつつ見込みのない枝を証明して捨てるのが分枝限定です。

構造を使う3系統: 分割・記憶・確定

全探索を実用化する3つの主要派生を、満たすべき構造とともに並べます。

3者の関係は入れ子です。分割統治は部分問題が独立(片方の解がもう片方に影響しない)なときに使えます。マージソートの左半分と右半分は独立です。ところが部分問題が重なると、分割統治のままでは同じ部分問題を指数回解き直してしまう。そこで重複分を表に記憶するのが動的計画法です。フィボナッチを素朴再帰で書くと指数時間なのに、メモ化すれば O(n) になるのが象徴的です。

さらに、DPでは全状態を試しますが、もし各段で選ぶべき一手が事前に確定できるなら、選択肢の列挙すら不要になります。これが貪欲法で、DPの特殊化と見なせます。「DPは全選択を試し最良を残す、貪欲は正しい一手が最初から分かっている」――この差が両者を分ける核心です。

全探索（指数時間・必ず最適）
  ├─ 部分問題が独立        → 分割統治
  │     └─ 部分問題が重なる → 動的計画法（記憶で重複除去）
  │           └─ 各段の最良手が確定 → 貪欲法（列挙を省略）
  └─ 列挙しつつ見込みなき枝を証明して捨てる → 分枝限定

選択のための3つの判断軸

ここまでを、初見の問題に当てる手順としてまとめます。上から順に問うと、当てるべき枠がほぼ一意に絞れます。

• 軸1: 最適部分構造があるか。部分問題の最適解を組み合わせると全体の最適解になるか。なければ DP も貪欲も使えず、全探索／分枝限定の世界です。
• 軸2: 貪欲選択性が立つか。各段の局所最良を選んでよいことを交換論法などで証明できるか。立てば貪欲、立たなければ DP。
• 軸3: 厳密解が要るか、近似で足りるか。問題が NP困難で入力が大きいなら、厳密解は諦め近似・乱択・ヒューリスティックへ降りる。

軸3が地図の後半を分けます。多項式時間で厳密に解ける問題（P クラス）なら前半の3系統で足ります。しかし巡回セールスマン（TSP）やナップサック、頂点被覆のように NP困難な問題では、n が大きいと厳密解が事実上得られません。P と NP の境界そのものは計算量クラス P と NPで扱います。ここで「厳密だが遅い」か「速いが厳密でない」かの二者択一が生じます。

厳密だが遅い: 分枝限定

厳密解にこだわるなら、全探索の指数空間をいかに賢く刈るかが勝負です。分枝限定（branch and bound）は、解空間を木として分岐（branch）しつつ、各部分木が到達しうる目的関数の限界値（bound）を評価し、現在の暫定最適を超えられないと証明できた枝を丸ごと捨てる手法です。

branch_and_bound(problem):
  best = +infinity          # 最小化問題の暫定最適
  stack = [root_partial_solution]
  while stack not empty:
    node = pop(stack)
    if bound(node) >= best:  # この枝の最良でも暫定に勝てない
      continue               # 枝ごと刈る（prune）
    if is_complete(node):
      best = min(best, cost(node))
    else:
      for child in branch(node):
        push(stack, child)
  return best

肝は bound の質です。緩めの下界しか出せないと刈れず、ほぼ全探索に退化します。逆に線形緩和（整数制約を実数に緩めて解く）などで強い下界を作れると、指数空間でも実用的に解けます。最悪計算量は指数のままですが、平均的には膨大な枝を刈れるのが価値です。整数計画ソルバの中核技術でもあります。

速いが厳密でない: 近似・乱択・メタヒューリスティック

厳密解を諦める側の地図です。ここは「どこまで質を保証するか」で階層化されます。

近似アルゴリズムは、最適値に対する解の比（近似比）を理論的に保証します。頂点被覆の極大マッチング法は必ず最適の2倍以内、距離が三角不等式を満たす TSP の Christofides 法は1.5倍以内、というように「最悪でもこの質」を約束できるのが価値です。

乱択アルゴリズムは乱数を使い、期待計算時間や正答確率を保証します。クイックソートは枢軸をランダム化すると期待 O(n log n)、Miller–Rabin 素数判定は誤答確率を任意に小さくできます。近似が「解の質」を保証するのに対し、乱択は「時間や確率」を保証する、と保証の対象が違う点を区別してください。

メタヒューリスティック（焼きなまし・遺伝的アルゴリズム・局所探索）は理論保証を持たず、経験的に良い解を返します。保証がない代わりに適用範囲が広く、定式化が難しい実問題で最後の手段になります。

1枚の地図にまとめる

最後に全体を1本の系統として俯瞰します。年代でなく枝刈りの論理で並べた系図です。

全探索（総当たり・必ず最適・指数時間）
│
├─ P クラス（多項式時間で厳密に解ける）
│    ├─ 部分問題が独立            → 分割統治
│    ├─ 部分問題が重複＋最適部分構造 → 動的計画法
│    └─ 上記＋貪欲選択性が成立      → 貪欲法
│
└─ NP困難（厳密解が現実的でない）
     ├─ それでも厳密解が要る        → 分枝限定（強い下界で枝刈り）
     └─ 近似で足りる
          ├─ 近似比を理論保証        → 近似アルゴリズム
          ├─ 時間・確率を保証        → 乱択アルゴリズム
          └─ 保証は不要・実用解優先    → メタヒューリスティック

判断の順序を一文で言えば、**「最適部分構造はあるか → 貪欲選択性は立つか → 厳密解が要るか近似で足りるか」**の3問を上から潰すだけです。この地図を持っていれば、初見の問題でも当てるべきパラダイムを勘でなく構造から絞り込めます。個々のアルゴリズムを覚える前に、この分岐の論理を体に入れることが、設計力の土台になります。