×
データ構造とアルゴリズム

貪欲法の解説(基本情報技術者シラバス用語)

貪欲法とは

貪欲法(どんよくほう)とは、問題を解決するアルゴリズムの設計手法の一つです。「グリーディ法」とも呼ばれます。この手法の特徴は、問題を解決していく各段階において、将来の影響を一切考えず、その時点で最も有利に見える選択(局所的な最適解)を繰り返し選んでいくことです。全体にとっての最終的な正解(全体最適解)が必ず得られるとは限りませんが、処理が非常にシンプルであり、計算速度が極めて速いという大きなメリットがあります。素早く「そこそこ良い答え」を見つけたい場合や、特定の条件を満たした問題に対して有効なアプローチとなります。

具体例