貪欲法

2025年10月20日

貪欲法

英語表記: Greedy Algorithm

概要

貪欲法（Greedy Algorithm）は、アルゴリズムの設計パラダイムの一つであり、問題を解決する際に、その時点での最善（局所最適）と思われる選択肢を繰り返し選び続ける手法です。これは、各ステップで最も利益の大きい判断を下すことで、最終的にも全体として最適な解（大域最適）が得られることを期待する戦略です。計算コストを抑えながら迅速に解を求める必要がある場合に特に有効なアプローチとなります。

詳細解説

設計パラダイムとしての貪欲法

貪欲法は、「アルゴリズムと計算量」における「設計パラダイム」という分類に属します。設計パラダイムとは、特定の種類の問題を解決するためにアルゴリズムを組み立てる際の基本的な考え方や枠組みのことです。貪欲法が他のパラダイム（例えば、動的計画法や分割統治法）と決定的に異なるのは、過去の選択や将来の影響を深く考慮せず、「今、ここ」で最高の利益をもたらす選択に固執する点です。

このアプローチの最大の魅力は、その単純さと高速性です。各ステップでの判断が非常にシンプルであるため、多くの場合、非常に低い計算量（O(n)やO(n log n)など）で解を導出できます。これは、大量のデータを扱う現代のITシステムにおいて、非常に重要な性質です。

動作の仕組みと構成要素

貪欲法が適用される問題は、通常、複数の選択肢の集合から、制約を満たしつつ何らかの目的関数（最大化または最小化したい値）を最適化する部分集合を選ぶ、という形式をとります。

貪欲法による問題解決は、以下の主要なステップで構成されます。

選択（Selection）: 現在の状況において、最も「貪欲な」（最も利益が大きい、あるいはコストが低い）選択肢を選びます。この選択は、問題全体を考慮せず、現在のステップのみを見て行われます。
実行可能性の確認（Feasibility Check）: その選択肢が、問題の制約条件を満たしているかを確認します。
解の更新（Solution Update）: 選択肢を実行可能な場合、それを現在の部分的な解に加え、次のステップに進みます。

このプロセスを、すべての選択肢が尽きるか、問題が完全に解決されるまで繰り返します。

成功と失敗の分かれ道

貪欲法が成功し、大域最適解を導くためには、その問題が以下の二つの重要な性質を持っている必要があります。

貪欲な選択プロパティ（Greedy Choice Property）: 局所最適な選択をしても、それが必ず大域最適な解の一部となることです。つまり、最初の一歩で最高の選択をすれば、残りの問題も最適に解けるという保証が必要です。
最適部分構造（Optimal Substructure）: 問題の最適な解が、その部分問題の最適な解から構成できることです。

もし、これらの性質が満たされない場合、貪欲法は残念ながら失敗し、最適な解にたどり着くことができません。この単純さゆえに、貪欲法が適用できる問題の範囲は比較的限定的である、ということを理解しておく必要があります。この限定性が、動的計画法のように、より複雑な計算資源を投じてでも最適解を追求する別のアプローチが求められる理由なのです。

（※ここまでで約1,400文字）

具体例・活用シーン

貪欲法は、日常生活から複雑なネットワーク設計に至るまで、幅広いシーンで活用されています。

1. お釣りの問題（身近な例）

私たちが買い物をし、お釣りを受け取る際の動作は、最も身近な貪欲法の例です。

問題: 特定の金額のお釣りを、使用する硬貨の枚数が最小になるように支払う。
貪欲な選択: 常に、残りの金額に対して使える、最も大きな額面の硬貨（例：500円、100円、50円…）を選ぶ。
結果: 日本や多くの国の硬貨システムでは、この貪欲な選択が必ず最小枚数という大域最適解をもたらします。もし、額面が特殊な設定（例：1円、4円、5円）だった場合、貪欲法は失敗しますが、標準的な通貨では成功する、という点が非常に面白いですね。

2. スケジューリング問題（IT分野の基礎）

会議室の予約やCPUのタスク割り当てなど、限られた資源を効率的に使うスケジューリング問題も貪欲法の得意分野です。

