貪欲法とは（全体像）
貪欲法とは、各段階で、その時点でいちばん良さそうな（局所的に最適な）選択をして、それをくり返していく設計技法のことだ。「グリーディ法」とも呼ばれる。グリーディ（greedy）は英語で「欲ばりな」という意味だ。
身近な例でいうと、お釣りを、できるだけ少ない枚数で払うとき、大きい硬貨から順に選んでいくようなやり方だ。その場その場で、一番得そうな選択をしていく。
ここで一番のポイント。貪欲法は、単純で速いのが強み。でも、目先で一番良い選択をくり返しても、全体として最善になるとは限らない。「貪欲法は、どんなときも必ず最適な答えを出す」と思い込むと誤りになる。
詳しく：局所最適と、動的計画法との違い
ここが心臓部。ポイントを表で押さえよう。
貪欲法のポイント
| 項目 | やさしい意味 |
|---|---|
| 方針 | 各段階で、その時点いちばん良い選択をする |
| 強み | 単純で速い |
| 注意 | 常に全体最適になるとは限らない |
| DPとの違い | 貪欲は目先の選択、DPは部分問題を記憶して全体を考える |
貪欲法の強みは、単純で速いこと。複雑に全部を調べなくても、その場で良さそうな選択をするだけだから、手早く答えに近づける。
ただし、注意点もある。目先の最善が、全体の最善とは限らない。だから、貪欲法でうまくいく問題と、いかない問題がある。なお、動的計画法（DP）とは違う。貪欲法は「目先の選択」をするのに対し、動的計画法は「部分問題の結果を記憶して、全体として最適を目指す」。この対比はよく問われる。
わかりやすく言い換えると
身近なたとえで整理しよう。
貪欲法は、「その場その場で、一番良さそうなものを選んでいく」イメージ。お釣りを大きい硬貨から選ぶような、欲ばりな選び方だ。
「全体最適とは限らない」というのは、目先の最善をくり返しても、全体ではもっと良い答えがあるかもしれないこと。要するに、つねに最適とは言えない。
「動的計画法との違い」は、貪欲法は目先の選択、動的計画法は部分問題を記憶して全体を考えること。つまり、考え方の向きが違う。
試験のツボ
🔴 一番出る：貪欲法の方針
①各段階で、その時点いちばん良い（局所最適な）選択をする
②それをくり返して、答えに近づける
🔴 次に出る：全体最適とは限らない
①単純で速いが、常に全体最適になるとは限らない
②目先の最善が、全体の最善とは限らない
🟡 押さえると安定：動的計画法との違い
①貪欲法は「目先の選択」
②動的計画法は「部分問題を記憶して、全体を考える」
よくある間違い
①「貪欲法は、どんなときも必ず最適な答えを出す」→ ✗ 各段階で局所最適を選ぶだけ。全体最適になるかは、問題による。
②「貪欲法と動的計画法は、同じ方法だ」→ ✗ 貪欲法は目先の選択、動的計画法は部分問題を記憶して全体を考える。向きが違う。
③「貪欲法は、すべての組み合わせをくまなく調べる方法だ」→ ✗ 逆で、全部を調べず、その場で良さそうな選択をする。だから単純で速い。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（貪欲法の正体）
貪欲法に関する次の記述のうち、最も適切なものはどれか。
- 社員の出退勤を記録して、毎月の給与を計算するためのしくみである
- 各段階で、その時点でいちばん良い選択をくり返す設計技法である
- 取引先へ毎月の請求書を郵送する、決まった事務作業のことを指す
- 完成したシステムを宣伝して、より多く売るための広告活動である
解答は 2 だぱん。
貪欲法は、各段階で、その時点いちばん良い選択をくり返す設計技法なんだぱん。お釣りを大きい硬貨から選ぶようなイメージだぱん。
選択肢1は給与計算、選択肢3は請求書の事務、選択肢4は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のしくみではない |
| 2 | ✓ | その時点いちばん良い選択をくり返すで正しい |
| 3 | ✗ | 請求書の事務の話 |
| 4 | ✗ | 広告活動ではない |
オリジナル問題2（全体最適とは限らない）
貪欲法の特徴に関する次の記述のうち、最も適切なものはどれか。
- 社員の給与を計算するときだけ、使える方法だとされているものだ
- 取引先へ請求書を郵送するときだけ、使える方法だとされているのだ
- すべての場合で、必ず全体最適な答えを出すとされているものである
- 単純で速いが、常に全体で最適になるとは限らないものなのである
解答は 4 だぱん。
貪欲法は、単純で速いが、常に全体最適になるとは限らないんだぱん。目先の最善が、全体の最善とは限らないからだぱん。
選択肢1の給与、選択肢2の請求書、選択肢3の「必ず全体最適」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のときだけではない |
| 2 | ✗ | 請求書のときだけではない |
| 3 | ✗ | 必ず全体最適とは限らない |
| 4 | ✓ | 単純で速いが全体最適とは限らないで正しい |
オリジナル問題3（動的計画法との違い）
貪欲法と動的計画法（DP）の違いに関する次の記述のうち、最も適切なものはどれか。
- 貪欲法は目先の選択、DPは部分問題を記憶して全体最適を考える
- 社員の給与の計算しだいで、違いが決まるとされているものである
- 取引先への請求書の枚数しだいで、違いが決まるとされているのだ
- 貪欲法と動的計画法は、まったく同じ方法だとされているものである
解答は 1 だぱん。
違いは、貪欲は目先の選択、DPは部分問題を記憶して全体を考えることなんだぱん。考え方の向きが違うんだぱん。
選択肢2の給与、選択肢3の請求書、選択肢4の「同じ方法」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 貪欲は目先・DPは全体で正しい |
| 2 | ✗ | 給与計算で決まるのではない |
| 3 | ✗ | 請求書の枚数で決まるのではない |
| 4 | ✗ | 同じ方法ではない |
まとめ
押さえどころ
- 🔴 貪欲法（グリーディ法） ＝ 各段階で、その時点いちばん良い（局所最適な）選択をくり返す設計技法。
- 🔴 全体最適とは限らない ＝ 単純で速いが、目先の最善が全体の最善とは限らない。
- 🟡 動的計画法との違い ＝ 貪欲は目先の選択、動的計画法は部分問題を記憶して全体を考える。
次に学ぶ
- 動的計画法（DP） ── 部分問題を記憶して全体最適を目指す技法。貪欲法と、考え方の向きを比べると分かりやすい。
- 計算量（ビッグオー記法） ── アルゴリズムの速さの目安。貪欲法は単純で速いのが強み。
執筆: SikakuQuest編集部