




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 教育游戲化與學(xué)習(xí)動(dòng)機(jī)的激發(fā)關(guān)系
- 抖音商戶剪輯師特效使用合理性制度
- 全球鈾礦資源分布與核能產(chǎn)業(yè)國際合作模式研究報(bào)告
- 公交優(yōu)先戰(zhàn)略2025年城市交通擁堵治理的公共交通與共享單車融合報(bào)告
- 哈爾濱石油學(xué)院《病原生物學(xué)與免疫學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 2024年黑龍江省哈爾濱市六十中學(xué)九年級(jí)化學(xué)第一學(xué)期期末教學(xué)質(zhì)量檢測(cè)模擬試題含解析
- 上海立信會(huì)計(jì)金融學(xué)院《大學(xué)語文與寫作》2023-2024學(xué)年第一學(xué)期期末試卷
- 安徽冶金科技職業(yè)學(xué)院《英語教學(xué)法》2023-2024學(xué)年第一學(xué)期期末試卷
- 江蘇省常州市武進(jìn)區(qū)2024年七年級(jí)數(shù)學(xué)第一學(xué)期期末經(jīng)典試題含解析
- 廣西電力職業(yè)技術(shù)學(xué)院《合唱與合唱指揮1》2023-2024學(xué)年第一學(xué)期期末試卷
- 仲景心法傳講系列四
- (完整word版)餐券模板
- 文創(chuàng)園物業(yè)管理方案
- 2023年6月廣東省普通高中學(xué)業(yè)水平考試生物試卷含答案
- 盟史簡介12.10.18課件
- 行車安全風(fēng)險(xiǎn)點(diǎn)告知牌
- 2019-2020鞍山八年第二學(xué)期語文期末考試帶答案
- 心臟粘液瘤超聲診斷
- 大學(xué)生勞動(dòng)教育教程全套PPT完整教學(xué)課件
- 鐵路工程施工監(jiān)理規(guī)劃
- 嬰幼兒語言發(fā)育篩查量表優(yōu)質(zhì)資料
評(píng)論
0/150
提交評(píng)論