貪欲アルゴリズムは、お釣りを出す際に最低限必要な硬貨の枚数を決定します。これは、{1, 5, 10, 20}の硬貨のみを使って36セントを表す貪欲アルゴリズムを模倣しようとする人がほとんどである手順です。お釣りの残額よりも少ない、最も高い額の硬貨が局所最適解となります。（一般に、お釣りを出す問題では、最適解を見つけるために動的計画法が必要ですが、ほとんどの通貨システムは、貪欲戦略で最適解を見つけることができる特殊なケースです。）

貪欲アルゴリズムとは、各段階で局所的に最適な選択を行うという問題解決のヒューリスティックに従うアルゴリズムです。 [1]多くの問題において、貪欲戦略は最適な解を生成しませんが、貪欲ヒューリスティックは、妥当な時間内に大域的最適解に近い局所的最適解を生成することができます。[2]

例えば、計算量が非常に多い巡回セールスマン問題に対する貪欲戦略は、次のようなヒューリスティックです。「旅の各ステップで、最も近い未訪問の都市を訪問する。」このヒューリスティックは最適な解を見つけることを意図しているわけではありませんが、妥当な数のステップで終了します。このような複雑な問題に対する最適な解を見つけるには、通常、不合理なほど多くのステップが必要になります。[3]

数学的最適化において、貪欲アルゴリズムはマトロイドの特性を持つ組み合わせ問題を最適に解決し、サブモジュラー構造を持つ最適化問題に定数係数近似を与えます。

詳細

貪欲アルゴリズムは、一部の数学の問題では優れた解を生成できますが、他の問題ではそうではありません。貪欲アルゴリズムが有効なほとんどの問題は、以下の2つの特性を備えています。

貪欲選択特性
与えられた瞬間に最善と思われる選択を行ってから、残りのサブ問題を（再帰的に）解決することができます。貪欲アルゴリズムによる選択は、それまでの選択によって決まりますが、将来の選択やサブ問題のすべての解決策には左右されません。貪欲な選択を次から次へと繰り返して行い、与えられた各問題をより小さな問題に縮小します。言い換えれば、貪欲アルゴリズムは選択を再検討することはありません。これが、網羅的で最善の（つまり、「最適な」）解決策を見つけることが保証されている動的計画法との主な違いです。各ステージの後、動的計画法は前のステージで行われたすべての決定に基づいて決定を行い、前のステージの解決策へのアルゴリズムのパスを再検討する場合があります。
最適なサブ構造
「ある問題に対する最適解が部分問題に対する最適解を含んでいる場合、その問題は最適な部分構造を示している。」 [4]

正しさの証明

貪欲アルゴリズムの正しさを証明するための一般的な手法として、帰納的交換論証が用いられる。[5]交換論証は、貪欲解とは異なる任意の解は、その質を低下させることなく貪欲解に変換できることを示す。この証明パターンは、典型的には次の手順に従う。

  1. 貪欲解とは異なる最適解が存在すると仮定する
  2. 最適解と貪欲解が異なる最初のポイントを特定する
  3. この時点で最適な選択を貪欲な選択と交換しても、解決策が悪化しないことを証明してください。
  4. 帰納的に、貪欲解と同一の最適解が存在するはずであると結論付ける

場合によっては、貪欲なソリューションを厳密に改善できる最適なソリューションがないことを証明するために、追加の手順が必要になることがあります。

失敗例

貪欲アルゴリズムが最適な解決策を達成できない可能性がある例。

貪欲アルゴリズムは、他の多くの問題において最適解を生成できず、最悪の解を一意に生成してしまうことさえあります。一例として、前述の巡回セールスマン問題が挙げられます。各都市数に対して、最近傍法によって最悪の巡回ルートが一意に生成される都市間の距離が割り当てられます。[6] その他の例としては、地平線効果を参照してください。

種類

