0047算法笔记——【随机化算法】拉斯维加斯(Las-Vegas)算法和n后问题

1、拉斯维加斯(LasVegas)算法拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失败的概率任意小。拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。[cpp]viewplaincopy1.voidobstinate(Objectx,Objecty)2.{//反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解y3.boolsuccess=false;4.while(!success)success=lv(x,y);5.}设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有。解此方程得：2、n后问题问题描速：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1)纯拉斯维加斯随机算法求解思路对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。具体实现代码如下：1、RandomNumber.h[cpp]viewplaincopy1.#includetime.h2.//随机数类3.constunsignedlongmaxshort=65536L;4.constunsignedlongmultiplier=1194211693L;5.constunsignedlongadder=12345L;6.7.classRandomNumber8.{9.private:10.//当前种子11.unsignedlongrandSeed;12.public:13.RandomNumber(unsignedlongs=0);//构造函数，默认值0表示由系统自动产生种子14.unsignedshortRandom(unsignedlongn);//产生0：n-1之间的随机整数15.doublefRandom(void);//产生[0,1)之间的随机实数16.};17.18.RandomNumber::RandomNumber(unsignedlongs)//产生种子19.{20.if(s==0)21.{22.randSeed=time(0);//用系统时间产生种子23.}24.else25.{26.randSeed=s;//由用户提供种子27.}28.}29.30.unsignedshortRandomNumber::Random(unsignedlongn)//产生0：n-1之间的随机整数31.{32.randSeed=multiplier*randSeed+adder;//线性同余式33.return(unsignedshort)((randSeed16)%n);34.}35.36.doubleRandomNumber::fRandom(void)//产生[0,1)之间的随机实数37.{38.returnRandom(maxshort)/double(maxshort);39.}2、7d4d1.cpp[cpp]viewplaincopy1.//随机化算法拉斯维加斯算法n后问题2.#includestdafx.h3.#includeRandomNumber.h4.#includecmath5.#includeiostream6.usingnamespacestd;7.8.classQueen9.{10.friendvoidnQueen(int);11.private:12.boolPlace(intk);//测试皇后k置于第x[k]列的合法性13.boolQueensLv(void);//随机放置n个皇后拉斯维加斯算法14.intn;//皇后个数15.int*x,*y;//解向量16.};17.18.//测试皇后k置于第x[k]列的合法性19.boolQueen::Place(intk)20.{21.for(intj=1;jk;j++)22.{23.if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))24.{25.returnfalse;26.}27.}28.returntrue;29.}30.31.//随机放置n个皇后的拉斯维加斯算法32.boolQueen::QueensLv(void)33.{34.RandomNumberrnd;//随机数产生器35.intk=1;//下一个皇后的编号36.intcount=1;//在一列中，可以放置皇后的个数37.38.while((k=n)&&(count0))39.{40.count=0;41.for(inti=1;i=n;i++)42.{43.x[k]=i;//位置44.if(Place(k))45.{46.y[count++]=i;47.}48.}49.if(count0)50.{51.x[k++]=y[rnd.Random(count)];//随机位置52.}53.}54.55.return(count0);//count0表示放置成功56.}57.58.//解n后问题的拉斯维加斯算法59.voidnQueen(intn)60.{61.QueenX;62.X.n=n;63.64.int*p=newint[n+1];65.for(inti=0;i=n;i++)66.{67.p[i]=0;68.}69.X.x=p;70.X.y=newint[n+1];71.72.//反复调用随机放置n个皇后的拉斯维加斯算法，直到放置成功73.while(!X.QueensLv());74.75.for(inti=1;i=n;i++)76.{77.coutp[i];78.}79.coutendl;80.delete[]p;81.}82.83.intmain()84.{85.intn=8;86.coutn皇后问题的解为：endl;87.nQueen(n);88.return0;89.}程序运行结果如下：2)与回溯法结合的拉斯维加斯随机算法求解思路如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。算法具体代码如下：1、RandomNumber.h如上2、7d4d1-2.cpp[cpp]viewplaincopy1.//随机化算法拉斯维加斯算法n后问题2.#includestdafx.h3.#includeRandomNumber.h4.#includecmath5.#includeiostream6.usingnamespacestd;7.8.classQueen9.{10.friendboolnQueen(int);11.private:12.boolPlace(intk);//测试皇后k置于第x[k]的合法性13.boolBacktrack(intt);//解n后问题的回溯法14.boolQueensLV(intstopVegas);//随机放置n个皇后拉斯维加斯算法15.intn,*x,*y;16.};17.18.//测试皇后k置于第x[k]列的合法性19.boolQueen::Place(intk)20.{21.for(intj=1;jk;j++)22.{23.if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))24.{25.returnfalse;26.}27.}28.returntrue;29.}30.31.//解n后问题的回溯法32.boolQueen::Backtrack(intt)33.{34.if(tn)35.{36.for(inti=1;i=n;i++)37.{38.y[i]=x[i];//问题的解39.}40.returntrue;41.}42.else43.{44.for(inti=1;i=n;i++)45.{46.x[t]=i;47.if(Place(t)&&Backtrack(t+1))48.{49.returntrue;50.}51.}52.}53.returnfalse;54.}55.56.57.//随机放置n个皇后拉斯维加斯算法58.boolQueen::QueensLV(intstopVegas)59.{60.RandomNumberrnd;//随机数产生器61.intk=1;62.intcount=1;63.64.//1=stopVegas=n65.while((k=stopVegas)&&(count0))66.{67.count=0;68.for(inti=1;i=n;i++)69.{70.x[k]=i;71.if(Place(k))72.{73.y[count++]=i;74.}75.}76.77.if(count0)78.{79.x[k++]=y[rnd.Random(count)];//随机位置80.}81.}82.return(count0);//count0表示放置成功83.}84.85.//与回溯法相结合的解n后问题的拉斯维加斯算法86.boolnQueen(intn)87.{88.QueenX;89.90.//初始化X91.X.n=n;92.93.int*p=newint[n+1];94.int*q=newint[n+1];95.96.for(inti=0;i=n;i++)97.{98.p[i]=0;99.q[i]=0;100.}101.102.X.y=p;103.X.x=q;104.105.intstop=3;106.if(n15)107.{108.stop=n-15;109.}110.111.boolfound=false;112.while(!X.QueensLV(stop));113.114.//算法的回溯搜索部分115.if(X.Backtrack(stop+1))116.{117.for(inti=1;i=n;i++)118.{119.coutp[i];120.}121.found=true;122.coutendl;123.}124.125.delete[]p;126.delete[]q;127.returnfound;128.}129.130.intmain()131.{132.intn=8;133.coutn皇后问题的解为：endl;134.while(!nQueen(n));135.return0;136.}程序运行结果如图：