貪欲アルゴリズム

【どんよくあるごりずむ (greedy algorithm)】

離散最適化問題を解くにあたって, 局所的な情報のみに基づき, 目的関数の改善効果が最も顕著な方向に解を更新して行く探索法を貪欲アルゴリズムという. 通常, 貪欲アルゴリズムで最適解に達する保証はないが, 高速に近似解を生成するという点で実際的な手法である. ただし, グラフの最小木, より一般的にはマトロイドの基族や劣モジュラシステムの基多面体における線形目的関数の最適化などに際しては, 最適解が得られることが保証されている.