貪欲法とは（全体像）
貪欲法は、「今いちばんよい選択」をくり返して答えに近づけるアルゴリズムの作り方。全体を見渡さず、各段階で目の前の最善（局所最適）を選んでいく。
身近な例がお釣り。500円玉から順に、できるだけ大きな硬貨で払えば枚数が最少になる（日本の硬貨ではこのやり方で最適になる）。このように「大きいものから取る」のが貪欲法のイメージだ。
ただし注意したいのは、この方法がいつも最適とは限らないこと。目の前の最善を選び続けた結果、全体では損をする問題もある。だから貪欲法は「速いが、使える問題を選ぶ」手法だ。
詳しく：成功例と失敗例、DPとの違いだけ覚えれば戦える
ここが記事の心臓部。貪欲法は、ある2つの性質がそろう問題でだけ最適解を保証する。
貪欲法が最適になる2つの条件
| 性質 | 意味 |
|---|---|
| 貪欲選択性 | 目の前の最善を選び続ければ、全体の最善に届く |
| 最適部分構造 | 小さな問題の最善が、大きな問題の最善の一部になる |
この2つがそろう問題と、そろわない問題がある。代表例を押さえておこう。
貪欲法の成功例と失敗例
| 例 | 結果 | |
|---|---|---|
| 最適になる | 最小全域木・ハフマン符号化・ダイクストラ法 | 貪欲で最適解 |
| 最適にならない | 0/1ナップサック問題・巡回セールスマン問題 | 近似解どまり |
そして、よく対比されるのが動的計画法（DP）。DPは「すべての小さな問題を試して結果を覚えておく」やり方で、貪欲法より広い範囲で最適解を出せるが、そのぶん計算は重い。
貪欲法と動的計画法（DP）の違い
| 貪欲法 | 動的計画法（DP） | |
|---|---|---|
| 選び方 | 目の前の最善だけ | すべての小問題を試す |
| 計算量 | 小さい（速い） | 大きい（重い） |
| 最適解 | 一部の問題だけ保証 | 広い範囲で保証 |
つまり、貪欲法は「速いが使える問題が限られる」、DPは「重いが広く最適を出せる」という関係。どちらを使うかは問題しだい、というわけだね。
わかりやすく言い換えると
要するに、貪欲法は「先を読まず、今いちばんよい手を取り続ける」やり方だ。
①得意なこと … 計算が軽くて速い（お釣りを大きい硬貨から払うイメージ）
②苦手なこと … 目の前の最善が裏目に出る問題では、最適にならない
③DPとの違い … 貪欲は局所だけ・DPは全部試す。DPのほうが広く最適だが重い
「最適保証は一部の問題だけ」という線を覚えておくと、ひっかけ問題に強くなる。
試験のツボ
🔴 一番出る：貪欲法は局所最適を選び続ける
①各ステップで今いちばんよい選択をする
②計算は軽いが、最適解になるとは限らない
🔴 次に出る：最適になる成功例
①最小全域木（クラスカル法・プリム法）
②ハフマン符号化・ダイクストラ法
🟡 押さえると安定：動的計画法（DP）との違い
①貪欲は局所だけ・DPは全部の小問題を試す
②DPは広く最適を出せるが計算が重い
よくある間違い
①「貪欲法はどんな問題でも最適解を保証する」→ ✗ 最適になるのは一部の問題だけ。一般には近似解どまり。
②「貪欲法と動的計画法は同じもの」→ ✗ 貪欲は目の前の最善だけ、DPはすべての小問題を試して覚える。
③「ナップサック問題は貪欲法でいつも最適になる」→ ✗ 0/1ナップサックは貪欲では最適にならない代表例。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（貪欲法の考え方）
貪欲法の考え方に関する次の記述のうち、正しいものはどれか。
- 貪欲法はすべての選択肢を最後まで試してから、いちばんよい組合せを選ぶやり方だ
- 貪欲法は選択をいっさい行わず、入力された順番のまま結果を出力するだけの方法だ
- 貪欲法は各ステップで今いちばんよい選択を続けるやり方で、計算が軽くて速いのだ
- 貪欲法は毎回わざと悪い選択をして、わざと遅い答えを出すために使う手法である
解答は 3 だよ。
貪欲法は各ステップで今いちばんよい選択を続けるやり方で、計算が軽くて速いんだ。お釣りを大きい硬貨から払うイメージだよ。
選択肢1は「すべて試す」で動的計画法に近い説明。選択肢2の「選択しない」、選択肢4の「わざと悪く」はどちらも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | すべて試すのはDPに近い |
| 2 | ✗ | 各ステップで選択する |
| 3 | ✓ | 局所最適を選び続けて速い |
| 4 | ✗ | 今最良の選択をする |
オリジナル問題2（最適になるかどうか）
貪欲法の最適性に関する次の記述のうち、正しいものはどれか。
- 貪欲法はあらゆる問題で必ず最適解を出すので、近似解で終わることはありえない
- 貪欲法は最小全域木などでは最適になるが、一般には近似解にとどまることもある
- 貪欲法はどんな問題でも最適にならず、正しい答えに近づくことすらできない手法だ
- 貪欲法が最適になるのは巡回セールスマン問題だけで、ほかの問題では役に立たない
解答は 2 だよ。
貪欲法は最小全域木などでは最適になるけど、一般には近似解にとどまることもあるんだ。最適になるかは問題しだいだよ。
選択肢1の「必ず最適」、選択肢3の「近づけない」、選択肢4の「TSPだけ最適」はどれも誤りだよ（TSPは貪欲が苦手な例）。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 一般には最適を保証しない |
| 2 | ✓ | 最適になる問題とならない問題がある |
| 3 | ✗ | 最適になる成功例がある |
| 4 | ✗ | TSPは貪欲が苦手な例 |
オリジナル問題3（動的計画法との違い）
貪欲法と動的計画法（DP）の違いに関する次の記述のうち、正しいものはどれか。
- 貪欲法は目の前の最善だけを選び、DPはすべての小さな問題を試すので最適に強い
- 貪欲法はすべての小問題を試し、DPは目の前の最善だけを選ぶという関係である
- 貪欲法もDPもまったく同じ手法で、計算量にも最適性にも違いは出ないものである
- 貪欲法は計算が重く、DPは計算が軽いという点だけが両者の唯一の違いとされる
解答は 1 だよ。
貪欲法は目の前の最善だけを選び、DPはすべての小問題を試すんだ。だからDPのほうが広く最適を出せるけど、そのぶん計算は重いよ。
選択肢2は貪欲とDPが逆。選択肢3の「同じ手法」、選択肢4の「重い・軽いが逆」も誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 貪欲＝局所・DP＝全小問題で最適に強い |
| 2 | ✗ | 貪欲とDPが逆 |
| 3 | ✗ | 計算量も最適性も違う |
| 4 | ✗ | 貪欲が軽く、DPが重い |
まとめ
押さえどころ
- 🔴 貪欲法の考え方 ＝ 各ステップで今いちばんよい選択を続ける。軽くて速いが最適とは限らない。
- 🔴 成功例 ＝ 最小全域木・ハフマン符号化・ダイクストラ法では最適になる。
- 🟡 DPとの違い ＝ 貪欲は局所だけ、DPは全部試す。DPは広く最適だが計算が重い。
次に学ぶ
- 動的計画法DP ── 貪欲法と対比される手法。すべての小問題を試して最適を出すしくみを押さえると違いが腑に落ちる。
- グラフ理論 ── 最小全域木やダイクストラ法の舞台になる、点と線でつながりを表す考え方。
執筆: SikakuQuest編集部