算法笔记随机化算法拉斯维加斯（LasVegas）算法和n后问题

1、精选优质文档-倾情为你奉上 1、拉斯维加斯(Las Vegas)算法     拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失败的概率任意小。拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。cpp  1. void obstinate(Object x

2、, Object y)  2. / 反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解y  3.     bool success= false;  4.     while (!success) success=lv(x,y);  5.         设p(x)是对输入x调用拉斯维加斯算法获得问题

3、的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有。解此方程得：     2、n后问题     问题描速：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。  &#

4、160;  1)纯拉斯维加斯随机算法求解思路      对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。      具体实现代码如下：     1、RandomNumber.hcpp  1. #include"time.h" &#

5、160;2. /随机数类  3. const unsigned long maxshort = 65536L;  4. const unsigned long multiplier = L;  5. const unsigned long adder = 12345L;  6.   7. class RandomNumber &

6、#160;8.   9.     private:  10.         /当前种子  11.         unsigned long randSeed;  12.     public:  13.   

7、0;     RandomNumber(unsigned long s = 0);/构造函数，默认值0表示由系统自动产生种子  14.         unsigned short Random(unsigned long n);/产生0：n-1之间的随机整数  15.       

8、60; double fRandom(void);/产生0,1)之间的随机实数  16. ;  17.   18. RandomNumber:RandomNumber(unsigned long s)/产生种子  19.   20.     if(s = 0)  21.       22.   &#

9、160;     randSeed = time(0);/用系统时间产生种子  23.       24.     else  25.       26.         randSeed = s;/由用户提供种子 &#

10、160;27.       28.   29.   30. unsigned short RandomNumber:Random(unsigned long n)/产生0：n-1之间的随机整数  31.   32.     randSeed = multiplier * randSeed + adder;/线性同余式&

11、#160; 33.     return (unsigned short)(randSeed>>16)%n);  34.   35.   36. double RandomNumber:fRandom(void)/产生0,1)之间的随机实数  37.   38.     return Random(maxshort)/double(maxshort);&#

12、160; 39.        2、7d4d1.cppcpp  1. /随机化算法 拉斯维加斯算法 n后问题  2. #include "stdafx.h"  3. #include "RandomNumber.h"  4. #include <cmath>  5. #include <iostream> 

13、; 6. using namespace std;  7.   8. class Queen  9.   10.     friend void nQueen(int);  11.     private:  12.         bool Pla

14、ce(int k);      /测试皇后k置于第xk列的合法性  13.         bool QueensLv(void);    /随机放置n个皇后拉斯维加斯算法  14.         int n;     

15、;             /皇后个数  15.         int *x,*y;              /解向量  16. ;  17.   18.