問題: 複数の活動（タスク）の中から、互いに重複しない活動をできるだけ多く選ぶ。
貪欲な選択: 常に、最も早く終了する活動を選びます。
理由: 最も早く終わる活動を選ぶことで、残りの時間帯を最大限に空け、より多くの活動を後続として組み込む余地を確保できるからです。これも、局所的な最善が全体的な最善につながる典型的なケースです。

3. 短絡的な登山家（メタファー）

貪欲法の性質を理解するためのメタファーとして、「短絡的な登山家」の話を考えてみましょう。

ある登山家が山頂を目指しています。彼は非常に短気で、視野も狭いとしましょう。この登山家は、「今、自分の目の前にある道のうち、最も急勾配で、一歩で最も高く登れる道」だけを選び続けます。これが彼の貪欲な選択です。

彼は、一見するとどんどん高度を稼いでいるように見えますが、しばしば問題に直面します。

失敗の例: 目の前の急勾配な道を進んだ結果、巨大な崖や行き止まりにぶつかってしまい、結局、大幅に時間をロスしてしまいます。もし彼が最初の一歩で、少し遠回りでも緩やかな（局所的には劣る）道を選んでいれば、最終的に安全かつ迅速に山頂（大域最適解）にたどり着けたかもしれません。
成功の例: 幸運にも、彼が登っている山が単純な形状をしており、急勾配な道が常に山頂へと繋がっていた場合、彼は最速で登頂を果たします。

この登山家のように、貪欲法は「今」の利益に集中するため、問題の構造が単純で、目先の利益が将来の利益を損なわない場合にのみ、力を発揮するのです。複雑な問題に対しては、より慎重な計画（動的計画法など）が必要になることがよくあります。

（※ここまでで約2,200文字）

資格試験向けチェックポイント

貪欲法は、「アルゴリズムの基本性質」を問う問題として、IT Passportから応用情報技術者試験まで幅広く出題されます。特に、他のアルゴリズムとの比較や、適用可能性を問う問題が頻出します。

| 項目 | ITパスポート・基本情報技術者試験レベル | 応用情報技術者試験レベル |
| :— | :— | :— |
| 定義と特徴 | 「局所最適解の積み重ねが大域最適解になることを期待する手法」であることを理解する。高速だが、常に最適解を得られるわけではない、という性質を把握する。 | 貪欲法が適用できる問題（例：お釣りの問題、スケジューリング）と、適用できない問題（例：一般のナップサック問題）の具体的な構造の違いを理解する。 |
| 比較対象 | 動的計画法（Dynamic Programming）との違いが最重要です。貪欲法が「一度決めたら戻らない」のに対し、動的計画法は「すべての部分問題を解いて最適解を導く」という違いを説明できるようにする。 | 貪欲法の成功の条件である「貪欲な選択プロパティ」と「最適部分構造」の有無を判断させる問題が出題されます。 |
| 具体的な適用 | 最小全域木（Minimum Spanning Tree: MST）を求めるクルスカル法（Kruskal’s Algorithm）やプリム法（Prim’s Algorithm）が、エッジの重みが最小のものから選ぶという貪欲な選択に基づいていることを知る。 | ハフマン符号化（Huffman Coding）が、出現頻度の低い要素から結合するという貪欲なアプローチを採用していることを確認する。また、分数ナップサック問題（Fractional Knapsack Problem）では成功するが、0/1ナップサック問題では失敗する理由を深く理解する。 |
| 出題パターン | 「次のうち、貪欲法を採用しているアルゴリズムはどれか」や「貪欲法の欠点として正しいものはどれか」といった知識問題。 | 特定の問題設定を与えられ、貪欲法を適用した際の解が最適解であるかどうかを判断させる応用問題。特に、最短経路問題（ダイクストラ法など）が貪欲的な要素を持つことを理解しておく必要があります。 |

資格試験において、貪欲法は「高速だがリスクがある」という設計パラダイムとしての立ち位置を問われることが多いです。「アルゴリズムの基本性質」を理解する上で、計算効率と解の正確性のトレードオフを学ぶための最高の教材と言えるでしょう。

（※ここまでで約2,900文字）