貪欲法の考え方
貪欲法は、問題を解く各ステップで「その時点で最も良さそうな選択」を行い、その選択を積み重ねて解を構成するアルゴリズム設計の考え方です。正解は「各ステップでその時点の最善に見える選択を積み重ねる」です。 (選択肢2が正しい)
正解の理由
貪欲法は、問題を解く各ステップで「その時点で最も良さそうな選択」を行い、その選択を積み重ねて解を構成するアルゴリズム設計の考え方です。正解は「各ステップでその時点の最善に見える選択を積み重ねる」です。
仕組み・頻出ポイント
- 局所的に最適な選択が、問題全体の最適解につながる性質がある場合に有効です。
- 活動選択問題、ハフマン符号、最小全域木の一部アルゴリズムなどが代表例です。
- 必ず大域的最適解を保証するわけではないため、適用条件の確認が重要です。
G検定で覚えるべきこと
貪欲法は「速そうだから何となく選ぶ」方法ではありません。正しさを保証するには、貪欲選択性や最適部分構造のような性質を考えます。ナップサック問題でも、分割可能な場合は貪欲で解けますが、0-1ナップサックでは動的計画法が必要になるなど、似た題材で解法が変わる点が試験で狙われます。
他の選択肢の評価
- 選択肢1: 全列挙は総当たり探索です。確実ですが組合せ爆発を起こしやすく、貪欲法とは発想が異なります。
- 選択肢2: 正解です。局所最適な選択を逐次採用する点が貪欲法です。
- 選択肢3: ランダム生成を続けるのは乱択アルゴリズムやメタヒューリスティックの一部で、貪欲法の定義ではありません。
- 選択肢4: 勾配計算は連続最適化やニューラルネットワーク学習の話です。
実務での見方
実務では、貪欲法は説明しやすく高速な近似・構成手法として使われることがあります。ただし、局所的に良い判断が後で不利に働く問題もあるため、最適性が必要な場面では反例や証明を確認します。AIや最適化では、速度と解の質のバランスを取る考え方として重要です。
確認観点
確認観点としては、その場の最善が後の選択肢を狭めないか、最適解を保証できる構造があるかです。高速に答えを作れる利点と、最適性を失う危険をセットで覚えると判断しやすくなります。
結論として、この問題では「用語の定義」だけでなく、どの前提で使えるのか、どの誤解を避けるべきか、実務では何を確認するのかまで結びつけて理解することが重要です。