グリーディーアルゴリズム（貪欲法）は、最適化問題を解く際にその場その場で最も良い選択を積み重ねる手法です。将来の結果を考慮せず目先の利益を優先するため計算が速い特徴があり、機械学習の決定木学習などで広く使われています。
グリーディーアルゴリズムとは
一言でいうとグリーディーアルゴリズムとは、将来の全体的な最適性ではなく、その瞬間における最も魅力的な選択肢を繰り返し選ぶことで問題の解決を図る効率的なアルゴリズムです。
詳しく解説
グリーディーアルゴリズムは日本語で「貪欲法」とも呼ばれます。複雑な最適化問題において、すべての組み合わせを網羅的に探索すると膨大な時間がかかるため、この手法では各ステップで最も効果的と思われる局所的な最適解を選んでいきます。AIや機械学習の分野では、決定木学習の構築において分割基準を決定する際などにこの考え方が応用されており、計算量を大幅に削減しながら実用的な精度のモデルを得るために重要な役割を果たしています。
具体例・使われ方
具体的な利用例として、機械学習における決定木学習があげられます。決定木のノードを分割する際、その時点での情報利得や不純度の減少量が最大になる特徴量と閾値を貪欲に選択していくことで、効率的に木構造を構築します。また、経路探索問題やナップサック問題の近似解を求める際にも用いられます。
似た用語との違い
動的計画法（Dynamic Programming）と比較されることが多いです。動的計画法が過去の選択結果と将来への影響をすべて考慮して大域的な最適解を確実に導き出すのに対し、グリーディーアルゴリズムは将来を考慮せずその場限りの選択を行うため、計算速度は速いものの全体最適を保証できないという明確な違いがあります。
注意点
目先の最適解を積み重ねるだけであるため、必ずしも大域的最適解（真の最適解）にたどり着くとは限らない点が最大の限界です。問題の性質によっては非常に精度の低い結果になる場合があるため、適用する問題が貪欲選択性質や最適部分構造を持っているかを確認する必要があります。