【どんよくほう】
貪欲法（グリーディアルゴリズム） とは？
最終更新:
💡 「今一番いいもの」を選び続ける
各段階で、その時点で最善と判断した選択を積み重ねるアルゴリズム設計手法。選び方と問題の条件によっては最適解を得られるが、常に全体の最適解になるわけではない。
📌 このページのポイント
- 各段階で局所的な最善を選び、解を構築する
- 最適解を保証するには、問題と選択規則に合った根拠が必要
- 硬貨の選び方や、重ならない活動の選択が具体例
- 動的計画法との優劣や速さは、問題と実装による
ひよこ 具体例で教えて？
ペンギン先生 お釣りを少ない枚数の硬貨で返す問題なら、残額を超えない最大の硬貨を選び続ける方法があるよ。でも、硬貨の種類によっては最適にならない。各段階で何を最善とするかが重要なんだ。
ひよこ 最大の硬貨を選ぶと失敗する例は？
ペンギン先生 架空の1・3・4円の硬貨を何枚でも使えて、6円を返すとしよう。最大から選ぶと4＋1＋1で3枚。でも3＋3なら2枚だから、貪欲な選択が全体の最善とは限らないと分かるね。
ひよこ いつ最適解になるの？
ペンギン先生 選んだ規則が最適解を壊さないことを示せる場合だよ。たとえば開始と終了が固定された活動から、重ならない活動の件数を最大にするなら、終了が早い活動から選ぶ方法が最適になる。締切の順に並べる別の問題とは区別しよう。
ひよこ 動的計画法より必ず速い？
ペンギン先生 必ずではないよ。単純な貪欲法で解ける問題もあるけど、並べ替えが必要な場合もある。計算量と正しさは個々の問題で確かめるんだ。貪欲法が失敗したから動的計画法だけが唯一の解法、というわけでもないよ。
ひよこ 正しい選び方か、どう確かめるの？
ペンギン先生 小さな入力で全候補と比べ、反例を探すと役立つよ。ただし例で成功しただけでは全入力の証明にはならない。選択を置き換えても最適性を失わないと示すなど、問題の条件に沿って理由を説明するんだ。
もっと詳しく知りたい人へ
終了が早い活動から選べば、報酬の合計も最大になる？
必ずしもならない。この規則が最適なのは、開始・終了が固定された活動から重ならないものを選び、件数を最大化する問題。報酬などの重みの合計が目的なら、早く終わる低報酬の活動より、長い高報酬の活動を選ぶ方がよい場合がある。
まとめ：ざっくりこれだけ覚えればOK！
「貪欲法」って出てきたら「各段階でその時点の最善を選ぶアルゴリズム」と思えればだいたいOK！
📖 おまけ：英語の意味
「Greedy Algorithm」 ＝ 貪欲アルゴリズム
💬 Greedy（欲張りな）。目の前の最善をGreedy（貪欲）に取り続けるアプローチだよ