貪欲アルゴリズムは「近視眼的」であり、「回復不可能」であるという特徴があります。貪欲アルゴリズムは、「最適な部分構造」を持つ問題にのみ適しています。しかしながら、多くの単純な問題では、貪欲アルゴリズムが最適なアルゴリズムとなります。ただし、貪欲アルゴリズムは、探索における選択肢の優先順位付けのための選択アルゴリズム、あるいは分岐限定アルゴリズムとして使用できることに注意することが重要です。貪欲アルゴリズムにはいくつかのバリエーションがあります。[7]

  • 純粋な貪欲アルゴリズム
  • 直交貪欲アルゴリズム
  • 緩和貪欲アルゴリズム

理論

貪欲アルゴリズムは、組合せ最適化と理論計算機科学において長い研究の歴史を持っています。貪欲ヒューリスティックは多くの問題において最適ではない結果を生み出すことが知られており、[8]、次のような自然な疑問が生じます。

  • 貪欲アルゴリズムはどのような問題に対して最適に機能しますか?
  • 貪欲アルゴリズムはどのような問題に対してほぼ最適な解決策を保証しますか?
  • 貪欲アルゴリズムでは最適な解決策が生成されないことが保証されている問題はどれですか?

マトロイドなどの一般的な問題や、集合被覆などの特定の問題について、これらの質問に答える文献が多数存在します。

マトロイド

マトロイドとは、線形独立性の概念をベクトル空間から任意の集合へと一般化した数学的構造である。最適化問題がマトロイドの構造を持つ場合、適切な貪欲アルゴリズムによって最適に解くことができる。[9]

劣モジュラ関数

集合のサブセット上で定義された関数は、任意の に対して が成り立つとき、サブモジュラ関数と呼ばれます。

を最大化する集合を見つけたいとします。貪欲アルゴリズムは、各ステップで最大に増加する要素を段階的に追加することで集合を構築し、出力として少なくとも となる集合を生成します。[10]つまり、貪欲アルゴリズムは最適解と同程度の定数倍の性能を発揮します。

同様の保証は、出力にカーディナリティ制約[11]などの追加制約を課した場合にも証明可能ですが、貪欲アルゴリズムに若干のバリエーションが必要となる場合が多くあります。概要については [12]を参照してください。

保証に関するその他の問題

貪欲アルゴリズムが強力な保証を与えるが、最適な解決策ではない他の問題には以下が含まれる。

これらの問題の多くには一致する下限があります。つまり、貪欲アルゴリズムは最悪の場合でも保証よりも優れたパフォーマンスを発揮しません。

アプリケーション

貪欲アルゴリズムは、通常、すべてのデータに対して網羅的に処理を行わないため、一般的に（常にそうとは限りませんが）、全体最適解を見つけることができません。特定の選択をあまりにも早く決定してしまうと、後になって全体最適解を見つけられなくなる可能性があります。例えば、グラフ彩色問題やその他のNP完全問題に対する既知の貪欲彩色アルゴリズムは、どれも常に最適解を見つけるわけではありません。しかしながら、これらのアルゴリズムは迅速に考案でき、最適解に近い近似値を与えることが多いため、有用です。

貪欲アルゴリズムが特定の問題クラスに対して大域的最適解をもたらすことが証明された場合、動的計画法などの他の最適化手法よりも高速であるため、通常は貪欲アルゴリズムが選択される手法となります。このような貪欲アルゴリズムの例としては、最小全域木を求めるクラスカルのアルゴリズムやプリムのアルゴリズム、最適なハフマン木を求めるアルゴリズムなどがあります。

貪欲アルゴリズムはネットワークルーティングにも用いられます。貪欲ルーティングでは、メッセージは宛先に「最も近い」隣接ノードに転送されます。ノードの位置（つまり「近さ」）の概念は、アドホックネットワークで使用される地理ルーティングのように、物理的な位置によって決定される場合があります。また、スモールワールドルーティングや分散ハッシュテーブルのように、位置は完全に人工的な概念である場合もあります。

例

参照

