貪欲アルゴリズム(Greedy Algorithm)
1. 概要
A. 定義
貪欲アルゴリズム(Greedy Algorithm)とは、各段階でその瞬間に最も良く見える局所最適(local optimum)の選択を行い、一度下した決定を取り消さないことにより、大域最適解(global optimum)に到達しようとする問題解決戦略であり、選択が大域最適へつながりうる貪欲選択性(greedy choice property)と最適部分構造(optimal substructure)が成り立つ問題に限って正しい答えを保証する。
貪欲アルゴリズムは「今すぐ最も有利なものを取り、後ろを振り返らない」という極めて単純な直観をアルゴリズムとして形式化したものである。釣り銭を渡すとき最大単位の硬貨から取る日常的な行動が典型例で、人はすべての組合せを吟味せずとも大きな硬貨から使えば枚数が減ることを経験的に知っている。このように貪欲戦略は「全体を見ず目先の最善だけで決定する」ため実装が簡潔で、たいてい多項式時間(しばしばO(n log n))で終わり、全探索や動的計画法より圧倒的に速い。まさにこの速さが貪欲アルゴリズムを魅力的にするが、同時に「局所最適の連続が果たして大域最適か」という正当性の問題が常につきまとう。
貪欲アルゴリズムの価値と危険は表裏一体である。特定の条件を満たす問題(最小全域木、ハフマン符号化、分数ナップサック、ジョブスケジューリングなど)では貪欲が証明可能に最適解を出すが、条件が崩れればもっともらしいが明白に誤った答えを出す。したがって貪欲アルゴリズムを扱う技術士の核心的力量は、「貪欲で解ける問題かをまず判別し、解けるなら貪欲選択の正当性を論証し、解けなければ動的計画法や全探索へ転換する」という設計判断にある。
B. 登場背景と必要性
多くの最適化問題は、可能な解の数が入力サイズに対して指数的に爆発する。例えばn個のジョブをどの順で処理するか、n個の品物のうち何をナップサックに入れるかは、それぞれn!・2ⁿ規模の場合の数をもち、すべての場合を列挙する全探索(brute force)はnが少し大きくなるだけで現実的に不可能になる。動的計画法(DP)は重複する部分問題を保存してこの爆発を多項式時間に抑えるが、状態空間が大きければメモリと時間は依然として負担となる。この地点で「すべての場合を吟味せずとも正しい答えに到達する近道」への要求が生じ、問題が特定の構造をもつとき貪欲アルゴリズムがその近道を提供する。
ここで重要な点は、全探索とDPが「あらゆる可能性をともかく舐める」受動的戦略であるのに対し、貪欲は「問題の構造を理解し、ほとんどの可能性を最初から見もしない」能動的戦略だということである。この違いは単なる高速化を超え、問題に内在する秩序(整列可能な優先度、交換可能な要素、マトロイド構造)を洞察してはじめて貪欲が成立するという意味でもある。したがって貪欲アルゴリズムを設計するとは、すなわち「この問題のどの性質が全数探索を不要にするか」を解き明かす作業であり、これはアルゴリズム設計者の問題分析力を最も直接的に試す領域である。
さらに現実の多くのシステムは、リアルタイム性と資源制約のもとで「完璧でなくとも速く十分に良い」解を要求する。ネットワークルータはミリ秒単位で経路を更新せねばならず、OSスケジューラは毎瞬間に次の実行プロセスを即座に選ばねばならず、データ圧縮器はストリームを通過しながら符号を生成せねばならない。このような環境では、全体を再計算するDPより、入ってくる情報に対して局所的に即座に決定する貪欲戦略が構造的により適する。さらに完全最適解がNP困難(NP-hard)で多項式時間に解けない問題(集合被覆、巡回セールスマン問題など)では、貪欲が最適ではなくとも保証された近似比(approximation ratio)をもつ実用的な解を提供し、理論と実務をつなぐ。このように貪欲アルゴリズムは「正確性を条件付きで保証する高速な最適化器」であり「困難問題の信頼できる近似器」という二重の必要性の上に立っている。
2. 貪欲アルゴリズムの動作原理と正当性条件
貪欲アルゴリズムが正しく動作するための二つの核心条件は、貪欲選択性と最適部分構造である。この二つが成り立ってこそ「局所最適の連鎖が大域最適」という飛躍が正当化される。
flowchart TB
PROB["最適化問題"] --> Q1{"貪欲選択性が成立?"}
Q1 -->|"いいえ"| DPFULL["DP / 全探索へ転換"]
Q1 -->|"はい"| Q2{"最適部分構造が成立?"}
Q2 -->|"いいえ"| DPFULL
Q2 -->|"はい"| GREEDY["貪欲アルゴリズム適用 (最適性を保証)"]
GREEDY --> PROOF["正当性証明: 交換論法 / マトロイド"]
貪欲選択性とは「大域最適解のうち少なくとも一つは、各段階の貪欲的選択を含むように構成できる」という性質である。すなわち今取る局所最善が最終最適解の一部になりうるのでなければならない。これを厳密に示す標準技法が交換論法(exchange argument)である。任意の最適解を仮定したうえで、その解から貪欲が選んだ要素が抜けているなら、他の要素と入れ替えても解が悪化しないことを示し、貪欲選択を含む最適解が必ず存在することを証明する。例えば活動選択問題で「終了時刻が最も早い活動を先に選ぶ」貪欲が正しい理由は、任意の最適解の最初の活動を終了がより早い貪欲活動に替えても、以降選択可能な活動が減らないからである。交換論法は貪欲アルゴリズムの正当性を扱う最も普遍的な道具であるから必ず習熟せねばならない。
交換論法をもう少し具体的に見ると、その骨格は「貪欲解と最適解が異なるなら、最適解を少しずつ貪欲解の側へ変形しても品質が落ちない」ことを示すことである。最初の選択が異なれば最適解の最初の選択を貪欲の最初の選択に置き換え、それでもなお最適であることを確認したうえで、この過程を二番目・三番目の選択へ繰り返す。すべての選択を置き換え終えると最適解が貪欲解と完全に同じになるため、結局「貪欲解も最適」という結論に至る。この帰納的置換がどの段階でも品質を損なわないことを証明するのが交換論法の核心であり、まさにその証明が可能であってはじめて貪欲を安心して採用できる。
最適部分構造とは「問題の最適解が部分問題の最適解で構成される」という性質で、貪欲が一要素を確定した後、残る部分問題もまた同じ貪欲戦略で最適解を得られねばならないことを意味する。この性質は動的計画法も共有するが、両技法の決定的な違いは部分問題を解く方式にある。動的計画法は複数の部分問題の解をすべて求めて比較・組合せするが、貪欲は「貪欲選択一つで部分問題をただ一つに狭め」その一筋だけを辿って降りていく。まさにこの「選択肢を一つに減らして振り返らない」おかげで貪欲がDPより速いが、その選択が誤れば全体が狂うという危険も併せ負う。
flowchart LR
S0["全体問題"] --> C1["貪欲選択 1 (局所最適)"]
C1 --> S1["縮小された部分問題"]
S1 --> C2["貪欲選択 2"]
C2 --> S2["より小さい部分問題"]
S2 --> DOTS["..."]
DOTS --> SOL["大域最適解"]
C1 -. "振り返らない(irrevocable)" .-> C1
正当性が保証されない代表的な反例が釣り銭問題である。硬貨単位が{1, 5, 10, 25}のような正準(canonical)体系であれば「大きい単位から」貪欲が最小枚数を保証するが、{1, 4, 6}体系で8を釣るとき貪欲は6+1+1=3枚を取る一方、最適解は4+4=2枚である。同じ問題でも入力条件(硬貨体系)が変われば貪欲の正当性が崩れるというこの事実は、貪欲アルゴリズムを使う前に必ず正当性を検証せねばならないことを鮮明に示す。検証なしに「直観的に正しく見える」という理由で貪欲を適用するのは典型的な設計誤りである。
この反例が与える教訓は、単に「貪欲が時々誤る」ではなく、局所最適の罠(local optimum trap)というより一般的な構造的限界を露わにする点にある。貪欲は現在の選択が将来に及ぼす波及を見ずに目先の利得だけを追うため、「今少し損をしても後で大きく得」という経路を原理的に探索できない。{1, 4, 6}体系で6を取った瞬間、残りの2を1+1でしか埋められなくなるのがまさにこの罠である。動的計画法がすべての選択肢を保存・比較してこうした「遅延した利得」を捉えるのと対照的に、貪欲はその一筋をまるごと捨てる。したがって貪欲の正当性検証とは本質的に「この問題には局所最適の罠が存在しない」ことを示す作業であり、交換論法はまさにその不在を証明する道具である。
3. 設計手順と代表アルゴリズム
以上の二条件を備えた問題において、貪欲アルゴリズムの設計はおおむね共通の手順に従う。まず最適化対象(目的関数)を定義し、各段階の貪欲選択基準(整列キー)を定めたうえで、選択が制約を違反しないか検査しながら解を累積し、最後に交換論法などで正当性を証明する。多くの貪欲アルゴリズムが「特定の基準で整列した後、前から走査する」形をもつため、支配的コストが整列のO(n log n)である場合が多い([[sorting-algorithms]]参照)。
この手順で最も創造的かつ難しい段階は貪欲選択基準を定めることである。残りの段階(制約検査・解累積)は機械的だが、「何を基準に最も良いものを選ぶか」は問題ごとに異なり、誤って選べば直ちに誤答につながる。そこで熟練した設計者は、もっともらしい候補基準を複数立てたうえで各々に対し小さな反例を積極的に探してふるい落とし、反例が出ない基準に対してのみ交換論法で正当性を確定する方式で臨む。下のフローチャートはこの共通手順を図示したものである。
flowchart TB
START["問題定義 · 目的関数"] --> SORT["貪欲基準で候補を整列"]
SORT --> LOOP{"残り候補あり?"}
LOOP -->|"はい"| PICK["基準上の最善候補を選択"]
PICK --> FEASIBLE{"制約違反なし?"}
FEASIBLE -->|"はい"| ADD["解集合に追加"]
FEASIBLE -->|"いいえ"| SKIP["スキップ"]
ADD --> LOOP
SKIP --> LOOP
LOOP -->|"いいえ"| PROOF["正当性検査の後に解を返す"]
A. 活動選択とジョブスケジューリング
活動選択問題(activity selection)は、開始・終了時刻が与えられた活動集合から互いに重ならない最大個数の活動を選ぶ問題である。貪欲基準は「終了時刻が最も早い活動を先に選択」であり、選んだ活動と重ならない次の活動を繰り返し選ぶ。終了が早いほど後に残る時間が多くなり、より多くの活動を詰める余地が大きくなるため、この基準が正しい。例えば一つの会議室に(1–4), (3–5), (0–6), (5–7), (3–9), (5–9), (6–10), (8–11), (8–12), (2–14), (12–16)の十一件の会議要請があれば、終了時刻順の貪欲は(1–4)→(5–7)→(8–11)→(12–16)の四件を割り当て、最適を達成する。興味深いことに「最も短い活動から」または「最も早く始まる活動から」というもっともらしい他の基準は反例が存在して最適を保証できず、これはどの貪欲基準を選ぶかが正当性を左右することを示す重要な教訓である。この原理はCPUスケジューリング、講義室・設備予約、広告スロット配置など、一つの資源に重ならないジョブを最大限に詰める実務問題に広く適用される。変形として各活動に価値(weight)が付与され「個数ではなく価値の和を最大化」せねばならない場合、単純な終了時刻貪欲はもはや最適を保証せず、重み付き区間スケジューリング(weighted interval scheduling)という動的計画法問題に転換される点も併せて知っておかねばならない。これは「活動ごとに価値が同じ」という隠れた前提が貪欲の正当性を支えていたことを露わにし、前提が変われば技法も変わらねばならないという繰り返される教訓を再確認させる。
B. 分数ナップサック問題
分数ナップサック(fractional knapsack)は、容量Wのナップサックに品物を入れて価値の和を最大化するが、品物を分割して入れられる問題である。貪欲基準は「単位重量当たり価値(価値/重量)が高い品物から満杯に入れ、最後の品物は残り容量だけ分割して入れる」である。例えば容量50kgのナップサックに(価値60, 重量10), (価値100, 重量20), (価値120, 重量30)の三品物があれば単位価値はそれぞれ6, 5, 4なので、1番(10kg·60)→2番(20kg·100)を丸ごと入れ、3番は残り20kgだけ(2/3)入れて価値60+100+80=240を得る。分割できるので単位価値の順がそのまま最適順となり、貪欲が正確に最適解を出す。
しかし品物を分割できない0/1ナップサックに条件が変わると、同じ貪欲が最適を保証できない。容量10kgに(価値60, 重量10), (価値70, 重量10)…のような構成では「単位価値の順に一つだけ入れる」がより価値の大きい組合せを逃しうるからである。0/1ナップサックは「入れる/入れない」の組合せを吟味せねばならないので貪欲選択性が崩れ、動的計画法(または分枝限定)で解かねばならない。分数ナップサックと0/1ナップサックのこの極端な対比は、「分割できるか」という制約一つが貪欲の正当性を分ける決定的要因であることを示す、技術士答案で頻繁に使われる代表事例である([[dynamic-programming]]参照)。
C. ハフマン符号化
ハフマン符号化(Huffman coding)は、文字別の出現頻度に応じて可変長接頭符号(prefix code)を生成し、データを可逆圧縮する貪欲アルゴリズムである。貪欲基準は「頻度が最も低い二ノードを繰り返し併合する」で、各段階で最小頻度の二ノードを取り出して併合ノードに束ね、二分木を下から上へ構築する。よく現れる文字には短い符号を、稀な文字には長い符号を与えて平均符号長が情報エントロピーに近づくようにする。例えば文字a·b·c·d·e·fの頻度が45·13·12·16·9·5であれば、ハフマンは最も稀なf(5)·e(9)をまず併合して14を作り、次に小さいc(12)·b(13)を併合して25を作る式で木を下から上へ構築する。こうして完成した木でaは1ビット、残りは3~4ビットの符号を受け、固定長3ビット符号(総300ビット規模)より小さい約224ビットに縮む——よく使う文字に短い符号を寄せた効果である。この「最小頻度優先」貪欲の正当性もまた交換論法で証明され(最適木で最も深い二葉は頻度が最も低い二文字に替えても損がない)、最小ヒープ(優先度キュー)を使えばO(n log n)で動作する。ハフマン符号化はJPEG·MP3·ZIP(DEFLATE)·PNGなど広範な圧縮標準のエントロピー符号化段階に実際に組み込まれ、貪欲アルゴリズムが産業標準の心臓部で動作する代表事例に数えられる。
D. グラフにおける貪欲:最小全域木とDijkstra
グラフ問題でも貪欲は核心的な設計戦略である。最小全域木(MST)を求めるKruskalアルゴリズムは「重みが最も小さい辺から、閉路を作らなければ採択」する貪欲であり、Primアルゴリズムは「現在の木に最も安く連結される頂点を一つずつ吸収」する貪欲である。いずれもグラフのカット性質(cut property)——「任意のカットを横切る最小重み辺はあるMSTに必ず含まれる」——によって最適性が保証される。Kruskalは辺を整列しUnion-Findで閉路を検査してO(E log E)で、Primは最小ヒープを使ってO(E log V)で動作し、通信網ケーブル敷設の最小化、電力網設計、クラスタリング(single-linkage clustering)などに使われる。
KruskalとPrimが同じMSTを異なる順序で積み上げる点は、貪欲戦略の柔軟性を示す。Kruskalが「全体の辺を重み順に舐めながら森(forest)の断片を徐々に併合する」大域的観点であるなら、Primは「一頂点から出発して木を一層ずつ育てる」局所成長の観点である。いずれにせよ各段階の貪欲選択(最小辺・最小連結頂点)がカット性質によって安全であることが保証されるので結果の最適性は同一であり、辺の多い密グラフではPrim(隣接行列ベースO(V²))が、疎グラフではKruskalが有利という式でグラフ密度に応じて選択が分かれる。一方、先に扱った[[shortest-path]]のDijkstraアルゴリズムもまた「未確定頂点のうち暫定距離が最小の頂点を確定する」貪欲であり、非負の重みという条件が貪欲選択の正当性を支える。興味深いことにPrimとDijkstraは「現在の集合に最も近い頂点を吸収する」という骨格がほぼ同じだが、Primは「辺の重みそのもの」を、Dijkstraは「出発点からの累積距離」を基準とする点だけが異なる。このようにグラフアルゴリズムの相当部分が貪欲パラダイムの上に立っている点は、貪欲戦略の設計的普遍性をよく示している。
4. 比較:貪欲 · 動的計画法 · 全探索
最適化問題を解く三つの代表的パラダイムである貪欲・動的計画法・全探索は、「どれだけ多くの場合を吟味するか」と「正確性をどこまで保証するか」で分かれる。下の表はその違いを整理するが、違いが生じる理由は各技法が部分問題を扱う方式に根ざす。
| 区分 | 貪欲アルゴリズム | 動的計画法 | 全探索 |
|---|---|---|---|
| 核心戦略 | 局所最適選択·取り消さない | 部分問題解の保存·組合せ | すべての場合を列挙 |
| 部分問題処理 | 選択で一つに狭める | 複数の解をすべて比較 | 分枝の全数探索 |
| 最適解保証 | 条件成立時のみ | 常に(当該構造で) | 常に |
| 時間計算量 | たいていO(n log n) | 多項式(状態数×遷移) | 指数(n!·2ⁿ) |
| メモリ | 小さい | 状態テーブルの分だけ大きい | 小さい(再帰スタック) |
| 適合状況 | 貪欲選択性が成立 | 重複部分問題·最適部分構造 | 小規模·正確性が絶対 |
貪欲と動的計画法はいずれも最適部分構造を要求する点で近いが、貪欲選択性の有無が両者を分かつ。この性質が成り立てば「各段階の選択を比較なしに即座に確定」できるので貪欲がDPより指数的に速く、メモリもほとんど使わない。逆にこの性質がなければ(0/1ナップサックのように)貪欲は誤り、DPですべての選択肢を保存・比較せねばならない。したがって実務的含意は「貪欲選択性が証明されれば貪欲を、重複部分問題だけがあればDPを、両方とも不確かで入力が小さければ全探索を」選べということである。特に同じ問題でも制約条件が変われば適合する技法が変わるという点(分数ナップサック↔0/1ナップサック)を見落とすと、見かけ上は正答のようだが特定の入力で食い違う致命的な欠陥を作る。
計算量の違いを数値で体感すれば、三パラダイムの隔たりが明瞭になる。入力サイズn=40の0/1ナップサックを全探索で解けば2⁴⁰≈1兆の枝を吟味せねばならず、現代のCPUでも数十分以上かかるが、容量Wが1,000程度なら動的計画法は40×1,000=4万個の状態だけを埋めてミリ秒で終わる。一方、同じ品物を分割できる分数ナップサックであれば貪欲は単位価値で整列するO(40 log 40)≈200程度の演算で十分である。このように「全探索の指数 → DPの多項式 → 貪欲の準線形」へと下がるコスト削減は劇的だが、その削減は各段階で問題構造に対するより強い仮定を代価に買う——DPは最適部分構造を、貪欲はそれに加えて貪欲選択性を要求する。ただ飯はなく、速いアルゴリズムほど適用条件が厳しいというこの原理がパラダイム選択の土台となる。
三技法の関係を一文で要約すれば、全探索は「遅いが常に正しい基準線」、動的計画法は「重複を除去して全探索を多項式に圧縮した安全な最適化器」、貪欲は「特定の構造を前提にDPさえ一筋に縮めた最も速い最適化器」である。実際のシステムはしばしばこれらを結合する——例えば0/1ナップサックの分枝限定(branch and bound)は全探索の探索空間を貪欲的上界(分数ナップサック解)で枝刈りし、実用性能を引き上げる。
5. 深化:マトロイド理論と近似アルゴリズム
貪欲アルゴリズムが「いつ最適を保証するか」に対する最も深い理論的答えはマトロイド(matroid)にある。マトロイドは有限集合とその部分集合の集まり(独立集合)が遺伝性(hereditary)と交換性(exchange property)を満たす構造で、「ある問題が重み付きマトロイドで表現されれば貪欲アルゴリズムが常に最適解を保証する」という定理(Rado-Edmonds)が成り立つ。最小全域木が貪欲(Kruskal)で最適を得る根本的理由も、グラフのグラフィックマトロイド(graphic matroid)構造から来る。この理論は「直観的に貪欲が正しいか」を超えて「貪欲が正しい十分条件は何か」を数学的に究明する点で、個別の交換論法を一般化する強力な枠組みである。ただしすべての貪欲成功事例がマトロイドで説明されるわけではなく(活動選択などはより弱い条件でも成立)、マトロイドは十分条件であって必要条件ではない。マトロイド理論が実務に与える含意は、新たな最適化問題に出会ったとき「この問題の解集合が遺伝性と交換性を満たすか」を点検することで貪欲適用の可能性を構造的に事前判別できる点にある。二つのマトロイドの共通部分(matroid intersection)までは依然として多項式時間で解けるが、三つ以上の共通部分はNP困難に移るという境界も知られており、問題をいくつのマトロイド制約に還元できるかが貪欲・多項式アルゴリズムの適用限界を測る理論的尺度となる。
貪欲のもう一つの重要な舞台は近似アルゴリズム(approximation algorithm)である。NP困難な最適化問題は多項式時間に最適解を求められないとされるので、実務では「最適ではないが最適に対して一定比率以内であることを保証する」近似解で妥協する。代表的に集合被覆(Set Cover)問題で「まだ覆えていない要素を最も多く覆う集合を繰り返し選択する」貪欲はln n倍の近似比を保証し、これはP≠NPの仮定の下で理論的にほぼ最善の近似比であることが知られている。巡回セールスマン問題(TSP)の最近傍(nearest neighbor)貪欲や、作業負荷分散の最長ジョブ優先(LPT)貪欲も保証された近似比をもつ実用的解法である。このように貪欲は「正確な最適化器」であるのみならず「困難問題の信頼できる近似器」として、正確性を一部譲る代わりに多項式時間と性能保証を得る典型的なトレードオフを体現する。
近似アルゴリズムで貪欲が特に好まれる理由は単純さと分析可能性にある。局所探索・遺伝的アルゴリズム・整数計画法のような代替は、より良い解を出しうるが収束性・実行時間を事前に保証しがたい一方、貪欲近似は実装が簡単でありながら「最適解の何倍以内」という最悪の場合の保証(worst-case guarantee)を数学的に証明できる。例えば複数の機械にジョブを分配して完了時刻を最小化する問題でLPT(長いジョブ優先)貪欲は最適に対し(4/3 − 1/3m)以内であることが証明され、実務で「このスケジュールはどれほど悪くとも最適より33%以上は悪くない」という式の明確な品質約束ができる。このような保証の有無が運用環境でアルゴリズムを信頼して採択できるかを分ける決定的要素であり、まさにこの点が貪欲近似を数多くのスケジューラ・バッチシステムの基本戦略に据えた背景である。
近年の動向としてはオンライン・ストリーミング環境での貪欲が注目される。入力全体を事前に見られずデータが流れ込む状況(オンライン広告割当、リアルタイムマッチング、ストリーミング集合被覆)では、振り返らない貪欲の性質がかえって自然な適合性をもつ。オンライン二部マッチングのRANKINGアルゴリズムが1−1/eの競合比を達成するように、貪欲ベースのオンラインアルゴリズムの競合分析(competitive analysis)は活発な研究領域である。さらに劣モジュラ関数(submodular function)最大化で貪欲が1−1/e近似を保証するという結果は、推薦システム・データ要約・センサ配置など現代のAI・データ応用で貪欲の理論的土台を提供し、貪欲アルゴリズムが古典的データ構造を超えて最新分野へ拡張されていることを示す。
6. 考慮事項と示唆
これまで見てきた貪欲アルゴリズムの原理・事例・理論を実際のシステム設計に移すとき、技術士は単に「速い」という理由で貪欲を選ぶより、正当性・適用条件・代替との関係を総合的に判断せねばならない。以下はその判断で核心的に考慮すべき事項である。
正当性証明のない貪欲適用を警戒する。 貪欲は「直観的に正しく見える」という理由だけで採択してはならず、交換論法やマトロイド構造で貪欲選択性と最適部分構造を必ず検証せねばならない。釣り銭・0/1ナップサックのように条件が変われば貪欲が誤る事例が多いので、要求分析段階で「この問題が本当に貪欲で解けるか、反例はないか」を先手で点検し「もっともらしいが誤った」解を排除せねばならない。
問題条件と制約に応じて技法を転換する。 同じナップサック問題も「分割できるか」に応じて貪欲(分数)とDP(0/1)に適合する技法が分かれ、グラフの負辺の有無がDijkstra(貪欲)の適用可能性を左右する。貪欲選択性が成り立てば貪欲を、重複部分問題だけがあればDPを、入力が小さく正確性が絶対であれば全探索を選ぶ式で、条件を診断して正しいパラダイムを選ぶ設計判断が核心である。
貪欲基準(整列キー)の選択が正当性を決める。 活動選択で「終了時刻優先」は最適だが「最も短い活動優先」は反例があるように、同一問題でもどの基準で貪欲的選択をするかが正答と誤答を分ける。したがって複数の候補基準を比較し各々の反例を検討して正当性が証明された基準だけを採択せねばならず、この過程を省けば特定の入力でのみ失敗する潜伏欠陥を生む。
近似と正確性のトレードオフをサービス要求に合わせて調整する。 NP困難問題では最適解の代わりに貪欲近似解が現実的な選択であり、集合被覆のln n近似のように保証された近似比を知ることが重要である。リアルタイム性・資源制約の大きいシステム(ルーティング・スケジューリング・ストリーミング)では「完璧な最適」より「速く十分に良い」貪欲解が合理的でありうるので、正確性・応答性・資源の均衡点をSLAとコストの観点で判断せねばならない。
実装上の落とし穴と境界事例を検証する。 貪欲はたいてい整列後の走査構造であるから、整列安定性・同点(tie)処理規則を明示してこそ再現性のある結果を得る。KruskalのUnion-Find経路圧縮の欠落、ハフマン木の頻度同点処理、活動選択の境界(終了=開始)条件など小さな実装誤りが最適性を壊しうるので、到達不能・空入力・同一重みのような境界事例に対する検証を設計に含める。
貪欲と他パラダイムの結合を積極的に活用する。 貪欲は単独で使われるのみならず、他技法の加速・初期化手段としても有用である。分枝限定は貪欲的上界で全探索を枝刈りし、局所探索(local search)とメタヒューリスティックは貪欲解を初期解として改善し、マトロイド共通部分のような拡張理論は貪欲の適用範囲を広げる。このように貪欲を全体最適化設計の一構成要素として見る統合的観点が実務の問題解決力を高める。
総合すると、貪欲アルゴリズムは「毎瞬間に最善を取り振り返らない」という単純な戦略であるが、その正当性は貪欲選択性と最適部分構造、さらにマトロイドという深い構造によって裏打ちされる。条件が成り立てば貪欲は最小全域木・ハフマン符号化・活動選択のように証明可能な最適解を多項式時間で提供し、困難問題では保証された近似比で実用的解を差し出す。技術士は問題の構造を正確に診断して貪欲・動的計画法・全探索のうち正しいパラダイムを選び、正当性を論証し、正確性と性能の均衡点で技法を結合する力量を備えねばならない。
参考資料
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to Algorithms" (3rd/4th ed.), Chapter 16: Greedy Algorithms, MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, 1952. https://ieeexplore.ieee.org/document/4051119
- J. Edmonds, "Matroids and the greedy algorithm", Mathematical Programming, 1971. https://link.springer.com/article/10.1007/BF01584082
- V. Chvátal, "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research, 1979. https://pubsonline.informs.org/doi/10.1287/moor.4.3.233
一言まとめ: 貪欲アルゴリズムは各段階で局所最適を選び取り消さない戦略であり、貪欲選択性と最適部分構造(さらにマトロイド)が成り立てば最小全域木・ハフマン符号化・分数ナップサックのように多項式時間で最適解を保証するが、条件が崩れれば誤った答えを出すため、正当性を交換論法で検証し動的計画法・全探索との境界を診断して正しいパラダイムを選ぶことが核心である。