Loading article…
コンピューティングにおいて、ラスベガスアルゴリズムは、常に正しい結果を返すランダム化アルゴリズムです。つまり、常に正しい結果を生成するか、失敗を通知します。ただし、ラスベガスアルゴリズムの実行時間は入力によって異なります。ラスベガスアルゴリズムの通常の定義には、期待実行時間が有限であるという制約が含まれます。ここで期待値は、アルゴリズムで使用されるランダム情報またはエントロピーの空間で実行されます。別の定義では、ラスベガスアルゴリズムは常に終了する（有効である）が、解を見つける失敗を示すために解空間の一部ではないシンボルを出力する可能性があると要求されます。[ 1 ]ラスベガスアルゴリズムの性質により、可能な解の数が限られており、候補解の正しさを検証することが比較的容易である一方で、解を見つけることが複雑な状況に適しています。
命題充足可能性（SAT）のためのデイビス・パトナムアルゴリズムのいくつかの変種など、計算が困難な問題に対する体系的な探索方法も非決定論的な決定を利用するため、ラスベガスアルゴリズムとみなすこともできる。[ 2 ]
ラスベガスアルゴリズムは、1979 年にグラフ同型問題の文脈で、モンテカルロアルゴリズムの双対としてLászló Babaiによって導入されました。[ 3 ] Babai [ 4 ]は、コイン投げの例とともに「ラスベガスアルゴリズム」という用語を導入しました。このアルゴリズムは一連の独立したコイン投げに依存しており、失敗する可能性（結果が出ない）はわずかにあります。しかし、モンテカルロアルゴリズムとは対照的に、ラスベガスアルゴリズムは報告された結果の正しさを保証できます。
int getRandomInteger ( int n ) { Random rand = new Random ( ); return rand.nextInt ( n ) ; }// Las Vegas algorithm, assuming a is array of length n.// Goal: return a correct index k such that a[k] == 1.intlasVegasAlgorithm(int[]a){intn=a.length;while(true){intk=getRandomInteger(n);if(a[k]==1){returnk;}}}As mentioned above, Las Vegas algorithms always return correct results. The code above illustrates this property. The goal is to find an index in the array a that contains the value 1. A variable k is generated randomly; after k is generated, k is used to index the array a. If this index contains the value 1, then k is returned; otherwise, the algorithm repeats this process until it finds 1. Although this Las Vegas algorithm is guaranteed to find the correct answer, it does not have a fixed runtime; due to the randomization, it is possible for arbitrarily much time to elapse before the algorithm terminates.
This section provides the conditions that characterize an algorithm's being of Las Vegas type.
An algorithm A is a Las Vegas algorithm for problem class X, if[5]
There are three notions of completeness for Las Vegas algorithms:
Let P(RTA,x ≤ t) denote the probability that A finds a solution for a soluble instance x in time within t, then A is complete exactly if for each x there exists
some tmax such that P(RTA,x ≤ tmax) = 1.
近似的な完全性は主に理論的な関心事であり、解を見つけるための時間的制約は通常、実用には大きすぎる。
ラスベガスアルゴリズムは、問題設定に基づいて異なる評価基準を持ちます。ラスベガスアルゴリズムには時間計算量が固定されていないため、これらの基準は異なる時間制限を持つ3つのカテゴリに分けられます。以下に、考えられる適用シナリオをいくつか示します。
（タイプ1とタイプ2はタイプ3の特殊なケースです。）
時間制限のないタイプ1の場合、平均実行時間は実行時の挙動を表すことができます。しかし、タイプ2の場合はそうではありません。
ここで、P ( RT ≤ t max ) は、時間内に解を見つける確率であり、実行時の挙動を表します。
タイプ 3 の場合、実行時の挙動は、 rtd ( t ) = P ( RT ≤ t ) と定義される実行時分布関数rtd : R → [0,1]またはその近似によってのみ表現できます。
実行時分布（RTD）は、ラスベガスアルゴリズムの実行時動作を記述する独特な方法である。
このデータを使用すると、任意の時間制限tに対する平均実行時間、標準偏差、中央値、パーセンタイル、成功確率P ( RT ≤ t ) などの他の基準を簡単に取得できます。
ラスベガスアルゴリズムは、検索問題で頻繁に登場します。たとえば、オンラインで情報を探している人は、目的の情報を求めて関連するウェブサイトを検索するかもしれません。そのため、時間計算量は、「運が良ければ」すぐにコンテンツが見つかる場合から、「運が悪ければ」膨大な時間を費やす場合まで様々です。適切なウェブサイトが見つかれば、エラーの可能性はなくなります。[ 6 ]
def randomized_quicksort ( a : list [ int ]) -> None : if len ( a ) == 1 : return A # Aはソート済みです。else : i : int = random.randrange ( 1 , len ( a )) # [1, len(a))の範囲の乱数を取得しますx : int = a [ i ] #ピボット要素# 上図に示すように、a を要素 < x、x、および > x に分割します。# a[1 : i- 1] と A[i + 1 : n] に対してクイックソートを実行します。# 結果を結合して、ソートされた配列を取得します。簡単な例として、ランダム化クイックソートがあります。これは、ピボットをランダムに選択し、要素をピボットより小さい要素、ピボットと等しい要素、ピボットより大きい要素の3つのパーティションに分割します。クイックソートは常に解を生成します。この場合、それはソートされた配列です。残念ながら、時間計算量はそれほど単純ではありません。実行時間は、どの要素をピボットとして選択するかによって変わることがわかります。
クイックソートの実行時間は、ピボットの選択精度に大きく左右されます。ピボットの値が大きすぎたり小さすぎたりすると、分割のバランスが崩れ、実行効率が低下します。しかし、ピボットの値が配列の中央付近であれば、分割は比較的バランスよく行われ、実行時間が短縮されます。ピボットはランダムに選択されるため、実行時間はほとんどの場合良好ですが、まれに悪化することもあります。
平均値の場合、分析は入力分布ではなくアルゴリズムが行うランダムな選択に依存するため、判断は困難です。クイックソートの平均値は、アルゴリズムがピボットを選択する際に取り得るすべてのランダムな選択に基づいて計算されます。
最悪の場合の実行時間は Θ( n 2 ) ですが、平均的な場合の実行時間は Θ( n log n ) です。最悪の場合が発生することはあまりないことがわかります。n の値が大きい場合、実行時間は高い確率でΘ( n log n ) になります。
ピボットが毎回中央の値の要素になる確率はn個に 1 個であり、これは非常にまれであることに注意してください。ただし、再帰ツリーの深さは依然としてO ( log n ) であり、各レベルの再帰がO ( n ) 回実行されるため、分割が 50% – 50% ではなく 10% – 90% の場合でも実行時間は同じです。
8クイーン問題は通常、バックトラッキングアルゴリズムで解かれます。しかし、ラスベガスアルゴリズムを適用することも可能であり、実際、バックトラッキングよりも効率的です。
チェス盤に8個のクイーンを配置し、互いに攻撃し合わないようにしてください。クイーンは同じ行、列、対角線上の駒を攻撃することを覚えておいてください。
k行（0 ≤ k ≤ 8）が女王によって正常に占有されていると仮定します。
k = 8の場合は、処理を成功として停止します。そうでない場合は、k + 1 行目の処理に進みます。
この行で既存のクイーンに攻撃されていない位置をすべて計算します。そのような位置がない場合は失敗します。そうでない場合は、ランダムに1つ選択し、kをインクリメントして繰り返します。
クイーンを配置できない場合は、アルゴリズムは単純に失敗することに注意してください。しかし、このプロセスは繰り返すことができ、毎回異なる配置が生成されます。[ 7 ]
期待実行時間が多項式時間であるラスベガスアルゴリズムを持つ決定問題の複雑性クラスはZPPである。
調べてみると、
これは、ラスベガスアルゴリズムの構築方法と密接に関係しています。具体的には、クラスRP は、正解が「いいえ」の場合は常に正解を返すが、正解が「はい」の場合は 1 から離れた一定の確率で誤答することが許容される、ランダム化多項式時間アルゴリズムが存在するすべての決定問題で構成されます。このようなアルゴリズムが問題とその補問題 (「はい」と「いいえ」の答えを入れ替えたもの) の両方に存在する場合、2 つのアルゴリズムを同時に繰り返し実行できます。つまり、どちらかが確定的な答えを返すまで、それぞれを一定ステップずつ交互に実行します。これが、期待多項式時間で実行されるラスベガスアルゴリズムを構築する標準的な方法です。一般に、ラスベガスアルゴリズムの実行時間には最悪の場合の上限がないことに注意してください。
ラスベガスアルゴリズムを最適化するには、期待実行時間を最小限に抑える必要があります。これは以下の方法で実現できます。
最適戦略の存在は、理論的には興味深い考察かもしれない。しかし、TA ( x )の分布に関する情報を見つけるのは容易ではないため、現実には実用的ではない。さらに、ほとんどの場合、任意のxに対して答えは一度しか必要とされないため、分布に関する情報を得るために実験を繰り返し実行しても意味がない。[ 8 ]
ラスベガスアルゴリズムは、モンテカルロアルゴリズムとは対照的です。モンテカルロアルゴリズムでは、使用されるリソースは制限されていますが、結果が一定の（通常は小さい）確率で誤っている可能性があります。ラスベガスアルゴリズムは、設定された時間実行し、終了しない場合にランダムな結果を生成することで、モンテカルロアルゴリズムに変換できます。マルコフの不等式を適用することで、ラスベガスアルゴリズムが設定された制限を超える確率の上限を設定できます。
ラスベガスアルゴリズムとモンテカルロアルゴリズムを比較した表を以下に示します。[ 9 ]
正しさを判定する決定論的な方法があれば、モンテカルロアルゴリズムをラスベガスアルゴリズムに変換することが可能です。しかし、アルゴリズムをテストする方法がなければ、モンテカルロアルゴリズムをラスベガスアルゴリズムに変換するのは困難です。一方、ラスベガスアルゴリズムをモンテカルロアルゴリズムに変換するのは簡単です。信頼度パラメータで指定された一定期間、ラスベガスアルゴリズムを実行することで実現できます。アルゴリズムがその時間内に解を見つけられれば成功、そうでなければ単に「申し訳ありません」と出力すればよいのです。
これは比較のためのラスベガスアルゴリズムとモンテカルロアルゴリズムの例です: [ 10 ]
長さが偶数nの配列があるとします。配列の要素の半分は 0 で、残りの半分は 1 です。ここでの目標は、1 を含むインデックスを見つけることです。
// ラスベガスのアルゴリズムint lasVegasAlgorithm ( int [] a ) { int n = a .長さ; while ( true ) { int k = getRandomInteger ( n ); if ( a [ k ] == 1 ) { return k ; } } }// モンテカルロアルゴリズムint monteCarloAlgorithm ( int [] a ) { int n = a . length ; for ( int i = 0 ; i < 300 ; ++ i ) { int k = getRandomInteger ( n ); if ( a [ k ] == 1 ) { return k ; } } return - 1 ; // 失敗を示す}ラスベガスアルゴリズムは配列内に「1」が見つかるまで終了しないため、正しさではなく実行時間を賭けることになります。一方、モンテカルロ法は300回実行されるため、実際にコードを実行するまで、300回のループで配列内に「1」が見つかるかどうかは分かりません。解が見つかる場合もあれば、見つからない場合もあります。したがって、ラスベガスアルゴリズムとは異なり、モンテカルロ法は実行時間ではなく正しさを賭けることになります。