算法筆記隨機(jī)化算法拉斯維加斯（LasVegas）算法和n后問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 1、拉斯維加斯(Las Vegas)算法     拉斯維加斯算法不會(huì)得到不正確的解。一旦用拉斯維加斯算法找到一個(gè)解，這個(gè)解就一定是正確解。但有時(shí)用拉斯維加斯算法找不到解。與蒙特卡羅算法類似，拉斯維加斯算法找到正確解的概率隨著它所用的計(jì)算時(shí)間的增加而提高。對(duì)于所求解問題的任一實(shí)例，用同一拉斯維加斯算法反復(fù)對(duì)該實(shí)例求解足夠多次，可使求解失敗的概率任意小。拉斯維加斯算法的一個(gè)顯著特征是它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。cpp  1. void obstinate(Object x

2、, Object y)  2. / 反復(fù)調(diào)用拉斯維加斯算法LV(x,y)，直到找到問題的一個(gè)解y  3.     bool success= false;  4.     while (!success) success=lv(x,y);  5.         設(shè)p(x)是對(duì)輸入x調(diào)用拉斯維加斯算法獲得問題

3、的一個(gè)解的概率。一個(gè)正確的拉斯維加斯算法應(yīng)該對(duì)所有輸入x均有p(x)>0。設(shè)t(x)是算法obstinate找到具體實(shí)例x的一個(gè)解所需的平均時(shí)間 ,s(x)和e(x)分別是算法對(duì)于具體實(shí)例x求解成功或求解失敗所需的平均時(shí)間，則有。解此方程得：     2、n后問題     問題描速：在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價(jià)于在n×n格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。  &#

4、160;  1)純拉斯維加斯隨機(jī)算法求解思路      對(duì)于n后問題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置的。在棋盤上相繼的各行中隨機(jī)地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個(gè)皇后均已相容地放置好，或已沒有下一個(gè)皇后的可放置位置時(shí)為止。      具體實(shí)現(xiàn)代碼如下：     1、RandomNumber.hcpp  1. #include"time.h" &#

5、160;2. /隨機(jī)數(shù)類  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.         /當(dāng)前種子  11.         unsigned long randSeed;  12.     public:  13.   

7、0;     RandomNumber(unsigned long s = 0);/構(gòu)造函數(shù)，默認(rèn)值0表示由系統(tǒng)自動(dòng)產(chǎn)生種子  14.         unsigned short Random(unsigned long n);/產(chǎn)生0：n-1之間的隨機(jī)整數(shù)  15.       

8、60; double fRandom(void);/產(chǎn)生0,1)之間的隨機(jī)實(shí)數(shù)  16. ;  17.   18. RandomNumber:RandomNumber(unsigned long s)/產(chǎn)生種子  19.   20.     if(s = 0)  21.       22.   &#

9、160;     randSeed = time(0);/用系統(tǒng)時(shí)間產(chǎn)生種子  23.       24.     else  25.       26.         randSeed = s;/由用戶提供種子 &#

10、160;27.       28.   29.   30. unsigned short RandomNumber:Random(unsigned long n)/產(chǎn)生0：n-1之間的隨機(jī)整數(shù)  31.   32.     randSeed = multiplier * randSeed + adder;/線性同余式&

11、#160; 33.     return (unsigned short)(randSeed>>16)%n);  34.   35.   36. double RandomNumber:fRandom(void)/產(chǎn)生0,1)之間的隨機(jī)實(shí)數(shù)  37.   38.     return Random(maxshort)/double(maxshort);&#

12、160; 39.        2、7d4d1.cppcpp  1. /隨機(jī)化算法 拉斯維加斯算法 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);      /測(cè)試皇后k置于第xk列的合法性  13.         bool QueensLv(void);    /隨機(jī)放置n個(gè)皇后拉斯維加斯算法  14.         int n;     

15、;             /皇后個(gè)數(shù)  15.         int *x,*y;              /解向量  16. ;  17.   18.

16、/測(cè)試皇后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. /隨機(jī)放置n個(gè)皇后的拉斯維加斯算法  32. bool Queen:QueensLv(void)  33.   34.     RandomNumber rnd;       /隨機(jī)數(shù)產(chǎn)生器  35.    

19、60;int k = 1;              /下一個(gè)皇后的編號(hào)  36.     int count = 1;          /在一列中，可以放置皇后的個(gè)數(shù)  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、;     /隨機(jī)位置  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.     /反復(fù)調(diào)用隨機(jī)放置n個(gè)皇后的拉斯維加斯算法，直到放置成功  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.        程序運(yùn)行結(jié)果如下：     2)與回溯法結(jié)合的拉斯維加斯隨機(jī)算法求解思路     如果將上述隨機(jī)放置策略與回溯法相結(jié)合，可能會(huì)獲得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個(gè)

31、解或宣告失敗。隨機(jī)放置的皇后越多，后繼回溯搜索所需的時(shí)間就越少，但失敗的概率也就越大。  算法具體代碼如下：    1、RandomNumber.h如上    2、7d4d1-2.cppcpp  1. /隨機(jī)化算法 拉斯維加斯算法 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);                  /測(cè)試皇后k置于第xk的合法性  13.         bool Backtrack(int t); 

34、;             /解n后問題的回溯法  14.         bool QueensLV(int stopVegas);       /隨機(jī)放置n個(gè)皇后拉斯維加斯算法  15.      

35、0;  int n,*x,*y;  16. ;  17.   18. /測(cè)試皇后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. /隨機(jī)

43、放置n個(gè)皇后拉斯維加斯算法  58. bool Queen:QueensLV(int stopVegas)  59.   60.     RandomNumber rnd;       /隨機(jī)數(shù)產(chǎn)生器  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);/隨機(jī)位置  80.           81.       82.     retu

49、rn (count>0);        /count>0表示放置成功  83.   84.   85. /與回溯法相結(jié)合的解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) &#