貪欲アルゴリズム

貪欲アルゴリズムとは、各段階で局所的に最適な選択を行うという問題解決のヒューリスティックに従うアルゴリズムです。 ^[1]多くの問題では、貪欲な戦略では最適な解決策は得られませんが、貪欲なヒューリスティックでは、妥当な時間内にグローバルな最適解に近い、ローカルに最適な解決策を生み出すことができます。

たとえば、計算の複雑さが極めて高い巡回セールスマン問題に対する貪欲戦略は、次のようなヒューリスティックです。「旅の各ステップで、最も近い未訪問の都市を訪問する。」このヒューリスティックは、最適なソリューションを見つけることを意図しているのではなく、妥当な数のステップで終了します。このような複雑な問題に対する最適なソリューションを見つけるには、通常、不当に多くのステップが必要です。数学的最適化では、貪欲アルゴリズムは、マトロイドの特性を持つ組み合わせ問題を最適に解決し、サブモジュラー構造を持つ最適化問題に定数係数近似値を与えます。

貪欲アルゴリズムは、一部の数学の問題では優れた解を生み出しますが、他の問題ではそうではありません。貪欲アルゴリズムが機能するほとんどの問題には、次の 2 つの特性があります。

貪欲選択特性

与えられた瞬間に最善と思われる選択を行い、残りのサブ問題を（再帰的に）解決することができます。貪欲アルゴリズムによる選択は、これまでの選択に依存する可能性がありますが、将来の選択やサブ問題に対するすべての解決策には依存しません。貪欲な選択を次から次へと繰り返して行い、与えられた各問題をより小さな問題に縮小します。言い換えれば、貪欲アルゴリズムは選択を再検討することはありません。これが、網羅的で解決策が確実に見つかる動的プログラミングとの主な違いです。各ステージの後に、動的プログラミングは前のステージで行われたすべての決定に基づいて決定を行い、前のステージの解決策へのアルゴリズムのパスを再検討する場合があります。

最適なサブ構造

「問題の最適解が部分問題に対する最適解を含んでいる場合、その問題は最適な部分構造を示す。」 ^[2]

貪欲アルゴリズムは、他の多くの問題では最適解を生成できず、最悪の解のみを生成することさえあります。1つの例は、前述の巡回セールスマン問題です。各都市数に対して、最近傍ヒューリスティックが最悪の巡回ルートを生成する都市間の距離が割り当てられます。^[3] その他の考えられる例については、地平線効果を参照してください。

貪欲アルゴリズムは「近視眼的」であり、「回復不可能」であるとも特徴付けられます。これらは「最適なサブ構造」を持つ問題にのみ理想的です。それにもかかわらず、多くの単純な問題では、貪欲アルゴリズムが最適なアルゴリズムです。ただし、貪欲アルゴリズムは、検索内のオプションを優先順位付けするための選択アルゴリズム、または分岐限定アルゴリズムとして使用できることに注意してください。貪欲アルゴリズムにはいくつかのバリエーションがあります。^[4]

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

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

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

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

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

集合のサブセット上で定義された関数は、任意の に対して が成り立つとき、サブモジュラ関数と呼ばれます。 ${\displaystyle f}$${\displaystyle \オメガ}$${\displaystyle S,T\subseteq \Omega }$${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$

を最大化する集合を見つけたいとします。貪欲アルゴリズムは、各ステップで最大に増加する要素を徐々に追加して集合を構築し、少なくとも である集合を出力します。^[7]つまり、貪欲アルゴリズムは最適解と同程度 の定数倍のパフォーマンスを発揮します。${\displaystyle S}$${\displaystyle f}$${\displaystyle S}$${\displaystyle f}$${\displaystyle (1-1/e)\max _{X\subseteq \Omega }f(X)}$${\displaystyle (1-1/e)\approx 0.63}$

^{カーディナリティ制約[8]}などの追加の制約が出力に課せられた場合も同様の保証が証明可能ですが、貪欲アルゴリズムに若干の変更が必要になることがよくあります。概要については ^{[9]を参照してください。}

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

• カバーを設定する
• シュタイナーの木の問題
• 負荷分散^[10]
• 独立集合

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

貪欲アルゴリズムは、通常、すべてのデータに対して網羅的に処理しないため、一般的には (常にというわけではありませんが) 全体的に最適なソリューションを見つけることができません。特定の選択をあまりにも早く決定してしまい、後で全体的に最適なソリューションを見つけられなくなる可能性があります。たとえば、グラフの色付け問題やその他のすべてのNP 完全問題に対する既知の貪欲色付けアルゴリズムはすべて、常に最適なソリューションを見つけるわけではありません。それでも、すぐに思いつくし、最適解に近い値を示すことが多いため、便利です。

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

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

• アクティビティ選択問題は、この種の問題の特徴であり、その目的は、互いに衝突しないアクティビティを最大数選択することです。
• MacintoshのコンピュータゲームCrystal Quest の目的は、巡回セールスマン問題に似た方法でクリスタルを集めることです。このゲームにはデモ モードがあり、ゲームは貪欲アルゴリズムを使用してすべてのクリスタルを探します。人工知能は障害物を考慮しないため、デモ モードはすぐに終了することがよくあります。
• マッチング追求は、信号近似に適用される貪欲アルゴリズムの例です。
• 貪欲アルゴリズムは、与えられた三角形内で 3 つの互いに交わらない円の合計面積を最大化するマルファッティの問題に対する最適解を見つけます。同じ貪欲アルゴリズムが任意の数の円に対して最適であると推測されます。
• ハフマン符号化中に貪欲アルゴリズムを使用してハフマン ツリーを構築し、最適なソリューションを見つけます。
• 決定木学習では貪欲アルゴリズムが一般的に使用されますが、最適な解決策が見つかる保証はありません。
  • そのようなアルゴリズムの 1 つとして、決定木構築用のID3 アルゴリズムが人気があります。
• ダイクストラのアルゴリズムと関連するA* 検索アルゴリズムは、グラフ検索と最短経路検索のための検証可能に最適な貪欲アルゴリズムです。
  • A* 検索は条件付きで最適であり、パス コストを過大評価しない「許容ヒューリスティック」を必要とします。
• クラスカルのアルゴリズムとプリムのアルゴリズムは、与えられた連結グラフの最小全域木を構築するための貪欲アルゴリズムです。これらは常に最適な解を見つけますが、一般には一意ではない場合があります。
• SequiturアルゴリズムとLempel-Ziv-Welchアルゴリズムは、文法帰納法のための貪欲アルゴリズムです。

ウィキメディア・コモンズには貪欲アルゴリズムに関連するメディアがあります。

• 「貪欲アルゴリズム」、数学百科事典、EMS Press、2001 [1994]
• ギフト、ノア。「Python の貪欲なコインの例」。