greedy algorithm

OR事典

欲張りアルゴリズム

読み方：よくばりあるごりずむ
【英】：greedy algorithm

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

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

貪欲アルゴリズム

読み方：どんよくあるごりずむ
【英】：greedy algorithm

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

「OR事典」の他の用語

グラフ･ネットワーク：	組合せ最適化問題  被覆  複雑ネットワーク  貪欲アルゴリズム  輸送問題  辺分離定理  辺連結度
組合せ最適化：	組合せ最適化問題  組合せ的爆発  計算の複雑さ  貪欲アルゴリズム  連結度  集合被覆問題  離散最適化問題