第6章随机化算法

第六章随机化算法教学目标理解产生伪随机数的线性同余法掌握数值随机化算法的特点及应用掌握蒙特卡罗算法的特点及应用掌握拉斯维加斯算法的特点及应用掌握舍伍德算法的特点及应用6.1概述6.1.1随机化算法的类型及特点类型数值随机化算法蒙特卡罗算法拉斯维加斯算法舍伍德算法特点数值随机化算法常用于数值问题的求解，所得到的解往往都是近似解，而且近似解的精度随计算时间的增加不断提高。蒙特卡罗算法每次均能求得问题的一个准确解，但这个解未必是正确的。求得正确解的概率依赖于算法执行时所用的时间，所用的时间越多得到正确解的概率就越高。一般情况下，蒙特卡罗算法不能有效地确定求得的解是否正确。拉斯维加斯算法不会得到不正确的解，一旦找到一个解，那么这个解肯定是正确的。但是有时候拉斯维加斯算法可能找不到解。拉斯维加斯算法得到正确解的概率随着算法执行时间的增加而提高。舍伍德算法不会改变对应确定性算法的求解结果，每次运行都能够得到问题的解，并且所得到的解是正确的6.1.2随机数发生器随机数发生器产生随机数的方法伪随机数发生器通过一个固定的、可以重复的计算方法产生随机数的发生器线性同余法2,1mod)(10nmcbaadann，d为种子；b为系数，满足b≥0；c为增量，满足c≥0；m为模数，满足m0。b、c和m越大且b与m互质可使随机函数的随机性能更好思考：如何产生0-1之间的随机数？//建立随机数类RandomNumber#definem65536L#defineb1194211693L#definec12345LclassRandomNumber{private:unsignedlongd;//d为当前种子public:RandomNumber(unsignedlongs=0);//缺省值0表示由系统自动产生种子unsignedshortrandom(unsignedlongn);//产生0：n-1之间的随机整数doublefRandom();//产生[0,1)之间的随机实数};RandomNumber::RandomNumber(unsignedlongs){if(s==0)d=time(0);//用系统时间产生种子elsed=s;//由用户提供种子}unsignedshortRandomNumber::random(unsignedlongn){d=b*d+c;//用线性同余计算新的种子return(unsignedshort)((d16)%n);//把d的高16位映射到0~(n-1)范围内}doubleRandomNumber::fRandom(){//产生[0,1)之间的随机实数returnrandom(m)/double(m);}6.2数值随机化算法6.2.1计算π的值将n个点随机投向一个正方形，设落入此正方形内切圆（半径为r）中的点的数目为k，如图6-1a）所示。a)b)0xy11假设所投入的点落入正方形的任一点的概率相等，则所投入的点落入圆内的概为。当n足够大时，k与n之比就逼近这一概率，从而在具体实现时只以第一象限为样本且r取值为1，建立直角坐标系，如图6-1b）所示4422rrnk4doubleDarts(intn){staticRandomNumberdarts;intk=0,i;doublex,y;for(i=1;i=n;i++){x=darts.fRandom();//产生一个[0,1)之间的实数，赋给xy=darts.fRandom();//产生一个[0,1)之间的实数，赋给yif((x*x+y*y)=1)k++;}return4*k/double(n);}6.2.2计算定积分设f(x)是[0,1]上的连续函数且0≤f(x)≤1，需要计算积分值。假设向单位正方形内随机投入n个点，如果有m个点落入G内，则I近似等于随机点落入G内的概率，即I≈m/n10)(dxxfIy=f(x)01x1yG图6-2随机投点实验估算I值示意图doubleDarts(intn){staticRandomNumberdart;intk=0,i;doublex,y;for(i=1;i=n;i++){x=dart.fRandom();//产生一个[0,1)之间的实数，赋给xy=dart.fRandom();//产生一个[0,1)之间的实数，赋给yif(y=f(x))k++;}returnk/double(n);}6.3蒙特卡罗算法设p是一个实数，且0.5p1。如果蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该算法是p正确的。对于同一实例，蒙特卡罗算法不会给出两个不同的正确解，则称该算法是一致的。而对于一个一致的p正确的蒙特卡罗算法，要想提高获得正确解的概率，只需执行该算法若干次，从中选择出现频率最高的解即可。设蒙特卡罗算法是一致的p正确的。那么至少调用多少次蒙特卡罗算法，可以使得蒙特卡罗算法得到正确解的概率不低于？1)10(p问题描述设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|n/2时，称元素x是数组T的主元素算法描述TemplateclassTypeboolmajority(TypeT[],intn)//判定主元素的蒙特卡罗算法{RandomNumberrnd;inti=rnd.random(n)+1;//产生1~n之间的随机下标Typex=T[i];//随机选择数组元素intk=0;for(intj=1;j=n;j++)if(T[j]==x)k++;return(kn/2);//当kn/2时，T含有主元素}6.3.1主元素问题boolmajorityMC(TypeT[],intn,double){//重复次调用多次算法majorityintk=(int)ceil(log()/log(1-p));for(inti=1;i=k;i++)if(majority(T,n))returntrue;returnfalse;}6.3.2素数测试试除法用2,3,…,去除n，判断是否能被整除，如果能，则为合数，否则为素数。算法描述boolPrime(unsignedintn){intm=floor(sqrt(double(n)));for(inti=2;i=m;i++)if(n%i==0)returnfalse;returntrue;}nWilson定理对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!-1(modn)。费尔马小定理如果p是一个素数且a是整数，则ap≡a(modp)。特别地，若a不能被p整除，则ap-1≡1(modp)。二次探测定理如果p是一个素数，x是整数且0xp，则方程x2≡1(modp)的解为x=1，p-1。6.4拉斯维加斯算法设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)0。在更强意义下，要求存在一个常数δ0，使得对问题的每一个实例x均有p(x)≥δ。思考：给定一个拉斯维加斯算法，设p(x)是对输入x调用它获得问题的一个解的概率，s(x)和e(x)分别是算法对于具体实例x求解成功或失败所需的平均时间，算法找到具体实例x的一个解所需的平均时间是多少？)()()(1)()()())(1()()(xexpxpxsxnpxexpnxsxnp6.4.1整数因子分解整数因子分解将大于1的整数n分解为的形式p1,p2,…,pk是k个素数且p1p2…pk，m1,m2,…,mk是k个正整数如果n是一个合数，则n必有一个非平凡因子x，1xn，使得x可以整除n。给定一个合数n，求n的一个非平凡因子的问题称为整数n的因子分割问题。结合上节的素数测试问题，整数因子分解问题实质上可以转化为整数的因子分割问题kmkmmpppn2121试除法进行因子分割intSplit(intn){intk=floor(sqrt(double(n)));for(inti=2;i=k;i++)if(n%i==0)returni;return1;}思考：该算法有什么不足？能否设计一个随机算法进行因子分割？Pollard(n)算法进行因子分割（提高概率）产生0~n-1范围内的一个随机数x，令y=x;按照产生一系列的xi对于k=2j（j=0,1,2,…），以及，计算xi-xk与n的最大公因子d=gcd(xi-xk,n)，如果，则实现对n的一次分割，输出d。2,3,4,...in,1)mod(xx21ii122jjind1intPollard(intn){RandomNumberrnd;inti=1;intx=rnd.Random(n);//随机整数inty=x;intk=2;while(true){i++;x=(x*x-1)%n;intd=gcd(y-x,n);if((d1)&&(dn))returnd;if(i==k){y=x;k*=2;}}//endwhile()}6.4.2n皇后问题问题描述n皇后问题要求将n个皇后放在n×n棋盘的不同行、不同列、不同斜线的位置，找出相应的放置方案随机化措施对某行放置皇后的有效位置进行随机对某行所有列位置进行随机关键代码分析boolQueen::QueensLV(){RandomNumberrnd;//随机数产生器intk=1;//下一个放置的皇后编号intcount=1;//记录当前要放置的第k个皇后在第k行的有效位置数while((k=n)&&(count0)){count=0;for(inti=1;i=n;i++){x[k]=i;if(Place(k))y[count++]=i;//第k个皇后在第k行的有效位置存于y数组}//从有效位置中随机选取一个位置放置第k个皇后if(count0)x[k++]=y[rnd.Random(count)];}return(count0);//count0表示放置成功}boolQueen::QueensLV1(void)//棋盘上随机放置n个皇后拉斯维加斯算法{RandomNumberrnd;//随机数产生器intk=1;//下一个放置的皇后编号intcount=maxcout;//尝试产生随机位置的最大次数，用户根据需要设置while(k=n){inti=0;for(i=1;i=count;i++){x[k]=rnd.Random(n)+1;if(Place(k))break;//第k个皇后在第k行的有效位置存于y数组}if(i=count)k++;elsebreak;}return(kn);//kn表示放置成功}6.5舍伍德算法随机快速排序在3.5节确定性算法的基础上，引入随机性操作。随机操作——随机选择基准元素关键代码分析intRandPartition(inta[],intlow,inthigh)//随机划分{RandomNumberrandom;inti=random(high-low+1)+low;swap(a[low],a[i]);intj=Partition(a,low,high);returnj;}voidrqs(inta[],intleft,intright)//随机快速排序{if(leftright){intp=RandPartition(a,left,right);rqs(a,left,p-1);rqs(a,p+1,right);}}6.5.2线性时间选择确定性算法中，首先分组，然后取每一组的中位数，再取每组中位数的中位数，最后以该中位数为基准元素对n个元素进行划分引入随机性成分随机选择一个元素作为基准元素关键代码分析templateclassTypeTypesel