乱択アルゴリズムと近似アルゴリズム
乱択アルゴリズムと近似アルゴリズムは、正確性や決定論を効率性と引き換えにするものです。乱択アルゴリズムは、速度や単純さを得るためにランダムな選択を使用し、近似アルゴリズムは、正確に解くには難しすぎる問題に対して、証明可能で最適に近い解を見つけます。
Definition
乱択アルゴリズムは、実行中にランダムな選択を行い、期待実行時間または正しさの確率について分析されます。近似アルゴリズムは効率的に実行され、困難な最適化問題に対して、最適解の証明された係数内に収まることが保証された解を返します。
Scope
この分野は、厳密で決定論的な解という目標を緩和するアルゴリズムを扱います。これには、確率的保証を伴う乱択アルゴリズム（ラスベガス法とモンテカルロ法）、NP困難な最適化問題に対する証明された近似比を持つ近似アルゴリズム、そして将来を知らずに決定を下さなければならないオンラインアルゴリズム（競争率によって分析される）が含まれます。これらは、計算量解析と設計パラダイムに基づいて、手に負えない問題や不確実性のある状況に対する標準的な対応策です。
Sub-topics
Core questions
- ランダム化は実行時間、単純さ、または堅牢性をどのように改善するのか？
- ラスベガス法とモンテカルロ法の保証の違いは何か？
- 近似アルゴリズムの品質は近似比によってどのように定量化されるのか？
- どのNP困難問題が良い近似を許容し、どれがそれに抵抗するのか？
- 将来の情報なしに行われるオンライン決定は、競争的にどのように評価されるのか？
Key concepts
- 乱択アルゴリズム
- ラスベガス法とモンテカルロ法
- 期待実行時間
- 集中不等式
- 近似比
- 多項式時間近似スキーム
- オンラインアルゴリズム
- 競争率
Key theories
- 効率性のためのランダム化
- ランダムな選択は、最良の決定論的アルゴリズムよりも高速または単純なアルゴリズムを生み出すことがあり、期待時間（ラスベガス法）またはエラー確率（モンテカルロ法）に関する保証を伴い、しばしば解析には集中不等式が使用されます。
- NP困難問題に対する近似比
- 厳密な解が手に負えない場合、近似アルゴリズムは最適解の特定の係数（近似比）内にあることが証明された解を提供します。達成可能な近似比は、問題がどの程度うまく近似できるかを特徴づけます。
Clinical relevance
これらの方法は、困難で不確実な問題に対する実用的なツールキットです。乱択アルゴリズムは、暗号学における素数判定、ハッシュ、負荷分散を推進します。近似アルゴリズムは、NP困難なスケジューリング、ルーティング、クラスタリング、施設配置問題に対して実用的な解を生成します。オンラインアルゴリズムは、リアルタイムで決定を下す必要があるキャッシュ、ページング、リソース割り当てをモデル化します。
History
乱択アルゴリズムは、1970年代のソロベイ-ストラッセン素数判定法とラビン素数判定法、およびラビンによる確率的手法の広範な提唱によって注目を集めました。近似アルゴリズムは、1970年代からNP完全性理論とともに発展し、オンラインアルゴリズムの競争解析は1980年代にスレーターとタージャンによって形式化され、これらが不正確なアルゴリズムと確率的アルゴリズムの現代的な研究を形成しました。
Key figures
- Rajeev Motwani
- Prabhakar Raghavan
- Vijay Vazirani
- Michael Rabin
- Robert Solovay
- Volker Strassen
Related topics
Seminal works
- motwani1995
- vazirani2001
- cormen2009
Frequently asked questions
- 乱択アルゴリズムはランダム性を使用するため信頼できないのでしょうか？
- いいえ。ラスベガスアルゴリズムは常に正しい答えを返し、その実行時間のみが変動します。モンテカルロアルゴリズムは誤る可能性がありますが、反復によってエラー確率を任意に低くすることができます。それらの保証は、予測不可能性ではなく、正確な確率的記述です。
- 最適な解を見つける代わりに、なぜ近似アルゴリズムを使用するのですか？
- NP困難な最適化問題の場合、大規模な入力に対して厳密な最適解を見つけることは非現実的である可能性があります。近似アルゴリズムは多項式時間で実行され、最適解の既知の係数内の解を保証します。これは多くの場合十分に良好であり、厳密な答えを待つよりもはるかに実用的です。