貪欲法

貪欲法は、現在のステップで最も良いと思われる選択を繰り返し行うことで、段階的に解を構築するアルゴリズムであり、そのような局所的に最適な選択が、大域的に最適な解に導くことが証明できる場合に限り、正しいとされます。

Definition

貪欲法は、一連の選択を通じて解を構築するアルゴリズムであり、それぞれの選択は、何らかの局所的な基準を最適化するように選ばれ、以前の選択を再検討することはありません。この方法は、局所的に最適な選択が大域的に最適な結果をもたらす場合にのみ正しいとされます。

Scope

このトピックでは、貪欲パラダイムについて扱います。具体的には、貪欲選択特性とそれを正当化する最適部分構造、標準的な証明手法（交換引数とマトロイドフレームワーク）、およびハフマン符号化、最小全域木（クラスカル法とプリム法）、ダイクストラ法による最短経路、区間スケジューリングなどの典型的な貪欲アルゴリズムが含まれます。また、貪欲戦略が厳密な手法ではなく、近似ヒューリスティックとしてのみ機能する場合についても考察します。

Core questions

• 貪欲選択特性とは何か、また特定の問題に対してどのように証明されるのか？
• 交換引数（exchange argument）は、貪欲な選択が安全であることをどのように示すのか？
• マトロイド構造を持つ問題は、貪欲法の最適性をどのように保証するのか？
• 貪欲法が厳密なアルゴリズムではなく、近似法に過ぎないのはどのような場合か？
• 同じ問題に対して、貪欲法と動的計画法はどのように比較されるのか？

Key concepts

• 貪欲選択特性
• 最適部分構造
• 交換引数
• マトロイド
• ハフマン符号化
• 最小全域木
• 区間スケジューリング
• 分数ナップサック問題

Key theories

貪欲選択特性と交換引数

大域的に最適な解が、最適性を損なうことなく貪欲な最初の選択と一致するように常に変更できる場合、問題は貪欲解を許容します。交換引数（または「貪欲が先行する」引数）はこれを形式化します。

マトロイドと貪欲法の最適性

実行可能な解が重み付きマトロイドの独立集合を形成する場合、貪欲アルゴリズムは常に最大重み独立集合を見つけます。これは、クラスカルの最小全域木アルゴリズムの最適性などの結果を統一的に説明します。

Clinical relevance

貪欲法は、広く利用されているシステムを駆動しています。例えば、データ圧縮形式におけるハフマン符号化、ネットワーク設計における最小全域木アルゴリズム、ルーティングやナビゲーションにおけるダイクストラアルゴリズム、オペレーティングシステムやリソース割り当てにおける貪欲スケジューリングや集合被覆ヒューリスティックなどがあります。

History

貪欲的推論は、クラスカル（1956年）とプリム（1957年）の最小全域木アルゴリズム、ハフマン（1952年）の最適プレフィックス符号、ダイクストラ（1959年）の最短経路アルゴリズムといった古典的な成果に現れています。貪欲法が成功する条件をマトロイド理論的に説明する研究は、1960年代から1970年代にかけてエドモンズらによって発展しました。

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

貪欲法が分数ナップサック問題には有効で、0/1ナップサック問題には有効でないのはなぜですか？

分数ナップサック問題では、品物を分割できるため、単位重量あたりの価値が最も高い品物を最初に選択することは常に安全であり、最適であることが証明できます。0/1ナップサック問題では、品物は分割できないため、貪欲な選択がより良い組み合わせを排除する可能性があり、厳密な最適解を得るには動的計画法が必要です。

貪欲アルゴリズムが正しいことをどのように証明しますか？

標準的な2つの手法は、交換引数（exchange argument）と「貪欲が先行する」（greedy stays ahead）引数です。交換引数は、任意の最適解を、最適性を悪化させることなく貪欲解に変換できることを示します。一方、「貪欲が先行する」引数は、貪欲な部分解が、各ステップにおいて他のどの部分解よりも少なくとも同等に優れていることを示します。マトロイド理論は、一般的な十分条件を提供します。