拉斯维加斯算法

摘要：

拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解

提问编辑摘要

拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。

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循环约