貪欲法（グリーディアルゴリズム）とは？基本概念と代表的な応用問題を解説

貪欲法（どんよくほう、Greedy Algorithm）は、与えられた問題に対して最適解を達成することを目指すアルゴリズム設計手法の一つです。このアプローチでは、各段階で解の候補領域の中から意思決定を行い、その時点で最も有望に見える選択肢——つまり「今すぐ得られる利益が最大となる解」— を貪欲に選び取っていきます。

貪欲法の基本的な考え方

貪欲法は「局所的な最適解」を積み重ねることで、結果的に全体の最適解（大域的最適解）に到達することを目指します。しかし、すべての問題でそれが成功するわけではありません。一般的には、貪欲法による局所的な選択の積み重ねは、必ずしも大域的な最適解を保証しないという点に注意が必要です。

貪欲法が正しく機能するためには、次のような性質が問題に備わっていることが望まれます。

• 貪欲選択性质（Greedy Choice Property）：その場での最良の選択が、全体の最適解につながること
• 最適部分構造（Optimal Substructure）：問題の最適解が、部分問題の最適解から構成できること

これらの性質を満たす問題（例：最小全域木問題やハフマン符号化など）では、貪欲法は非常に効率的かつ強力な解法となります。一方、満たさない問題では動的計画法などの別の手法を検討する必要があります。

このセクションで扱う主なトピック

以下は、貪欲法の理解を深めるために学習すべき代表的なアルゴリズムと応用問題の一覧です。

• 活動選択問題（Activity Selection Problem） — 重なりなく実行できる活動の最大数を選ぶ問題
• ダイクストラ法（隣接リスト表現） — グラフ上の単一始点最短経路を求める効率的な実装
• ダイクストラの最短経路アルゴリズム — 重み付きグラフにおける最短経路探索の基本手法
• ハフマン符号化アルゴリズム — データ圧縮に用いられる可変長符号の構築手法
• ソート済み入力に対する効率的なハフマン符号化 — 入力が整列されている場合の高速化技法
• 締め切り付きジョブスケジューリング問題 — 期限制約のもとで利益を最大化するスケジュール決定問題
• クラスカルの最小全域木アルゴリズム — 辺を重み順に追加していく最小全域木構築法
• 最小硬貨両替問題（Minimum Coin Change Problem） — 目標金額を作るのに必要な硬貨の最小枚数を求める問題
• 最小プラットフォーム数問題 — 列車の到着・出発時刻から必要なホームの最小数を求める問題
• プリムの最小全域木アルゴリズム — 頂点を一つずつ木に成長させていく最小全域木構築法
• プリム法（隣接リスト表現） — 隣接リストを用いたプリム法の効率的な実装
• 分数ナップサック問題（Fractional Knapsack Problem） — アイテムを分割して詰められるナップサック問題で、貪欲法が厳密な最適解を保証する好例

これらの問題を通じて、貪欲法がどのような場面で有効であり、どこに限界があるのかを体系的に学ぶことができます。各トピックの詳細な解説もぜひ参考にしてください。