貪欲法（グリーディ法）とは？

貪欲法（グリーディ法）の意味

各段階でそのときに最も良さそうな選択肢を選び続けることで、全体の解を得ようとするアルゴリズム設計手法。必ずしも最適解にたどり着くとは限らないが、計算が高速でシンプルという利点がある。

貪欲法（グリーディ法）の具体例

硬貨の種類が「1円・5円・10円・50円・100円・500円」のような特定の条件下では、常に使える最大額の硬貨から選んでいく貪欲法で最小枚数のお釣りを求められる。

貪欲法（グリーディ法）は試験でどう引っ掛けられる？

「高速だが最適解とは限らない」が核心で、最適解を保証するのは動的計画法や全探索。ただし常に不正解というわけではなく、ダイクストラ法のように条件（辺の重みが非負）を満たせば最適解になる例もある点に注意。

貪欲法（グリーディ法）と関連する用語

• 動的計画法