過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

貪欲法

その時点で最もよい選択をする

貪欲法は、各段階で局所的に最もよいと考えられる選択を行い、通常はその選択を戻さずに解を組み立てる方法です。グリーディ法とも呼びます。手順が単純で効率的になる場合がありますが、どんな問題でも全体の最適解になるわけではありません。問題の性質によって正しさを示せることが重要です。

硬貨の例

金額に対して使える最大の硬貨から選ぶ方法を考えます。硬貨が1、3、4で金額が6なら、最大から選ぶと4+1+1で三枚です。しかし3+3なら二枚で済みます。この例は、局所的に大きい硬貨を選ぶことが、枚数を最小にするとは限らないことを示します。日常の硬貨でうまくいく経験を、任意の条件へ一般化しないようにします。

成功する問題の性質

ある選択を最初に採用しても最適解を失わず、残りが同じ形の問題になることなどを示せれば、貪欲な手順を正当化できます。区間を選ぶ問題や、最小全域木を求める一部の方法などに関係します。ただし、同じ「短いものを選ぶ」でも、何を短さとして比べるかによって結果が変わります。

動的計画法との比較

動的計画法は、部分問題の複数の可能性を結果として保存し、組み合わせて最適なものを求める方法です。貪欲法は選択肢を早く一つに絞るため、記憶量や計算量を抑えられることがあります。その代わり、選んだ後によりよい組合せがなくなるという根拠が必要です。速度だけを見て置き換えることはできません。

試験での確認

問題文で「その時点で最小の費用」「最も早く終了するもの」などの規則が示されたら、その規則どおりに一段ずつ選びます。最適性を問われる場合は、小さな反例を考えると誤った一般化を見つけられます。すべての候補を調べる全探索とも区別します。貪欲法という名称は悪い方法という意味ではなく、適用条件が合えば厳密な最適解を効率よく得られる手法です。条件と結論をセットで理解しましょう。

選択の基準を変えると別のアルゴリズムになります。最小費用、最大利益、最早終了など、問題が何を優先すると定めているかを正確に読み取ります。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

用語一覧

5件