貪欲法と分割統治 — 「目先の最善」はいつ正しいか

動的計画法が「全部の可能性を表に貯める」戦略なら、貪欲法は「その場の最善だけを選んで振り返らない」戦略、分割統治は「半分にして征服する」戦略です。速いぶん、使ってよい条件がある。貪欲が勝つ瞬間と壊れる瞬間の両方を動かして、アルゴリズム設計の「型」を身につけます。

1. 目先の最善を積み重ねる — 区間スケジューリング

会議室が1つ、予約希望が15件。重ならないように、できるだけ多くの予約を採用したい。これが区間スケジューリング問題です。貪欲法の方針は「ある基準で並べ、先頭から順に、今までの採用と重ならなければ採用」——問題はその基準です。

候補は3つ。「開始が早い順」「所要時間が短い順」「終了が早い順」。下のデモで戦略を切り替えて、採用できた本数を比べてください。

区間スケジューリング — どの「並べ方」が一番多く採用できるか

戦略

黄枠＝いま検討中の区間、緑＝採用、薄い赤＝重なるので却下。水色の縦線が「確保済みの最終時刻」で、これより左から始まる区間は却下されます。最後に3戦略の採用数が比較表示されます。どの予約セットでも「終了が早い順」は必ず最多（＝最適）になります。

「終了が早い順」が最適である直感はこうです。最初に終わる区間を選んでおけば、残り時間が最大になる——つまりどんな最適解があっても、その最初の区間を「最速で終わる区間」に交換して損しない。この「最適解を貪欲の選択に交換しても悪化しない」という論法を交換論法（exchange argument）と呼び、貪欲法の正しさ証明の定番です。

2. 貪欲が壊れる瞬間 — コイン両替で反例を見る

両替問題：金額 x を最少枚数の硬貨で払う。貪欲法は「払える最大の硬貨から取る」。硬貨が {1, 5, 10, 25} なら、実はこれで常に最適です。ところが硬貨を {1, 3, 4} に変えた途端、貪欲は壊れます。金額6は貪欲だと 4+1+1 の3枚、正解は 3+3 の2枚。

貪欲 vs DP — 同じ金額を両者が並走して払う

硬貨セット

金額

上段＝貪欲法、下段＝DP（最適）。下のグラフは金額1〜40の全比較で、緑棒＝DPの最少枚数、橙枠＝貪欲の枚数、赤●＝貪欲が負ける金額です。{1,3,4} では 6, 10, 14, … と負けが並ぶ一方、{1,5,10,25} に切り替えると赤●が1つも出ません（この性質を持つ硬貨系を「カノニカル」と呼びます）。

dp[x] = min_{c ∈ 硬貨}( dp[x − c] ) + 1,　dp[0] = 0 DPは「1枚使う直前」の最適解から今を作る——貪欲が捨ててしまう選択肢も全部残す

注意 — 「たまたま合っていた」は通用しない {1, 5, 10, 25} で貪欲が最適なのは偶然に近い性質で、硬貨をひとつ変えるだけで崩れる。貪欲法を使うときは正しさの証明（交換論法など）か、反例の不存在を確かめる根拠を必ずセットにすること。小さい入力での全数チェックは反例探しの強力な道具になる。

3. 貪欲が正しいと言える条件

貪欲法が最適解を出すことが証明できる問題には、共通して2つの性質があります。

貪欲選択性（greedy choice property）：局所的な最善の選択を含む最適解が必ず存在する。交換論法で示すのが典型。
部分構造最適性（optimal substructure）：最初の選択をした後に残る部分問題の最適解が、全体の最適解の一部になっている。

2つ目はDPと共通です。つまり貪欲法は「表を作らなくても最初の1手が確定するDP」と見ることができます。ダイクストラ法（確定済み集合に最も近い頂点から確定）、クラスカル法（最も軽い辺から採用）、ハフマン符号（最も頻度の低い2記号を併合）は、いずれもこの構造を持つ有名な貪欲アルゴリズムです。

