貪欲法と最適性の証明（交換論法・マトロイド）

貪欲法は「いつ」正しいのか

貪欲法（greedy algorithm）は、各ステップでその時点の局所最良を選び、一度選んだら後戻りしないアルゴリズム設計です。実装は単純で高速ですが、致命的な問題があります。局所最良の積み重ねが大域最適になる保証はない。たとえば最短経路でも、ナップサック問題（0-1版）でも、素朴な貪欲は簡単に最適を外します。

だからこそ上級者に問われるのは「貪欲が動くか」ではなく「なぜこの貪欲は最適なのか、証明できるか」です。正当性を支える道具は主に2つ――交換論法（exchange argument）とマトロイド理論です。漸近計算量の記法に不安があれば計算量と Big-O 記法を先に押さえてください。

貪欲が最適になるには、問題が2つの性質を持つ必要があります。

• 貪欲選択性（greedy choice property）: ある局所最良の選択を含む大域最適解が必ず存在する。つまり最初の貪欲な一手を「捨てない」最適解が取れる。
• 最適部分構造（optimal substructure）: 最初の選択を固定した後の残り問題の最適解を足すと、全体の最適解になる。

この2つが揃えば、最初の貪欲な選択を残り問題に再帰的に適用するだけで最適解に到達します。動的計画法が「すべての選択を試して最良を残す」のに対し、貪欲は「正しい一手が事前に分かっている」点が本質的な違いです。

交換論法: 最適解を貪欲解へ寄せる

交換論法は、貪欲選択性を証明する最も汎用的な手法です。骨子はこうです。

1. 任意の最適解 OPT を取る。
2. OPT が貪欲の最初の選択 g を含まないと仮定する。
3. OPT の中の要素を g と**入れ替え（交換）**ても、解の価値が悪化しないことを示す。
4. ゆえに g を含む最適解が存在する。あとは残り問題に帰納を回す。

ポイントは「交換しても最適性を壊さない」を1手ぶんだけ示せばよいことです。全体を一気に比較する必要はありません。具体例で見ます。

区間スケジューリング（互いに重ならないよう最大個数の区間を選ぶ）では、貪欲は「終了時刻が最も早い区間を選ぶ」を繰り返します。これが最適である証明が交換論法の典型です。

greedy_interval(intervals):
  sort intervals by finish time ascending
  selected = []
  last_finish = -infinity
  for iv in intervals:
    if iv.start >= last_finish:   # 直前と重ならない
      selected.append(iv)
      last_finish = iv.finish
  return selected

証明: 貪欲が最初に選ぶ区間を g（最も早く終わる区間）とする。最適解 OPT の中で最も早く終わる区間を o とすると、g の終了時刻は o 以下。よって OPT の o を g に差し替えても、g は o より早く終わるので後続の区間と衝突せず、選べる区間数は減らない。これで g を含む最適解が作れた。残りの区間に同じ議論を繰り返せば、貪欲解が最適とわかる。

ハフマン符号: 交換で最適性を保証する

データ構造の応用であるハフマン符号も、交換論法で最適性が示せる代表例です。各文字に頻度が与えられ、平均符号長が最小の**接頭符号（prefix code）**を作る問題です。貪欲は「頻度が最小の2要素を併合して新しい節点にする」を繰り返し、二分木を下から組み上げます。

huffman(freqs):
  Q = min-heap of nodes keyed by frequency
  while size(Q) > 1:
    a = pop_min(Q); b = pop_min(Q)
    merge = Node(freq = a.freq + b.freq, left=a, right=b)
    push(Q, merge)
  return pop_min(Q)   # 根

正当性の核は次の交換補題です。最小頻度の2文字 x, y は、ある最適符号木で必ず最も深い同じ親を持つ兄弟にできる。証明は、最適木で最も深い兄弟 a, b を取り、x と a、y と b を入れ替える。頻度が小さい要素を深い位置へ動かすので、平均符号長（頻度×深さの総和）は増えない。つまり最適性を保ったまま x, y を最深の兄弟にできる。あとは x, y を併合した縮小問題に帰納すれば、貪欲が最適接頭符号を生むと示せます。

マトロイド: 貪欲が常に最適になる構造

交換論法は強力ですが、問題ごとに証明を作り直す手間があります。**マトロイド（matroid）**は「どんな重みでも貪欲が最適になる」問題クラスを代数的に特徴づける一般理論です。

マトロイドは集合 S とその部分集合族（独立集合）I の組で、次の3公理を満たします。

• 空集合は独立。
• 遺伝性: 独立集合の任意の部分集合も独立。
• 交換性: 独立集合 A, B で A が B より要素数が小さいなら、B の中に A へ加えても独立なままの要素が必ず存在する。

この交換性こそ、交換論法を構造として埋め込んだものです。各要素に重みを付け、重みの大きい順に、独立性を壊さない要素を取る貪欲（マトロイド貪欲）は、最大重み独立集合を常に与えることが証明できます（Rado–Edmonds の定理）。

最も身近な例が最小全域木のクラスカル法です。辺を重み昇順に見て、閉路を作らなければ採用する――これは「閉路を作らない辺集合＝森」を独立集合とするグラフ的マトロイド上の貪欲そのもの。だから個別の交換論法を組まなくても、マトロイドの定理1本で最適性が従います。

判断の手順をまとめる

貪欲法を実務やアルゴリズム設計で採るとき、正当性の確認は次の順で進めると曖昧さが消えます。

• まず反例を探す。素朴な貪欲基準で最適を外す入力を作れたら、その基準は捨てる。基準ごとに最適性が決まる。
• 交換論法を試す。最適解の1要素を貪欲の選択へ入れ替えても価値が悪化しないか。悪化しないなら貪欲選択性が立つ。
• マトロイドに乗るか確認する。独立集合が遺伝性と交換性を満たすなら、重み順貪欲が無条件で最適。クラスカル法はこの型。
• 乗らないなら動的計画法へ切り替える。最適部分構造はあるが貪欲選択性がない問題（0-1 ナップサックなど）は、全選択を試す DP が正解。

貪欲は「速いから使う」のではなく「最適性を証明できるから使う」設計です。交換論法という1手ぶんの議論と、マトロイドという構造の保証――この2つを押さえれば、貪欲が当たるか外れるかを勘でなく根拠で判断できます。