Loading article…
ランダム化アルゴリズムとは、その論理または手順の一部としてある程度のランダム性を用いるアルゴリズムのことです。このアルゴリズムは通常、一様乱数ビットを補助入力として使用し、その動作を制御します。これは、乱数ビットによって決定されるあらゆるランダムな選択肢の中で、「平均的な場合」において良好なパフォーマンスを達成することを目的としています。したがって、実行時間、出力（またはその両方）はランダム変数となります。
ランダムな入力を使用して常に正しい答えで終了するが、期待実行時間が有限であるアルゴリズム（例えばクイックソート[ 1 ]のようなラスベガスアルゴリズム）と、誤った結果を生成する可能性がある（例えばMFAS問題に対するモンテカルロアルゴリズム[ 2 ]のようなモンテカルロアルゴリズム）または失敗を通知したり終了できなかったりして結果を生成できないアルゴリズムとの間には区別がある。場合によっては、確率的アルゴリズムが問題を解決する唯一の実用的な手段となる。[ 3 ]
一般的に、ランダム化アルゴリズムは、真の乱数発生器の代わりに擬似乱数発生器を用いて近似的に実装されます。このような実装では、理想的な真の乱数発生器の存在を前提とした理論的な挙動や数学的な保証から逸脱する可能性があります。
具体例として、n個の要素を持つ配列の中から「 a 」を見つける問題を考えてみましょう。
入力： n ≥ 2 個の要素からなる配列。要素の半分は「a」、残りの半分は「b」である。
出力:配列の中から「a 」を探します。
本稿では、ラスベガスアルゴリズムとモンテカルロアルゴリズムの2種類のアルゴリズムを示す。
ラスベガスのアルゴリズム：
findingA_LV (配列A 、n ) begin repeat n個の要素からランダムに1 つの要素を選択します。'a 'が見つかるまで繰り返しますendこのアルゴリズムは確率1で成功します。反復回数は変化し、任意に大きくすることができますが、期待される反復回数は
定数であるため、多数の呼び出しにおける期待実行時間は（ビッグシータ表記を参照）
モンテカルロアルゴリズム：
findingA_MC (配列A 、n 、k ) begin i := 0 repeat n個の要素からランダムに1 つの要素を選択します。i := i + 1 until i = kまたは'a'が見つかるまでend「a」が見つかればアルゴリズムは成功し、そうでなければアルゴリズムは失敗します。k回の反復後、 「 a 」が見つかる確率は次のとおりです。
このアルゴリズムは成功を保証するものではありませんが、実行時間は制限されています。反復回数は常にk以下です。kを定数とすると、実行時間（期待値と絶対値）は次のようになります。。
ランダム化アルゴリズムは、囚人のジレンマのように、悪意のある「敵対者」や攻撃者が意図的にアルゴリズムに不正な入力を与えようとする場合に特に役立ちます（最悪ケースの複雑性と競合分析（オンラインアルゴリズム）を参照） 。このため、ランダム性は暗号学において遍在しています。暗号アプリケーションでは、擬似乱数は使用できません。なぜなら、敵対者が擬似乱数を予測でき、アルゴリズムが事実上決定論的になってしまうからです。したがって、真の乱数の発生源、または暗号学的に安全な擬似乱数生成器のいずれかが必要です。ランダム性が本質的に存在するもう1つの分野は量子コンピューティングです。
上記の例では、ラスベガスアルゴリズムは常に正しい答えを出力しますが、その実行時間はランダム変数です。モンテカルロアルゴリズム（シミュレーションのモンテカルロ法に関連）は、入力サイズとそのパラメータkの関数によって制限される時間内に完了することが保証されていますが、わずかなエラーの確率を許容します。任意のラスベガスアルゴリズムは、指定された時間内に完了しない場合に任意の、場合によっては誤った答えを出力するようにすることで、（マルコフの不等式を介して）モンテカルロアルゴリズムに変換できることに注意してください。逆に、答えが正しいかどうかを確認する効率的な検証手順が存在する場合、モンテカルロアルゴリズムを正しい答えが得られるまで繰り返し実行することで、モンテカルロアルゴリズムをラスベガスアルゴリズムに変換できます。
計算複雑性理論では、ランダム化アルゴリズムを確率的チューリングマシンとしてモデル化します。 ラスベガスアルゴリズムとモンテカルロアルゴリズムの両方が考慮され、いくつかの複雑性クラスが研究されています。最も基本的なランダム化複雑性クラスは RP であり、これは NO インスタンスを絶対的な確実性で認識し、YES インスタンスを少なくとも 1/2 の確率で認識する効率的な (多項式時間) ランダム化アルゴリズム (または確率的チューリングマシン) が存在する決定問題のクラスです。RP の補集合は co-RP です。平均実行時間が多項式時間で、出力が常に正しい (終了しない可能性のある) アルゴリズムを持つ問題クラスはZPPに属すると言われます。
YESとNOの両方のインスタンスを多少の誤差を伴って識別することが許容される問題のクラスはBPPと呼ばれます。このクラスはPのランダム化版として機能し、つまりBPPは効率的なランダム化アルゴリズムのクラスを表します。
クイックソートは1959年にトニー・ホーアによって発見され、1961年に発表された。[ 4 ]同年、ホーアはリストの中央値を線形期待時間で見つけるクイックセレクトアルゴリズムを発表した。[ 5 ]決定論的な線形時間アルゴリズムが存在するかどうかは1973年まで未解決のままだった。[ 6 ]
1917年、ヘンリー・キャボーン・ポックリントンは、素数を法とする平方根を効率的に求めるためのポックリントンのアルゴリズムとして知られるランダム化アルゴリズムを導入した。[ 7 ] 1970年、エルウィン・バーレカンプは、有限体上の多項式の根を効率的に計算するためのランダム化アルゴリズムを導入した。[ 8 ] 1977年、ロバート・M・ソロベイとフォルカー・シュトラッセンは、多項式時間ランダム化素数判定法（つまり、数の素数を判定する法）を発見した。その後まもなく、マイケル・O・ラビンは、1976年のミラーの素数判定法も多項式時間ランダム化アルゴリズムに変換できることを示した。当時、素数判定のための証明可能な多項式時間決定論的アルゴリズムは知られていなかった。
最も初期のランダム化データ構造の 1 つはハッシュ テーブルであり、これは 1953 年にIBMのHans Peter Luhnによって導入されました。[ 9 ] Luhn のハッシュ テーブルは、衝突を解決するために連鎖を使用し、リンク リストの最初の応用例の 1 つでもありました。[ 9 ]その後、1954 年にIBM ResearchのGene Amdahl、Elaine M. McGraw、Nathaniel Rochester、およびArthur Samuel が線形プロービングを導入しましたが、[ 9 ] Andrey Ershov は1957 年に独立して同じアイデアを持っていました。[ 9 ] 1962 年にDonald Knuth が線形プロービングの最初の正しい分析を行いましたが、[ 9 ]彼の分析を含むメモランダムは、ずっと後になってから公開されました。[ 10 ]最初の公開された分析は、1966 年に Konheim と Weiss によるものでした。[ 11 ]
ハッシュテーブルに関する初期の研究では、完全にランダムなハッシュ関数へのアクセスを前提とするか、キー自体がランダムであると前提としていました。[ 9 ] 1979年、カーターとウェグマンはユニバーサルハッシュ関数を導入し、[ 12 ]これによって、操作ごとの期待時間が一定である連鎖ハッシュテーブルを実装できることを示しました。
ランダム化データ構造に関する初期の研究は、ハッシュテーブル以外にも及んだ。1970年、バートン・ハワード・ブルームは、ブルームフィルタとして知られる近似メンバーシップデータ構造を導入した。[ 13 ] 1989年、ライムント・ザイデルとセシリア・R・アラゴンは、treapとして知られるランダム化バランス探索木を導入した。[ 14 ]同年、 ウィリアム・ピューは、スキップリストとして知られる別のランダム化探索木を導入した。[ 15 ]
コンピュータサイエンスでランダム化アルゴリズムが普及する以前、ポール・エルデシュは、数学的対象の存在を確立するための数学的手法としてランダム化構成の使用を普及させた。この手法は確率的方法として知られるようになった。[ 16 ]エルデシュは、1947年に単純なランダム化構成を使用してラムゼーグラフの存在を確立したときに、確率的方法を初めて適用した。 [ 17 ]彼は、1959年に、より洗練されたランダム化アルゴリズムを使用して、高い周長と彩色数を持つグラフの存在を確立したことで有名である。[ 18 ] [ 16 ]
クイックソートは、ランダム性が役立つ、よく知られた一般的なアルゴリズムです。このアルゴリズムの多くの決定論的なバージョンでは、明確に定義されたある種の退化入力（既にソートされた配列など）に対してn個の数値をソートするのにO ( n² )の時間が必要となり、この動作を引き起こす入力の特定のクラスは、ピボット選択のプロトコルによって定義されます。しかし、アルゴリズムがピボット要素を均一にランダムに選択する場合、入力の特性に関係なく、O ( n log n )の時間で完了する確率が証明されています。
計算幾何学では、凸包やドロネー三角形分割のような構造を構築する標準的な手法として、入力点をランダムに並べ替え、既存の構造に1つずつ挿入する方法があります。ランダム化により、挿入によって構造に生じる変更の期待値が少なくなり、アルゴリズムの実行時間の期待値を上限付きで制限することができます。この手法は、ランダム化増分構築法として知られています。[ 19 ]
入力:グラフG ( V , E )
出力：頂点をLとRに分割するカット。LとRの間には最小数のエッジが存在する。
（多重）グラフにおいて、2つのノードuとvを縮約すると、 uとvを結ぶエッジを除く、 uまたはvに接続するエッジの和集合であるエッジを持つ新しいノードu 'が生成されることを思い出してください。図1は、頂点AとBの縮約の例を示しています。縮約後、結果として得られるグラフには平行エッジが存在する可能性がありますが、自己ループは含まれません。
カーガー[ 20 ]の基本アルゴリズム：
始める i = 1 繰り返し繰り返し G 内の任意の辺 (u,v) ∈ E を取る uとvを縮約形u'に置き換える ノードが2つだけになるまで 対応するカット結果 C iを取得します i = i + 1 i = mになるまでC 1、 C 2、 ...、 C m の中から最小カットを出力します。 終了
外側のループの各実行において、アルゴリズムは内側のループを繰り返し、ノードが 2 つだけ残って対応するカットが得られるまで続けます。1 回の実行時間は、nは頂点の数を表します。外側のループをm回実行した後、すべての結果の中から最小のカットを出力します。図2は、アルゴリズムの実行例を示しています。実行後、サイズ3のカットが得られます。
補題 1 — k を最小カットサイズとし、C = { e 1 , e 2 , ..., e k } を最小カットとする。反復iにおいて、収縮のためにエッジe ∈ Cが選択されない場合、 C i = Cとなる。
Gが連結でない場合、 GはLとRの間にエッジを持たずに分割できます。したがって、非連結グラフの最小カットは0です。ここで、 Gが連結であると仮定します。V = L ∪ RをCによって誘導されるVの分割とします。C = { { u , v } ∈ E : u ∈ L , v ∈ R } ( Gは連結なのでwell-definedです)。Cのエッジ{ u , v }を考えます。最初は、u、vは異なる頂点です。エッジを選択する限り、 、 uとv はマージされません。したがって、アルゴリズムの最後に、グラフ全体をカバーする 2 つの複合ノードが得られます。1 つはLもう 1 つはR。図 2 と同様に、最小カットのサイズは 1 であり、C= {(A、BA、Bを選択しない場合、最小カットを取得できます。
補題2 — Gがp個の頂点を持つ多重グラフであり、その最小カットのサイズがkである場合、Gは少なくともpk /2個のエッジを持つ。
最小カットはkなので、すべての頂点v はdegree( v ) ≥ kを満たさなければなりません。したがって、次数の合計は少なくともpkです。しかし、頂点の次数の合計は 2 | E |に等しいことはよく知られています。補題が成り立ちます。
アルゴリズムが成功する確率は、1 − すべての試行が失敗する確率です。独立性により、すべての試行が失敗する確率は
補題1より、 C i = Cとなる確率は、反復i中にCの辺が選択されない確率である。内側のループを考え、j ∈ {0, 1, …, n − 3}であるj回の辺の縮約後のグラフをG jとする。G jはn − j個の頂点を持つ。条件付き可能性の連鎖律を用いる。反復jで選択された辺がCに含まれない確率は、 Cの辺がこれまで選択されていないという条件の下で、次のようになる。G j は依然としてサイズkの最小カットを持つので、補題 2 により、少なくとも端。
したがって、。
連鎖律によれば、最小カットCを見つける確率は
キャンセルはしたがって、アルゴリズムが成功する確率は少なくとも。 のためにこれは、アルゴリズムは確率で最小カットを見つけるやがて。
ランダム性は、空間や時間のようなリソースと見なすことができます。デランダム化とは、ランダム性を取り除く（または可能な限り少なく使用する）プロセスです。[ 21 ] [ 22 ]すべてのアルゴリズムの実行時間を大幅に増加させることなくデランダム化できるかどうかは、現時点ではわかっていません。 [ 23 ]例えば、計算複雑性では、P = BPPかどうかはわかっていません。[ 23 ]つまり、小さなエラー確率で多項式時間で実行される任意のランダム化アルゴリズムを、ランダム性を使用せずに多項式時間で実行するようにデランダム化できるかどうかはわかりません。
特定のランダム化アルゴリズムを非ランダム化するために使用できる具体的な方法がいくつかあります。
計算モデルをチューリングマシンに限定した場合、ランダムな選択を行う能力によって、その能力がなければ多項式時間で解けない問題が多項式時間で解けるようになるかどうかは、現在未解決の問題である。これは、P = BPP であるかどうかの問題である。しかし、他の文脈では、ランダム化によって厳密な改善が得られる問題の具体的な例が存在する。
![{\displaystyle \Pr[\mathrm {find~a} ]=1-(1/2)^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c3fa724b0da3c3ac125350c4d0703329e0eabbc)
![\displaystyle \Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/327acc4529b1f6daba99ac1e9938a7917f2bec82)
![{\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9a5ee0a8aef637a2522ae343d168d48bb739389)
