拉斯維加斯算法:拉斯維加斯算法的一個顯著特徵是它所作的隨機性決策有可能導 -百科知識中文網

拉斯維加斯算法的一個顯著特徵是它所作的隨機性決策有可能導致算法找不到所需的解。

void obstinate(Object x, Object y) {// 反覆調用拉斯維加斯算法LV(x,y)，直到找到問題的一個解y bool success= false; while (!success) success=lv(x,y); }設p(x)是對輸入x調用拉斯維加斯算法獲得問題的一個解的機率。一個正確的拉斯維加斯算法應該對所有輸入x均有p(x)>0。設t(x)是算法obstinate找到具體實例x的一個解所需的平均時間,s(x)和e(x)分別是算法對於具體實例x求解成功或求解失敗所需的平均時間，則有：

解此方程可得：

n後問題

對於n後問題的任何一個解而言，每一個皇后在棋盤上的位置無任何規律，不具有系統性，而更象是隨機放置的。由此容易想到下面的拉斯維加斯算法。

在棋盤上相繼的各行中隨機地放置皇后，並注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后已相容地放置好，或已沒有下一個皇后的可放置位置時為止。

如果將上述隨機放置策略與回溯法相結合，可能會獲得更好的效果。可以先在棋盤的若干行中隨機地放置皇后，然後在後繼行中用回溯法繼續放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，後繼回溯搜尋所需的時間就越少，但失敗的機率也就越大。

拉斯維加斯算法

整數因子分解

設n>1是一個整數。關於整數n的因子分解問題是找出n的如下形式的唯一分解式：拉斯維加斯算法其中，p1<p2<…<pk是k個素數，m1,m2,…,mk是k個正整數。如果n是一個合數，則n必有一個非平凡因子x，1<x<n，使得x可以整除n。給定一個合數n，求n的一個非平凡因子的問題稱為整數n的因子分割問題。

int Split(int n){ int m = floor(sqrt(double(n))); for (int i=2; i<=m; i++) if (n%i==0) return i; return 1;}

事實上，算法split(n)是對範圍在1～x的所有整數進行了試除而得到範圍在拉斯維加斯算法的任一整數的因子分割。

Pollard算法

在開始時選取0～n-1範圍內的隨機數，然後遞歸地由

產生無窮序列

對於

，以及

，算法計算出xj-xi與n的最大公因子d=gcd(xj-xi，n)。如果d是n的非平凡因子，則實現對n的一次分割，算法輸出n的因子d。void Pollard(int n){// 求整數n因子分割的拉斯維加斯算法 RandomNumber rnd; int i=1; int x=rnd.Random(n); // 隨機整數int y=x; int k=2; while (true) { i++; x=(x*x-1)%n;int d=gcd(y-x,n); // 求n的非平凡因子 if ((d>1) && (d<n)) cout><<d><<endl; if (i==k) { y=x; k*=2;} } }>

對Pollard算法更深入的分析可知，執行算法的while循環約