貪欲法とは、問題解決の各ステップにおいてその場での最適な選択を繰り返すことで、全体としての最適解に近づけようとするアルゴリズム手法です。計算コストが低く、AIの探索や機械学習の様々な決定プロセスで広く応用されていますが、局所最適解に陥る弱点もあります。
貪欲法とは
一言でいうと貪欲法とは、「目の前の最も良い選択を積み重ねて全体を解こうとするアルゴリズム」のことです。
詳しく解説
貪欲法（グリーディーアルゴリズム）は、計算の各段階でその時点で最も得になる選択肢を選んでいく手法です。将来の先読みをせず、その場の最適解を直感的に選ぶため、プログラムの処理速度が非常に速いという特徴があります。AI分野では、決定木学習の構築や強化学習の方策最適化、経路探索などの効率化において重要な役割を果たしています。
具体例・使われ方
例えば、AIがカーナビやゲームのマップ上で最短経路を探索する際、現在地から最も距離が縮まる隣接ノードを次々と選んで進む処理に貪欲法的なアプローチが使われます。また、機械学習の決定木アルゴリズムでは、各分岐で情報の不確実性を最も減らせる特徴量をその都度選択する際に用いられます。
似た用語との違い
動的計画法（DP）やバックトラッキングなどの網羅的探索と比較されます。動的計画法が過去の計算結果を保存しつつすべての可能性を考慮して大域的最適解を確実に見つけるのに対し、貪欲法は過去の選択を振り返らずその場の判断だけで進むため、正確性よりも計算の速さを重視する点で異なります。
注意点
貪欲法は目の前の利益を優先するため、全体を見渡したときの真の最適解（大域的最適解）にたどり着けず、途中で局所最適解で止まってしまうという重大な限界があります。そのため、AIに適用する際は、問題の性質が貪欲法で解けるもの（マトロイド構造など）であるかを見極める注意が必要です。