Loading article…
コンピューティングにおいて、モンテカルロアルゴリズムは、ある一定の（通常は小さい）確率で出力が間違っている可能性があるランダム化アルゴリズムです。このようなアルゴリズムの2つの例として、Karger-Steinアルゴリズム[1]と最小フィードバックアークセットのモンテカルロアルゴリズムがあります。[2]
この名前は、ギャンブルの象徴として世界中でよく知られているモナコ公国のモンテカルロカジノを指しています。「モンテカルロ」という用語は、1947年にニコラスメトロポリスによって初めて導入されました。[3]
ラスベガス アルゴリズムはモンテ カルロ アルゴリズムのデュアルであり、間違った答えを返すことはありません。ただし、作業の一環としてランダムな選択を行う場合があります。その結果、同じ入力であっても、実行ごとに所要時間が異なる場合があります。
モンテカルロ アルゴリズムによって与えられた答えが正しいかどうかを検証する手順があり、正解の確率が 0 より上に限られている場合、確率 1 でアルゴリズムを繰り返し実行しながら答えをテストすると、最終的に正解が得られます。このプロセスがラスベガス アルゴリズムであるかどうかは、確率 1 で停止することが定義を満たすと見なされるかどうかによって決まります。
片側誤差と両側誤差
決定論的アルゴリズムによって返される答えは常に正しいと期待されますが、モンテカルロ アルゴリズムの場合はそうではありません。決定問題の場合、これらのアルゴリズムは一般に、偽バイアスまたは真バイアスのいずれかに分類されます。偽バイアスのモンテカルロ アルゴリズムは、 false を返す場合は常に正しく、真バイアスのアルゴリズムは、 trueを返す場合は常に正しいです。これは片側誤差のアルゴリズムについて説明していますが、バイアスがないアルゴリズムもあります。これらは両側誤差があると言われています。それらが提供する答え ( trueまたはfalse ) は、ある限られた確率で正しくないか正しくなります。
たとえば、ソロベイ・シュトラッセンの素数判定は、与えられた数が素数かどうかを判定するために使用されます。素数入力に対しては常に真と答え、合成数入力に対しては少なくとも1 ⁄ 2 の確率で偽と答え、1 ⁄ 2未満の確率で真と答えます。したがって、アルゴリズムからの偽の回答は確実に正しいのに対し、真の回答は不確実なままです。これは1 ⁄ 2正しい偽バイアスアルゴリズムと言われています。
増幅
片側誤差のモンテカルロアルゴリズムの場合、アルゴリズムをk回実行することで失敗の確率を下げることができます (成功の確率は増幅されます)。 1 ⁄ 2正解で偽バイアスのある Solovay–Strassen アルゴリズムをもう一度考えてみましょう。このアルゴリズムを複数回実行して、k回の反復で偽の応答に達した場合は偽の回答を返し、それ以外の場合はtrue を返します。したがって、数が素数の場合は回答は常に正解であり、数が合成数の場合は少なくとも 1−(1− 1 ⁄ 2 ) k = 1−2 −kの確率で正解になります。
両側誤差を持つモンテカルロ決定アルゴリズムの場合、アルゴリズムをk回実行し、回答の 多数決関数を返すことで、失敗確率をさらに低減できます。
複雑度クラス
複雑性クラス BPP は、両側誤りの確率が制限された多項式時間モンテカルロアルゴリズムで解ける決定問題を表します。複雑性クラスRP は、片側誤りの確率が制限されたモンテカルロアルゴリズムで解ける問題を表します。つまり、正解が偽の場合、アルゴリズムは常にそのように答えますが、正解が真である場合でも誤って偽と答える場合があります。[4]対照的に、複雑性クラスZPP は、多項式期待時間ラスベガスアルゴリズムで解ける問題を表します。ZPP ⊆ RP ⊆ BPPですが、これらの複雑性クラスが互いに異なるかどうかはわかっていません。つまり、モンテカルロアルゴリズムはラスベガスアルゴリズムよりも計算能力が高い可能性がありますが、これは証明されていません。[4]別の複雑性クラスPPは、コインを投げるよりも正確ですが、誤り確率が必ずしも1 ⁄ 2から制限されるわけではない多項式時間モンテカルロアルゴリズムによる決定問題を表します。[4]
モンテカルロ法とラスベガス法のクラス
ランダム化アルゴリズムは主にモンテカルロ法とラスベガス法の2つの主要なタイプに分けられますが、これらは階層の最上位に過ぎず、さらに分類することができます。[4]
- ラスベガス
- シャーウッド - 「ラスベガスの高性能かつ効果的な特別ケース」
- 数値—「数値ラスベガス」
- モンテカルロ
- アトランティック シティ—「モンテカルロ法の限定誤差の特殊ケース」
- 数値的 - 「数値近似モンテカルロ」
「ラスベガス法とモンテカルロ法はどちらも決定、つまり決定版の問題を扱っています。」[4]「しかし、これは誤った印象を与えて、これらのアルゴリズムをそのような問題に限定するべきではありません。両方のタイプのランダム化アルゴリズムは、出力が単純な「はい」または「いいえ」ではなく、本質的に数値的な結果を受け取る必要がある数値問題にも使用できます。」[4]
上の表はモンテカルロ法とラスベガス法のランダム化アルゴリズムの一般的な枠組みを表しています。[4]数学記号の代わりにを使うこともできます。こうすると最悪の場合の確率が等しくなります。[4]
計算数論およびその他の分野への応用
よく知られているモンテカルロアルゴリズムには、ソロベイ–シュトラッセン素数性テスト、ベイリー–PSW素数性テスト、ミラー–ラビン素数性テスト、および計算群論におけるシュライアー–シムズアルゴリズムの特定の高速バリアントがあります。
確率が事前に分かっておらず、経験的に決定される確率最適化（SO）グループの一部であるアルゴリズムの場合、モンテカルロとそのようなアルゴリズムを統合して、「事前に計算された確率の境界と確率最適化コンポーネントの両方を持つ」ことが時々可能です。 [4]「そのようなアルゴリズムの例は、Ant Inspired Monte Carloです。」[4] [5]このようにして、「SOの欠点は軽減され、ソリューションへの信頼性が確立されました。」[4] [5]
参照
- モンテカルロ法、ランダムサンプルの採取に基づく物理シミュレーションおよび計算統計で使用されるアルゴリズム
- アトランティックシティアルゴリズム
- ラスベガスアルゴリズム
参考文献
引用
- ^ Karger, David R.; Stein, Clifford (1996 年 7 月). 「最小カット問題への新しいアプローチ」. J. ACM . 43 (4): 601–640. doi : 10.1145/234533.234534 . ISSN 0004-5411. S2CID 5385337.
- ^ Kudelić, Robert (2016-04-01). 「最小フィードバックアークセット問題のためのモンテカルロランダム化アルゴリズム」.応用ソフトコンピューティング. 41 : 235–246. doi :10.1016/j.asoc.2015.12.018.
- ^ メトロポリス、N. (1987)。 「モンテカルロ法の始まり」(PDF)。ロス アラモス サイエンス(スタニスワフ ウラムに捧げられた 1987 年の特別号): 125–130。
- ^ abcdefghijk クーデリッチ、ロバート;イヴコビッチ、ニコラ。タマラ・シュマグク（2023）。チョードリー、ジョティ。マハレ、パリクシット N.。ペルマル、ティナガラン;ジョシ、アミット（編）。 「ランダム化アルゴリズムの概要」。スマートシステムによるIOT。シンガポール: Springer Nature: 651–667。土井：10.1007/978-981-99-3761-5_57。ISBN 978-981-99-3761-5。
- ^ ab Kudelić, Robert; Ivković, Nikola (2019). 「Ant にヒントを得た最小フィードバックアークセットのモンテカルロアルゴリズム」.エキスパートシステムとアプリケーション. 122 : 108–117. doi :10.1016/j.eswa.2018.12.021. ISSN 0957-4174.
出典
- モトワニ、ラジーブ、ラガヴァン、プラバカール(1995)。ランダム化アルゴリズム。ニューヨーク：ケンブリッジ大学出版局。ISBN 0-521-47465-5。
- Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) 「第 5 章 確率分析とランダム化アルゴリズム」アルゴリズム入門(第 2 版)ボストン: MIT Press および McGraw-Hill。ISBN 0-262-53196-8。
- Berman, Kenneth A.; Paul, Jerome L. (2005) 「第 24 章 確率的アルゴリズムとランダム化アルゴリズム」アルゴリズム: 順次、並列、分散ボストン: Course Technology ISBN 0-534-42057-5。