16、/测试皇后k置于第xk列的合法性  19. bool Queen:Place(int k)  20.   21.     for(int j=1; j<k; j+)  22.       23.         if(abs(k-j)=abs(xj-xk)|(xj=xk) 

17、 24.           25.             return false;  26.           27.       28.   

18、0; return true;  29.   30.   31. /随机放置n个皇后的拉斯维加斯算法  32. bool Queen:QueensLv(void)  33.   34.     RandomNumber rnd;       /随机数产生器  35.    

19、60;int k = 1;              /下一个皇后的编号  36.     int count = 1;          /在一列中，可以放置皇后的个数  37.   38.

20、60;   while(k<=n)&&(count>0)  39.       40.         count = 0;  41.         for(int i=1; i<=n; i+)  42.

21、           43.             xk = i;/位置  44.             if(Place(k)  45.     

22、0;         46.                 ycount+ = i;  47.               48.    

23、       49.         if(count>0)  50.           51.             xk+ = yrnd.Random(count); 

24、;     /随机位置  52.           53.       54.   55.     return (count>0);        /count>0 表示放置成功 &#

25、160;56.   57.   58. /解n后问题的拉斯维加斯算法  59. void nQueen(int n)  60.   61.     Queen X;  62.     X.n = n;  63.   64.     int *p =&

26、#160;new intn+1;  65.     for(int i=0; i<=n; i+)  66.       67.         pi = 0;  68.       69.    

27、0;X.x = p;  70.     X.y = new intn+1;  71.   72.     /反复调用随机放置n个皇后的拉斯维加斯算法，直到放置成功  73.     while(!X.QueensLv();  74.   75.     for(int&

28、#160;i=1; i<=n; i+)  76.       77.         cout<<pi<<" "  78.       79.     cout<<endl;  80.   

29、;  delete p;  81.   82.   83. int main()  84.   85.     int n=8;    86.     cout<<n<<"皇后问题的解为："<<endl;    87.  &

30、#160;  nQueen(n);    88.     return 0;    89.        程序运行结果如下：     2)与回溯法结合的拉斯维加斯随机算法求解思路     如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个

31、解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。  算法具体代码如下：    1、RandomNumber.h如上    2、7d4d1-2.cppcpp  1. /随机化算法 拉斯维加斯算法 n后问题  2. #include "stdafx.h"  3. #include "RandomNumber.h"  4. #include &l

32、t;cmath>  5. #include <iostream>  6. using namespace std;  7.   8. class Queen  9.   10.     friend bool nQueen(int);  11.     private:  12.

33、        bool Place(int k);                  /测试皇后k置于第xk的合法性  13.         bool Backtrack(int t); 

34、;             /解n后问题的回溯法  14.         bool QueensLV(int stopVegas);       /随机放置n个皇后拉斯维加斯算法  15.      

35、0;  int n,*x,*y;  16. ;  17.   18. /测试皇后k置于第xk列的合法性  19. bool Queen:Place(int k)  20.   21.     for(int j=1; j<k; j+)  22.       23. 

36、0;       if(abs(k-j)=abs(xj-xk)|(xj=xk)  24.           25.             return false;  26.       

37、0;   27.       28.     return true;  29.   30.   31. /解n后问题的回溯法  32. bool Queen:Backtrack(int t)  33.   34.     if(t>n)  35. &#

38、160;     36.         for(int i=1; i<=n; i+)  37.           38.             yi = xi;/问题的

39、解  39.           40.         return true;  41.       42.     else  43.       44.   &#

40、160;     for(int i=1; i<=n; i+)  45.           46.             xt = i;  47.        

41、;     if(Place(t)&&Backtrack(t+1)  48.               49.                 return true;  50. &

42、#160;             51.           52.       53.     return false;  54.   55.   56.   57. /随机

43、放置n个皇后拉斯维加斯算法  58. bool Queen:QueensLV(int stopVegas)  59.   60.     RandomNumber rnd;       /随机数产生器  61.     int k = 1;  62.    &

44、#160;int count = 1;  63.   64.     /1<=stopVegas<=n  65.     while(k<=stopVegas)&&(count>0)  66.       67.         

45、count = 0;  68.         for(int i=1; i<=n; i+)  69.           70.             xk = i; &

46、#160;71.             if(Place(k)  72.               73.                 ycount+&

47、#160;= i;  74.               75.           76.   77.         if(count>0)  78.     

48、      79.             xk+ = yrnd.Random(count);/随机位置  80.           81.       82.     retu

49、rn (count>0);        /count>0表示放置成功  83.   84.   85. /与回溯法相结合的解n后问题的拉斯维加斯算法  86. bool nQueen(int n)  87.   88.     Queen X;  89.   

50、60;   90.     /初始化X  91.     X.n = n;  92.   93.     int *p = new intn+1;  94.     int *q = new intn+1;  

51、95.   96.     for(int i=0; i<=n; i+)  97.       98.         pi = 0;  99.         qi = 0;  10

52、0.       101.   102.     X.y = p;  103.     X.x = q;  104.   105.     int stop = 3;  106.     if(n>15) &#