貪欲アルゴリズム

OR事典

貪欲アルゴリズム

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

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

「OR事典」の他の用語

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

ウィキペディア

貪欲法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/14 23:52 UTC 版)

貪欲法（どんよくほう、英: greedy algorithm）は、アルゴリズムの一種、欲張り法（よくばりほう）、グリーディ算法（グリーディさんぽう）ともいう。