1 貪欲法の概要
貪欲法（ぐうしょほう）とは、最適化や意思決定の問題に対して、各段階で「その時点で最も良い選択」を採用し、逐次的に解を組み立てるアルゴリズム設計方針を指す。設計の中心は、局所的な判断基準（スコア、優先度、コスト増減など）を定め、それを手順として確定させることにある。
貪欲法は実装が簡潔になりやすい一方で、局所最適が常に全体最適へ結びつくとは限らない。したがって「なぜその選択が正しいと言えるのか」を問題の性質にもとづいて検討することが実務上の要点になる。判断の根拠が確立できる問題では、貪欲法は強い計算効率と分かりやすい構造を提供する。
1.1 基本概念
貪欲法を理解する鍵は、「各ステップでの意思決定」と「その意思決定が未来の選択の余地に与える影響」をどう扱うかにある。局所の良さを基準に選ぶ点は共通だが、どのような情報を状態として保持し、いつ終了するかによって振る舞いが変わる。
1.1.1 局所最適と全体最適
局所最適とは、ある段階で候補を並べたときに、評価規準のもとで最良と判定される選択のことをいう。全体最適は、問題全体に対して最適目的（最小化・最大化）を満たす解のことだが、局所最適が全体最適を保証するには、問題側の構造が必要になる。
たとえば、局所で得をしても後続で選択の自由が失われる場合、全体としては不利になることがある。逆に、ある条件下では局所の選択が将来に害を与えず、むしろ最適解へ変形できるため、全体最適が成立する。
1.1.2 解を段階的に構成する考え方
貪欲法では、部分解が積み上がる形で最終解が得られる。典型的には、最終目的に関連する「要素（選択対象）」を順に確定し、次の段階で残りの未確定部分について同様の判断を行う。
この段階的構成は、実装上は「選んだものを結果に追加し、選択可能な候補集合を更新する」という形で表現される。停止条件は、候補が尽きる、目的が達成される、ある制約を満たすことが不可能になるといった形で定義されることが多い。
1.2 代表的な処理手順
貪欲法の処理手順は、問題の種類に応じて具体化されるが、概念的には共通の枠組みで整理できる。候補の集合を定義し、各手順で選択規則を適用し、状態を更新しながら停止まで繰り返す。
1.2.1 選択ルールの定義
選択ルールとは、各段階でどの候補を選ぶかを決める基準である。目的関数に対する増分（削減量、利益、コスト差など）を計算し、最も有望な候補を選ぶ形が一般的だが、問題によっては制約充足性を優先し、一定の候補のみを比較する方式もある。
選択ルールを定めるときのポイントは、評価規準が局所的に計算可能であること、かつ正当化に必要な性質（貪欲選択特性など）を満たしうることを意識する点にある。
1.2.2 状態の更新と停止条件
選択後は、次の段階での比較が正しく行えるように状態を更新する。状態には、すでに選んだ要素の集合、制約に関する残り情報、到達済み領域などが含まれることが多い。
停止条件は、解が完成したことを判定できる条件として定義される。たとえば、一定数の要素を選び終えた、ある目的値が所定の基準に達した、これ以上候補を選んでも制約を破るため進めない、といった判断が該当する。
1.3 貪欲法が向く問題
貪欲法が有効になりやすいのは、局所の選択が将来の最適性を損なわないという構造を持つ問題である。逆に、将来への影響が複雑で、局所の決定が取り返しのつかない形で制約を壊すタイプの問題では、貪欲法単独の成立が難しいことが多い。
1.3.1 構造が単純な問題
要素の選択が互いに独立に近く、選んだ後の選択可能範囲が単調に減少するような問題は、貪欲の枠組みに適合しやすい。たとえば、順序付きの選択で「早く終わるほど得である」など、比較規準が明確な場面では適用が容易になる。
また、目的関数が選択の積み上げとして扱いやすい場合も適性が高い。部分決定が単純に合成できると、正当化のための理屈も組み立てやすい。
1.3.2 追加制約が限定的な問題
制約が強すぎると、局所の良さが容易に全体の破綻へつながる。貪欲法に向くのは、制約が局所的な検査で扱えたり、選択後の残り問題が同型になったりする場合である。
制約が限定的とはいえ、完全に任意ではなく、選択ルールの比較が制約を織り込めることが重要になる。加えて、状態更新が効率よく実行できるような形で制約が表現されると、実務上の利点が増す。
2 数学的背景と正当化の考え方
貪欲法の成否は、アルゴリズムそのものではなく、その正当化が可能かに左右される。一般に、貪欲選択が正しい根拠として「特性」や「最適部分構造」、あるいは証明技法として「交換論法」や帰納的議論などが用いられる。
2.1 最適性の根拠
最適性の根拠とは、貪欲に従うことが全体最適を損ねないことを論理的に保証する性質である。実装の正しさは、選択ルールがその性質に適合することから導かれる。
2.1.1 貪欲選択特性
貪欲選択特性とは、「最適解の中には、ある段階で貪欲が選ぶ要素と同じ（あるいは等価な）選択を含む」ことが示せる性質を指す。これが成立すると、最初の選択を貪欲に固定しても最適解への道が閉ざされない。
この性質は、局所での比較が単なる経験則ではなく、最適解の形を制約する論理として働くことを意味する。成立の示し方は問題ごとに異なるが、典型的には「貪欲で選ぶものが最適解にも現れる」ことを示す形になる。
1.2 最適部分構造
最適部分構造とは、「問題全体の最適解から取り出した残りの部分問題が、その部分でも最適である」または「残り問題が同種の最適化として扱える」性質である。貪欲法では、最初の判断に続いて次の段階でも同様に最適化できることが重要になる。
ただし注意点として、最適部分構造があるからといって必ず貪欲が正しくなるわけではない。貪欲選択特性と組み合わさることで、逐次決定が全体最適に整合する形になる。
2.2 代表的な証明手法
貪欲法の正しさを示す証明にはいくつかの型がある。ここでは、頻出する交換論法と帰納的議論を中心に、考え方の骨格をまとめる。
2.2.1 交換論法
交換論法は、最適解の中に貪欲の選択が現れるように、解の要素を入れ替えて（または置き換えて）目的値を保つ・改善することで、貪欲が矛盾なく最適解へ含められることを示す方法である。
典型的な流れとしては、任意の最適解を取り、貪欲の最初の選択と一致しない部分がある場合に、その部分を貪欲選択で置き換える。その際に目的値が悪化しないことを論証し、最適性を損なわずに貪欲の選択を含む最適解を構成する。
2.2.2 帰納的議論
帰納的議論では、問題のサイズや段階数を基準に、貪欲が正しいことを段階的に示す。多くの場合、最初の段階で貪欲が選ぶ要素を固定し、その後の残り問題に対して同様の主張を帰納法で適用する。
成立には、残り問題が同じ種類の最適化として再現されること、そして最初の選択を固定しても最適性が保たれることが必要になる。よって、最適部分構造や貪欲選択特性の利用と相性がよい。
2.3 反例の理解
貪欲法が失敗するのは珍しくない。反例を理解することは、どの性質が欠けているのかを把握し、選択ルールの設計や正当化可能性の評価に役立つ。
2.3.1 貪欲が失敗する典型パターン
典型的には、局所で最も得に見える選択が、後続で必要な選択を排除してしまうパターンで失敗する。言い換えると、「一見した増分の良さ」が「将来の可用性」を犠牲にしている。
また、局所評価が目的関数の全体構造に対応していない場合にも破綻する。部分的な指標だけでは、残り要素の組み合わせにより大きな差が生まれるため、貪欲が正しい保証を持てない。
2.3.2 正当化できないときの判断
貪欲法を採用する際、選択ルールの根拠が証明として確立できない場合は、少なくとも全一般に正しいと主張できない。したがって、検討すべきは「貪欲選択特性が成立するか」「最適部分構造が利用できるか」「交換が可能か」といった観点である。
これらが見つからないとき、解の探索空間を絞る他手法（動的計画法、分岐限定など）へ切り替える判断が妥当になる。実務では、検証実験とともに、証明が難しい理由が構造的欠如である可能性も評価対象になる。
3 分析と実装上の要点
貪欲法の実装は比較的単純になりやすいが、候補管理やデータ構造設計によって性能が大きく変わる。ここでは計算量見積もり、実装戦略、そして再現性に関する注意点を整理する。
3.1 計算量
計算量は「各段階で何を計算し、候補集合をどう更新するか」で決まる。貪欲法は局所判断だけを行うため、全探索に比べて軽くなることが多いが、それでも実装の選び方が重要になる。
3.1.1 候補選択のコスト
最もコストがかかりやすいのは、各ステップで最良候補を見つける処理である。素朴に探索すると、各段階で候補を総当たりするため、候補数が多いと総計が膨らむ。
したがって、評価値の更新や比較が効率よく行えるように、候補集合を整理することが望ましい。特に、貪欲選択を何度も繰り返す問題では、ここが性能の支配要因になりやすい。
3.1.2 データ構造による高速化
高速化には、優先度付きキュー（ヒープ）や平衡木、特定の順序を保つ構造などが用いられる。これらにより、最大（最小）要素の取り出しや、更新の計算量を下げられる。
また、候補の並べ替えを一度だけ行い、走査で対応できる問題ではソートが効く場合がある。更新が少ない形に問題を落とせるほど、全体の手間も減る。
3.2 実装戦略
実装の要点は、選択ルールをどのように計算へ落とし込み、候補管理をどう行うかにある。ここではよくある二つの戦略を挙げる。
3.2.1 優先度付きキュー（ヒープ）の利用
優先度付きキューは、現在の候補集合から評価値の最大または最小を素早く取得するのに適する。各ステップで「最良候補の取り出し」を行い、選択後に生じる新たな候補や更新をヒープへ反映する構造が典型例である。
利点は、取り出しの計算量を抑えながら、動的に変化する候補集合へ対応できる点にある。欠点としては、評価値の更新方針（減算・加算、無効化の扱いなど）を誤ると正しさに影響する場合がある。
3.2.2 ソートによる候補管理
ソート戦略は、候補集合を最初に並べ替えて固定の順で処理することで、繰り返し比較のコストを減らす。たとえば、開始時点の選択が単調で、次段の判断が「順序に沿って確認する」だけで済む場合に向く。
ただし、選択後に候補の評価値が変わるタイプでは、単純なソートだけで維持できないことがある。この場合は、ソートで初期整理しつつ、更新は別手段で扱う折衷が必要になる。
3.3 安定性と再現性
同じ目的値を持つ候補が複数ある場合、貪欲法は選択のタイブレーク次第で結果の形が変わり得る。計算結果の再現性は、研究や検証だけでなく運用上の信頼性にも関わる。
3.3.1 タイブレークの扱い
タイブレークとは、評価値が同点の候補が複数あるときの選び方の規則である。たとえば、入力順、IDの小さいもの、二次評価指標などで決める。
これにより、同じ入力に対して常に同じ出力を得る設計が可能になる。さらに、同点であっても目的値が同じとは限らない場面では、二次評価の設計が結果の品質に影響するため慎重さが必要になる。
3.3.2 同値解の管理
同値解は、目的値が等しいために複数の解が存在する状態を指す。貪欲法はそのうちの一つを返すが、同値解の列挙を目的としているわけではない場合、どれを返しても要件を満たすことがある。
要件が「解の一例でよい」のか「特定の性質を持つ解が必要」なのかを整理し、必要に応じてタイブレークや追加条件を定めると、仕様と出力の整合が取りやすくなる。
4 応用分野と具体例
貪欲法は多様な問題に現れる。ここでは、最小化・最大化、組合せ最適化、グラフ構造、そして近似の観点を中心に、典型的な適用イメージを整理する。
4.1 最小化・最大化の問題
最小化・最大化では、候補の評価値が目的関数と直接結びつくことが多い。貪欲選択は、その評価値に基づいて各段階の意思決定を行う形になりやすい。
4.1.1 変更最小化（例：コイン問題の発想）
変更最小化の一例として、硬貨の組み合わせで支払額を作り、使用枚数を最小にする問題がある。一般の通貨体系では最小枚数を保証しない貪欲も存在するため、成立の可否は通貨体系の性質に依存する。
ただし、ある種の「規格化された」通貨では、より大きい額を優先して選ぶ戦略が正しい場合がある。ここでは、貪欲選択特性が成立するかを確認することが重要になる。
4.1.2 組合せ最適化（例：活動選択）
活動選択は、互いに重ならない活動を選び、選択件数を最大化する問題として知られる。終了時刻が早い活動を優先して選ぶことで、残りの活動集合に対する選択可能性が最大化されるため、貪欲法が自然に働く例として扱われることが多い。
この種の問題では、ある活動を選んだときに「次に選べる範囲」が明確に制限される。制限が単調で、局所選択が未来を狭めすぎない構造になっていると、貪欲の正当化が進めやすい。
4.2 グラフに関する貪欲法
グラフ上の最適化では、局所的に良い辺や頂点を選ぶことで全体の構造を組み立てる場面が多い。木や経路に関する目的では、貪欲が特に理解しやすい形で現れる。
4.2.1 最小全域木（例：最小全域木の発想）
最小全域木は、全頂点を連結しつつ総辺重みを最小化する問題である。貪欲法の代表例として、辺を評価しながら選択していき、サイクルを避ける方針などが知られている。
この枠組みでは、選んだ辺が構造を壊さないことや、局所的な最小候補が全体の最適に寄与することが、交換論法や特性により正当化される。実装上は候補辺の扱いが性能を左右するため、優先度付き管理がしばしば用いられる。
4.2 最短経路との関係（比較の観点）
最短経路は、貪欲そのものではなく、優先度付き選択を組み込んだアルゴリズムとして説明されることが多い。比較の観点では、「局所最小の距離が確定していく」流れが似ている一方で、一般の貪欲選択と異なり、距離推定の更新や取り扱いがより精密に設計されている。
つまり、見た目としては貪欲的に候補を選ぶが、正当化の論理が距離の単調性などに強く依存する点が重要である。これにより「貪欲という語で一括りにできない」境界が見えてくる。
4.3 連続・近似の考え方
連続最適化や巨大データでは、厳密解の計算が難しい場合がある。そのとき貪欲法は近似手法として位置付けられることがある。
4.3.1 近似アルゴリズムとしての貪欲法
近似アルゴリズムでは、最適値との距離（比率、差分など）を評価しつつ、計算量と品質のバランスを取る。貪欲法は局所判断を繰り返すため、アルゴリズムとして扱いやすく、大規模な場面での実装がしやすい。
ただし、近似保証が成立するかは問題ごとに異なる。貪欲選択の理由付けをどのように数学的に整理するかが、保証の獲得に直結する。
4.3.2 誤差評価の考え方
誤差評価では、出力値と最適値の関係を指標化する。比率保証（目的の比）や加法保証（誤差の最大差）などがあり、選択ルールと問題構造の両方が必要になる。
近似においては、最適性そのものではなく「どれだけ悪くなり得るか」を知ることが実務上の価値になる。したがって、貪欲法の選択規則がもたらす悪化要因を分解し、評価式に落とすことが重要になる。
4.4 よくある落とし穴（失敗例の教訓）
貪欲法の失敗は、しばしば証明不足や状態設計の不備から生じる。失敗例を踏まえて、どこを検証すべきかを明確にすると再発を防ぎやすい。
4.4.1 選択ルールの不備
選択ルールが目的関数と整合していない場合、局所の判断が全体の成果に反映されない。評価指標の定義を誤る、比較対象を取り違える、増分計算が成立していない、といった初歩的なミスが原因になることも多い。
また、貪欲が必要とする性質（特性や部分構造）を満たさないにもかかわらず、その可能性の検討をせずに採用すると、正しさが破綻する。
4.4.2 状態設計の見落とし
貪欲法では、未来に影響する情報を状態として保持する必要がある。選んだ結果によって選択可能範囲が変わるにもかかわらず、状態が不十分だと、次段で誤った比較が行われる。
状態を省略しすぎると、同じ段階に見えても実際には異なる状況が混ざってしまう。これにより、表面上は簡潔でも実際の挙動は正しくならない。
4.4.3 検証不足による誤判定
理屈の検証不足は最大の落とし穴になりやすい。少数のテストで動いたとしても、正当化が欠ければ一般性は保証されない。逆に、証明しようとしても不成立の兆候が見えた場合は、探索的に反例を探す姿勢が必要になる。
実装においても、境界条件（最小ケース、同値ケース、候補ゼロ、重複入力）で挙動が崩れやすい。貪欲法は分岐が少ない分、例外処理を落とすと致命的になることがある。
5 関連アルゴリズムとの比較
貪欲法は他手法と比較して初めて理解が深まる。ここでは、動的計画法、探索・分岐限定、局所探索との違いを整理し、どの状況で選択すべきかの判断材料を与える。
5.1 動的計画法との対比
動的計画法（DP）は、部分問題を体系的に解き、最適値を保存することで全体の最適を導く手法である。貪欲法との違いは、「部分問題の扱い」と「再計算を避ける方法」に現れる。
5.1.1 部分問題の扱いの違い
貪欲法は、各段階で一つ（あるいは少数）の選択に固定し、残りを同じ規則で進める。対してDPは、複数の候補選択を残したまま部分最適を比較し、必要な情報を表として保持する。
結果として、貪欲法は計算量が小さくなることがあるが、成立条件が欠けると最適性が得られない。DPは一般に正しさが確立しやすい代わりに、状態数や遷移が増えると計算負荷が大きくなる。
5.1.2 計算量・実装難度の比較
DPは状態設計と遷移定義が必要で、実装難度が上がりやすい。貪欲法は選択ルールが明確であれば簡潔だが、正当化と境界条件の検証が要求される。
計算量はDPが表の次元に依存し、貪欲法は候補管理と反復回数に依存する。問題サイズの性質によって有利不利が変わるため、目的値、入力規模、制約の形式を踏まえて選択することが重要になる。
5.2 探索・分岐限定との対比
探索・分岐限定は、候補を分岐させながら全探索に近い形で解を探すが、評価値の上限や下限にもとづいて無駄を削減するのが特徴である。
5.2.1 全探索の必要性
貪欲法は分岐をほぼ持たないため、全探索が不要な構造の問題で強みを発揮する。逆に、全体最適が局所では決まりにくい問題では、貪欲だけでは探索の必要性が残る。
このような場合、探索・分岐限定は正解に到達する確率を高められるが、その代わり計算時間が増えやすい。
5.2.2 現実的な打ち切りの設計
分岐限定では、上界・下界による打ち切りが設計の中心になる。貪欲法のように局所選択を採用することで良い解を早く見つけ、下界（あるいは暫定解）を改善して枝刈りを強くする、という併用もよく行われる。
つまり、貪欲法は単体での解決だけでなく、探索の効率化のための「初期解生成器」として機能する場合がある。
5.3 局所探索やその他のアプローチとの違い
局所探索は、現在の解の近傍を改善することで状態を動かす方針であり、逐次決定型の貪欲法と性質が異なる。その他のアプローチには、メタヒューリスティクスや学習に基づく手法などが含まれる。
5.3.1 反復改善か逐次確定か
貪欲法は「選んだものを基本的に後で覆さない」逐次確定に近い。局所探索は「いったん作った解を改善し直す」反復の側面が強く、変更や後戻りを許す。
そのため、貪欲法は計算量が予測しやすい反面、誤りを修正する仕組みが乏しい。局所探索は修正の余地を持つが、停留点や初期解依存といった問題が起こりやすい。
5.3.2 性能保証の有無の違い
貪欲法は、正当化が成立する問題では性能保証が強い形で得られる。対して局所探索は、保証が弱い場合や問題依存のことがある。
近似や経験則に寄るアプローチでは、保証をどこまで求めるかが設計目標になる。保証の有無は「目的関数の性質」「探索のルール」「理論的解析の可否」によって左右される。