参考文献

  1. ^ Black, Paul E. (2005年2月2日). 「greedy algorithm」.アルゴリズムとデータ構造の辞書.米国国立標準技術研究所(NIST) . 2012年8月17日閲覧。
  2. ^ van Melkebeek, Dieter. 「Greedy approximations」（PDF） .ウィスコンシン大学マディソン校. 2025年7月25日閲覧。
  3. ^ Frieze, Alan; Pegden, Wesley (2023-10-05). 「TSPにおけるシンプルなヒューリスティックスの明るい側面」arXiv : 2310.03222 [cs.DM].
  4. ^ コーメン他 2001年、第16章
  5. ^ Erickson, Jeff (2019). 「貪欲アルゴリズム」. アルゴリズム. イリノイ大学アーバナ・シャンペーン校.
  6. ^ Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). 「巡回セールスマンは貪欲であってはならない：TSPにおける貪欲型ヒューリスティックスの支配分析」.離散応用数学. 117 ( 1–3 ): 81–86 . doi : 10.1016/S0166-218X(01)00195-0 .
  7. ^ DeVore, RA; Temlyakov, VN (1996-12-01). 「貪欲アルゴリズムに関するいくつかの考察」 .計算数学の進歩. 5 (1): 173– 187. doi :10.1007/BF02124742. ISSN  1572-9044.
  8. ^ フェイジ 1998
  9. ^ パパディミトリウ & スタイグリッツ 1998
  10. ^ ネムハウザー、ウォルジー、フィッシャー 1978
  11. ^ ブッフビンダー他 2014
  12. ^ クラウス＆ゴロビン 2014
  13. ^ 「講義5：近似アルゴリズム入門」（PDF） .上級アルゴリズム（2IL45）— コースノート. アイントホーフェン工科大学. 2022年10月9日時点のオリジナルよりアーカイブ（PDF） .

出典

  • コーメン、トーマス H.チャールズ・E・ライザーソン;ロナルド・L・リベスト、スタイン、クリフォード (2001)。 「16の貪欲なアルゴリズム」。アルゴリズムの概要。 MITプレス。 370ページ–。ISBN 978-0-262-03293-3。
  • グレゴリー・グティン、アンダース・ヨー、アレクセイ・ズベロヴィッチ (2002). 「巡回セールスマンは貪欲であってはならない：TSPにおける貪欲型ヒューリスティックスの支配分析」.離散応用数学. 117 ( 1–3 ): 81–86 . doi : 10.1016/S0166-218X(01)00195-0 .
  • Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004). 「貪欲アルゴリズムが失敗するとき」.離散最適化. 1 (2): 121– 127. doi : 10.1016/j.disopt.2004.03.007 .
  • Bendall, Gareth; Margot, François (2006). 「組み合わせ問題における貪欲型耐性」.離散最適化. 3 (4): 288– 298. doi : 10.1016/j.disopt.2006.03.001 .
  • Feige, U. (1998). 「集合被覆近似のためのln nの閾値」(PDF) . Journal of the ACM . 45 (4): 634– 652. doi :10.1145/285055.285059. S2CID 52827488. 2022年10月9日時点のオリジナルより アーカイブ(PDF) 。
  • Nemhauser, G.; Wolsey, LA; Fisher, ML (1978). 「劣モジュラー集合関数の最大化のための近似値の解析—I」.数理計画. 14 (1): 265– 294. doi :10.1007/BF01588971. S2CID  206800425.
  • Buchbinder, Niv; Feldman, Moran; Naor, Joseph (Seffi); Schwartz, Roy (2014). 「基数制約付き劣モジュラ最大化」(PDF) . 第25回ACM-SIAM離散アルゴリズムシンポジウム議事録. Society for Industrial and Applied Mathematics. doi :10.1137/1.9781611973402.106. ISBN 978-1-61197-340-22022年10月9日時点のオリジナルよりアーカイブ（PDF）されています。
  • Krause, A.; Golovin, D. (2014). 「劣モジュラー関数最大化」. Bordeaux, L.; Hamadi, Y.; Kohli, P. (編). Tractability: Practical Approaches to Hard Problems . Cambridge University Press. pp.  71– 104. doi :10.1017/CBO9781139177801.004. ISBN 9781139177801。
  • パパディミトリウ, クリストス H. ;シュタイグリッツ, ケネス(1998).組合せ最適化：アルゴリズムと複雑性. ドーバー.
ウィキメディア コモンズには、貪欲アルゴリズムに関連するメディアがあります。