貪欲法とは
貪欲法（どんよくほう）とは、問題を解決するアルゴリズムの設計手法の一つです。「グリーディ法」とも呼ばれます。この手法の特徴は、問題を解決していく各段階において、将来の影響を一切考えず、その時点で最も有利に見える選択（局所的な最適解）を繰り返し選んでいくことです。全体にとっての最終的な正解（全体最適解）が必ず得られるとは限りませんが、処理が非常にシンプルであり、計算速度が極めて速いという大きなメリットがあります。素早く「そこそこ良い答え」を見つけたい場合や、特定の条件を満たした問題に対して有効なアプローチとなります。
具体例
お釣りとして渡す硬貨の枚数を最も少なくする問題を考えます。例えば、620円のお釣りを用意する際、貪欲法では「常にその時点で使える最も高価な硬貨を選ぶ」というルールに従います。まず500円玉を1枚選び、残り120円から100円玉を1枚選び、残り20円から10円玉を2枚選ぶことで、計4枚という最適な組み合わせを素早く見つけることができます。
もう少し詳しく
貪欲法の最大の強みは、そのアルゴリズムの直感的な分かりやすさと計算量の少なさにあります。毎回の選択において全ての選択肢を試す（全探索する）必要がなく、単に「今一番良さそうなもの」を選ぶだけで次のステップに進めるため、実行時間が劇的に短くなります。しかし、この「目先の利益だけを追求する」という性質が落とし穴になることもあります。例えば、お釣りの問題で「400円玉、300円玉、100円玉」があり、600円のお釣りを作る場合を想像してください。貪欲法ではまず最大の400円玉を選んでしまい、残りの200円を100円玉2枚で払うため合計3枚になりますが、本当の正解は300円玉を2枚使う（合計2枚）ことです。このように、貪欲法が必ずしも最良の答え（全体最適解）を導き出せるとは限らない問題が存在するため、アルゴリズムを採用する前に、その問題が貪欲法で正確に解ける性質を持っているかを数学的に証明・確認することが重要になります。
試験でのポイント
シラバスや試験では、貪欲法が「局所的な最適解を求めることで全体最適解を導こうとする手法」として定義づけられ、そのメリットと限界がよく問われます。試験対策としては、貪欲法で正しい答えが得られる代表的な問題（例えば、日本の硬貨を使ったお釣り計算や、クラスカル法などの最小全域木問題）と、正しい答えが得られない問題の区別をつけられるようにしておくことが重要です。また、動的計画法などの他のアルゴリズム手法との対比で出題されることが非常に多いです。貪欲法は「後戻りせず直感的に最良を選ぶ」、動的計画法は「過去の計算結果を利用して全体を考慮する」という違いを明確に説明できるようにしておきましょう。
関連する用語
貪欲法と比較されることが多いアルゴリズム設計手法として、過去の計算結果を記録して利用する動的計画法や、問題を小さな部分問題に分割して解く分割統治法があります。これらをセットで理解することで、アルゴリズムの全体像が見えてきます。