POINT — 設計の手順は「貪欲 → 反例 → DP」新しい最適化問題に出会ったら、①まず貪欲を疑う（一番速い O(n log n) 級の解になるため）。②小さな反例を探す（手計算や全数チェックで貪欲の答えと最適を比較）。③反例が出たらDPに切り替える。貪欲が通るなら証明を、通らないならDPの漸化式を書く——この順番が実務でも競技でも最短ルート。

一歩先へ — マトロイドという統一理論「重み最大の要素から順に、矛盾しない限り採用する」型の貪欲が常に最適になる構造は、マトロイドとして完全に特徴づけられている（Rado–Edmonds の定理）。クラスカル法が正しいのは、森（閉路のない辺集合）がグラフ的マトロイドをなすから。逆に区間スケジューリングはマトロイドではないのに貪欲が効く例で、貪欲の適用範囲はマトロイドより広い——「貪欲が効く⇔マトロイド」ではない点に注意。

4. 分割統治 — 3つのアルゴリズム、1つの骨格

貪欲法が「選択を1つに絞る」戦略なら、分割統治（divide and conquer）は「問題を小さく割って全部解き、結合する」戦略です。マージソート・二分探索・べき乗計算（繰り返し二乗法）は一見バラバラですが、分割→統治→結合という同じ3段テンプレートに載っています。

そして計算量は、分割数 a と結合コスト O(n^d) の綱引きだけでほぼ決まります。下のデモで再帰の木を層ごとに眺めながら、a と結合コストを切り替えてみてください。合計コストが O(n log n) → O(n) → O(n²) と姿を変えます。

分割統治の共通骨格 — 再帰の木と層ごとのコスト（n = 64, b = 2 固定）

例

分割数 a

結合コスト

上の3箱がテンプレート、左が再帰の木（各層の部分問題）、右がその層の総コストです。アニメは「分割で降りて、結合で層コストを合算しながら登る」を繰り返します。a=2・O(n) なら全層のコストが同じ 64 で層数 log n → O(n log n)。a=2・O(1) なら最下層が支配して O(n)。a=4・O(n) や a=2・O(n²) では根や葉の1層が爆発して O(n²)。

T(n) = a·T(n/b) + O(n^d) のとき　T(n) = O(n^d)（d > log_ba）／ O(n^d log n)（d = log_ba）／ O(n^log_ba)（d < log_ba）マスター定理（簡略形）— 結合が重ければ根が、分割が多ければ葉が、釣り合えば「全層×log n」が支配する

アルゴリズム	分割数 a	縮小率 b	結合コスト	再帰式	計算量
マージソート	2	2	O(n)	T(n) = 2T(n/2) + O(n)	O(n log n)
二分探索	1	2	O(1)	T(n) = T(n/2) + O(1)	O(log n)
べき乗（繰り返し二乗法）	1	2	O(1)	T(n) = T(n/2) + O(1)	O(log n)
（参考）カラツバ乗算	3	2	O(n)	T(n) = 3T(n/2) + O(n)	O(n^1.585)

二分探索とべき乗計算は、問題はまるで違うのに再帰式が同じなので計算量も同じになる点に注目してください。分割統治の解析では「何の問題か」より「a・b・結合コスト」だけが物を言います。カラツバ乗算のように分割数を1つ減らす工夫（4回の乗算を3回に）が指数を変える——これが分割統治設計の醍醐味です。

5. まとめ — 3つの設計方針の使い分け

貪欲法：最速・最省メモリ。ただし貪欲選択性の証明か反例チェックが必須。区間スケジューリングは「終了が早い順」で最適、コイン両替は硬貨系次第で崩壊。
動的計画法：部分構造最適性があり、選択を1つに絞れないとき。貪欲の反例が出たらこちら。
分割統治：問題が「独立な小問題＋結合」に割れるとき。計算量はマスター定理で a・b・結合コストから即座に読める。

一歩先へ — 3戦略は排他ではないクイックソートは「分割統治」だが、ピボット選択には乱択の工夫が入る。ハフマン符号は「貪欲」だが、正しさの証明は部分問題への帰着（DP的な見方）でなされる。実戦のアルゴリズムはこれらの戦略のハイブリッドであり、次回扱う「計算の限界」の世界では、貪欲は厳密解をあきらめた近似アルゴリズムとして再登場する。