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

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

各段階で「その時点で最も良さそうな選択」を繰り返し積み重ねていくことで解を求める手法。必ずしも全体最適解が得られるとは限らないが、単純で高速に近似解・最適解を求められる場合がある。

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

おつりを最小枚数の硬貨で渡す問題では、額の大きい硬貨から使えるだけ使っていく貪欲法で最適解が得られることが多い（ただし硬貨の額の組み合わせによっては最適解にならない場合もある）。

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

「速いが最適解とは限らない」が要点で、常に最適解を与えるという選択肢は誤り。ただし例外があり、ダイクストラ法・クラスカル法（最小全域木）・ハフマン符号化は貪欲法でありながら最適解が保証される。硬貨のおつり問題も額の組み合わせ次第（例：1・4・5円で8円）では最適にならない。

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

• 動的計画法