第7章 概率算法2

17.4拉斯维加斯(LasVegas)算法舍伍德型算法的优点是其时间复杂性对所有实例而言相对均匀，但与其相应的确定性算法相比，其平均时间复杂性没有改进。拉斯维加斯算法能显著地改进算法的有效性。甚至对某些迄今为止找不到有效算法的问题，也能找到满意的结果。2拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。voidobstinate(Objectx,Objecty){//反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解yboolsuccess=false;while(!success)success=lv(x,y);}其中x是输入参数，当success的值为true时，y返回问题的解。当success的值为false时，未能找到解。3设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有：))()())((1()()()(xtxexpxsxpxt解此方程可得：)()()(1)()(xexpxpxsxt47.4.1n后问题对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到下面的拉斯维加斯算法。在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。5如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。stopVegaspset01.0000262.00--262.0050.503933.8847.2380.39120.046513.0010.20222.1167.4.2整数因子分解设n1是一个整数。关于整数n的因子分解问题是找出n的如下形式的唯一分解式：kmkmmpppn2121其中，p1p2…pk是k个素数，m1,m2,…,mk是k个正整数。7如果n是一个合数，则n必有一个非平凡因子x，1xn，使得x可以整除n。给定一个合数n，求n的一个非平凡因子的问题称为整数n的因子分割问题。intSplit(intn){intm=floor(sqrt(double(n)));for(inti=2;i=m;i++)if(n%i==0)returni;return1;}事实上，算法split(n)是对范围在1～x的所有整数进行了试除而得到范围在1～x2的任一整数的因子分割。8Pollard算法在开始时选取0～n-1范围内的随机数，然后递归地由nxxiimod)1(21产生无穷序列,,,,21kxxx对于i=2k，以及2kj2k+1，算法计算出xj-xi与n的最大公因子d=gcd(xj-xi，n)。9如果d是n的非平凡因子，则实现对n的一次分割，算法输出n的因子d。voidPollard(intn){//求整数n因子分割的拉斯维加斯算法RandomNumberrnd;inti=1;intx=rnd.Random(n);//随机整数inty=x;intk=2;while(true){i++;x=(x*x-1)%n;intd=gcd(y-x,n);//求n的非平凡因子if((d1)&&(dn))coutdendl;if(i==k){y=x;k*=2;}}}10对Pollard算法更深入的分析可知，执行算法的while循环约次后，Pollard算法会输出n的一个因子p。由于n的最小素因子p，故Pollard算法可在O(n1/4)时间内找到n的一个素因子。pn117.5蒙特卡罗(MonteCarlo)算法在实际应用中常会遇到一些问题，不论采用确定性算法或概率算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。127.5.1蒙特卡罗(MonteCarlo)算法的基本思想设p是一个实数，且1/2p1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。13有些蒙特卡罗算法除了具有描述问题实例的输入参数外，还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。输入参数+错解接受概率参数14对于一个一致的p正确蒙特卡罗算法，要提高获得正确解的概率，只要执行该算法若干次，并选择出现频次最高的解即可。如果重复调用一个一致的(1/2+)正确的蒙特卡罗算法2m-1次，得到正确解的概率至少为1-，其中，miimimi4)41()41(221221015对于一个解所给问题的蒙特卡罗算法MC(x)，如果存在问题实例的子集X使得：(1)当xX时，MC(x)返回的解是正确的；(2)当xX时，正确解是y0，但MC(x)返回的解未必是y0。称上述算法MC(x)是偏y0的算法。重复调用一个一致的，p正确偏y0蒙特卡罗算法k次，可得到一个O(1-(1-p)k)正确的蒙特卡罗算法，且所得算法仍是一个一致的偏y0蒙特卡罗算法。167.5.2主元素问题设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|n/2时，称元素x是数组T的主元素。templateclassTypeboolMajority(Type*T,intn){//判定主元素的蒙特卡罗算法inti=rnd.Random(n)+1;Typex=T[i];//随机选择数组元素intk=0;for(intj=1;j=n;j++)if(T[j]==x)k++;return(kn/2);//kn/2时T含有主元素}17templateclassTypeboolMajorityMC(Type*T,intn,doublee){//重复调用算法Majorityintk=ceil(log(1/e)/log(2));for(inti=1;i=k;i++)if(Majority(T,n))returntrue;returnfalse;}对于任何给定的0，算法majorityMC重复调用log(1/)次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于。算法majorityMC所需的计算时间显然是O(nlog(1/))。187.5.3素数测试Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!-1(modn)。费尔马小定理：如果p是一个素数，且0ap，则ap-1(modp)。二次探测定理：如果p是一个素数，且0xp，则方程x21(modp)的解为x=1，p-1。19voidpower(unsignedinta,unsignedintp,unsignedintn,unsignedint&result,bool&composite){//计算modn，并实施对n的二次探测unsignedintx;if(p==0)result=1;else{power(a,p/2,n,x,composite);//递归计算result=(x*x)%n;//二次探测if((result==1)&&(x!=1)&&(x!=n-1))composite=true;if((p%2)==1)//p是奇数result=(result*a)%n;}}20boolPrime(unsignedintn){//素数测试的蒙特卡罗算法RandomNumberrnd;unsignedinta,result;boolcomposite=false;a=rnd.Random(n-3)+2;power(a,n-1,n,result,composite);if(composite||(result!=1))returnfalse;elsereturntrue;}算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。