算法設(shè)計(jì)與分析

1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析授課教師：王秋芬授課教師：王秋芬辦公地點(diǎn)：辦公地點(diǎn)：7307Email: w_第六章第六章 隨機(jī)化算法隨機(jī)化算法教學(xué)目標(biāo)教學(xué)目標(biāo)理解產(chǎn)生偽隨機(jī)數(shù)的線性同余法掌握數(shù)值隨機(jī)化算法的特點(diǎn)及應(yīng)用 掌握蒙特卡羅算法的特點(diǎn)及應(yīng)用掌握拉斯維加斯算法的特點(diǎn)及應(yīng)用掌握舍伍德算法的特點(diǎn)及應(yīng)用6.1概述概述6.1.1隨機(jī)化算法的類型及特點(diǎn)隨機(jī)化算法的類型及特點(diǎn)類型類型數(shù)值隨機(jī)化算法數(shù)值隨機(jī)化算法 蒙特卡羅算法蒙特卡羅算法 拉斯維加斯算法拉斯維加斯算法 舍伍德算法舍伍德算法 特點(diǎn)特點(diǎn)數(shù)值隨機(jī)化算法常用于數(shù)值問題的求解，所得到的解往數(shù)值隨機(jī)化算法常用于數(shù)值問題的求解，所得到的解往往都是近似解

2、，而且近似解的精度隨計(jì)算時(shí)間的增加不往都是近似解，而且近似解的精度隨計(jì)算時(shí)間的增加不斷提高。斷提高。蒙特卡羅算法每次均能求得問題的一個(gè)準(zhǔn)確解，但這蒙特卡羅算法每次均能求得問題的一個(gè)準(zhǔn)確解，但這個(gè)解未必是正確的。求得正確解的概率依賴于算法執(zhí)個(gè)解未必是正確的。求得正確解的概率依賴于算法執(zhí)行時(shí)所用的時(shí)間，所用的時(shí)間越多得到正確解的概率行時(shí)所用的時(shí)間，所用的時(shí)間越多得到正確解的概率就越高。一般情況下，蒙特卡羅算法不能有效地確定就越高。一般情況下，蒙特卡羅算法不能有效地確定求得的解是否正確。求得的解是否正確。 拉斯維加斯算法不會(huì)得到不正確的解，一旦找到一個(gè)拉斯維加斯算法不會(huì)得到不正確的解，一旦找到一個(gè)解

3、，那么這個(gè)解肯定是正確的。但是有時(shí)候拉斯維加解，那么這個(gè)解肯定是正確的。但是有時(shí)候拉斯維加斯算法可能找不到解。拉斯維加斯算法得到正確解的斯算法可能找不到解。拉斯維加斯算法得到正確解的概率隨著算法執(zhí)行時(shí)間的增加而提高。概率隨著算法執(zhí)行時(shí)間的增加而提高。舍伍德算法不會(huì)改變對應(yīng)確定性算法的求解結(jié)果，每舍伍德算法不會(huì)改變對應(yīng)確定性算法的求解結(jié)果，每次運(yùn)行都能夠得到問題的解，并且所得到的解是正確次運(yùn)行都能夠得到問題的解，并且所得到的解是正確的的 6.1.2 隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器 產(chǎn)生隨機(jī)數(shù)的方法產(chǎn)生隨機(jī)數(shù)的方法 偽隨機(jī)數(shù)發(fā)生器偽隨機(jī)數(shù)發(fā)生器通過一個(gè)固定的、可以重復(fù)的計(jì)算方法產(chǎn)

4、生隨機(jī)通過一個(gè)固定的、可以重復(fù)的計(jì)算方法產(chǎn)生隨機(jī)數(shù)的發(fā)生器數(shù)的發(fā)生器線性同余法線性同余法 2 , 1mod)(10nmcbaadann，d為種子；為種子；b為系數(shù)，滿足為系數(shù)，滿足b0；c為增量，滿為增量，滿足足c0；m為模數(shù)，滿足為模數(shù)，滿足m0。b、c和和m越大越大且且b與與m互質(zhì)可使隨機(jī)函數(shù)的隨機(jī)性能更好互質(zhì)可使隨機(jī)函數(shù)的隨機(jī)性能更好思考：如何產(chǎn)生思考：如何產(chǎn)生0-1之間的隨機(jī)數(shù)？之間的隨機(jī)數(shù)？ /建立隨機(jī)數(shù)類建立隨機(jī)數(shù)類RandomNumber #define m 65536L#define b 1194211693L#define c 12345Lclass RandomNumber

5、 private: unsigned long d; /d為當(dāng)前種子為當(dāng)前種子 public: RandomNumber(unsigned long s=0); /缺省值缺省值0表示由系統(tǒng)自動(dòng)產(chǎn)生表示由系統(tǒng)自動(dòng)產(chǎn)生種子種子 unsigned short random(unsigned long n); /產(chǎn)生產(chǎn)生0：n-1之間的隨機(jī)之間的隨機(jī)整數(shù)整數(shù) double fRandom(); /產(chǎn)生產(chǎn)生0,1)之間的隨機(jī)實(shí)數(shù)之間的隨機(jī)實(shí)數(shù) ; RandomNumber:RandomNumber(unsigned long s) if(s=0) d=time(0); /用系統(tǒng)時(shí)間產(chǎn)生種子用系統(tǒng)時(shí)間產(chǎn)生

6、種子 else d=s; /由用戶提供種子由用戶提供種子 unsigned short RandomNumber:random(unsigned long n) d=b*d+c; /用線性同余計(jì)算新的種子用線性同余計(jì)算新的種子 return (unsigned short)(d16)%n); /把把d的高的高16位映射到位映射到0(n-1)范圍內(nèi)范圍內(nèi) double RandomNumber:fRandom() /產(chǎn)生產(chǎn)生0,1)之間的隨機(jī)實(shí)數(shù)之間的隨機(jī)實(shí)數(shù) return random(m)/double(m); 6.2數(shù)值隨機(jī)化算法數(shù)值隨機(jī)化算法6.2.1計(jì)算計(jì)算的值的值將將n個(gè)點(diǎn)隨機(jī)投向一

7、個(gè)正方形，設(shè)落入此正方形個(gè)點(diǎn)隨機(jī)投向一個(gè)正方形，設(shè)落入此正方形內(nèi)切圓（半徑為內(nèi)切圓（半徑為r）中的點(diǎn)的數(shù)目為）中的點(diǎn)的數(shù)目為k，如圖，如圖6-1a）所示。所示。a)b)0 xy11假設(shè)所投入的點(diǎn)落入正方形的任一點(diǎn)的概率相等，假設(shè)所投入的點(diǎn)落入正方形的任一點(diǎn)的概率相等，則所投入的點(diǎn)落入圓內(nèi)的概為則所投入的點(diǎn)落入圓內(nèi)的概為 。當(dāng)當(dāng)n足夠大時(shí)，足夠大時(shí)， k與與n之比就逼近這一概率，從而之比就逼近這一概率，從而 在具體實(shí)現(xiàn)時(shí)只以第一象限為樣本且在具體實(shí)現(xiàn)時(shí)只以第一象限為樣本且r取值為取值為1，建，建立直角坐標(biāo)系，如圖立直角坐標(biāo)系，如圖6-1b）所示）所示 4422rrnk4double Darts(

8、int n) static RandomNumber darts; int k=0,i;double x,y;for( i=1;i=n;i+)x=darts.fRandom(); /產(chǎn)生一個(gè)產(chǎn)生一個(gè)0,1)之間的實(shí)數(shù)，賦給之間的實(shí)數(shù)，賦給xy=darts.fRandom(); /產(chǎn)生一個(gè)產(chǎn)生一個(gè)0,1)之間的實(shí)數(shù)，賦給之間的實(shí)數(shù)，賦給y if(x*x+y*y)=1) k+;return 4*k/double(n);6.2.2計(jì)算定積分設(shè)f(x)是0,1上的連續(xù)函數(shù)且0f(x)1，需要計(jì)算積分值 。假設(shè)向單位正方形內(nèi)隨機(jī)投入n個(gè)點(diǎn)，如果有m個(gè)點(diǎn)落入G內(nèi)，則I近似等于隨機(jī)點(diǎn)落入G內(nèi)的概率，即Im/

9、n 10)(dxxfIy=f(x)01x1yG 圖6-2 隨機(jī)投點(diǎn)實(shí)驗(yàn)估算I值示意圖double Darts(int n)static RandomNumber dart; int k=0,i;double x,y;for( i=1 ;i=n;i+) x=dart.fRandom ( ); /產(chǎn)生一個(gè)產(chǎn)生一個(gè)0,1)之間的實(shí)數(shù)，賦給之間的實(shí)數(shù)，賦給xy=dart.fRandom ( ); /產(chǎn)生一個(gè)產(chǎn)生一個(gè)0,1)之間的實(shí)數(shù)，賦給之間的實(shí)數(shù)，賦給y if(y=f(x) k+;return k/double(n);6.3蒙特卡羅算法設(shè)設(shè)p是一個(gè)實(shí)數(shù)，且是一個(gè)實(shí)數(shù)，且0.5pn/2時(shí)，稱元時(shí)，稱元

10、素素x是數(shù)組是數(shù)組T的主元素的主元素算法描述算法描述Template bool majority(Type T, int n) / 判定主元素的蒙特卡羅算法判定主元素的蒙特卡羅算法 RandomNumber rnd;int i=rnd.random(n)+1; /產(chǎn)生產(chǎn)生1n之間的隨機(jī)下標(biāo)之間的隨機(jī)下標(biāo)Type x=Ti; / 隨機(jī)選擇數(shù)組元素隨機(jī)選擇數(shù)組元素int k=0;for (int j=1;jn/2); /當(dāng)當(dāng) kn/2 時(shí)，時(shí)，T含有主元素含有主元素 6.3.1主元素問題主元素問題bool majorityMC(Type T, int n, double ) / 重復(fù)次調(diào)用多次算法

11、重復(fù)次調(diào)用多次算法majorityint k= (int) ceil(log()/log(1-p);for (int i=1;i=k;i+) if (majority(T,n) return true;return false;6.3.2素?cái)?shù)測試素?cái)?shù)測試試除法試除法 用用2,3, 去除去除n，判斷是否能被整除，如果能，判斷是否能被整除，如果能，則為合數(shù)，否則為素?cái)?shù)。則為合數(shù)，否則為素?cái)?shù)。算法描述算法描述bool Prime(unsigned int n)int m=floor(sqrt(double(n);for(int i=2;i=m;i+) if(n%i=0) return false;r

12、eturn true; nWilson定理定理對于給定的正整數(shù)n，判定n是一個(gè)素?cái)?shù)的充要條件是(n-1)! -1(mod n)。費(fèi)爾馬小定理費(fèi)爾馬小定理如果p是一個(gè)素?cái)?shù)且a是整數(shù)，則 apa(mod p)。特別地，若a不能被p整除，則ap-11(mod p)。 二次探測定理二次探測定理如果p是一個(gè)素?cái)?shù)，x是整數(shù)且0 x0。在更強(qiáng)意義下，要求存在一個(gè)常數(shù)在更強(qiáng)意義下，要求存在一個(gè)常數(shù)0，使得對，使得對問題的每一個(gè)實(shí)例問題的每一個(gè)實(shí)例x均有均有p(x)。思考：給定一個(gè)拉斯維加斯算法，設(shè)思考：給定一個(gè)拉斯維加斯算法，設(shè)p(x)是對輸是對輸入入x調(diào)用它獲得問題的一個(gè)解的概率，調(diào)用它獲得問題的一個(gè)解的概

13、率，s(x)和和e(x)分別是算法對于具體實(shí)例分別是算法對于具體實(shí)例x求解成功或失敗所需求解成功或失敗所需的平均時(shí)間的平均時(shí)間 ，算法找到具體實(shí)例，算法找到具體實(shí)例x的一個(gè)解所需的一個(gè)解所需的平均時(shí)間是多少？的平均時(shí)間是多少？ )()()(1)()()()(1 ()()(xexpxpxsxnpxexpnxsxnp6.4.1整數(shù)因子分解整數(shù)因子分解整數(shù)因子分解整數(shù)因子分解 將大于將大于1的整數(shù)的整數(shù)n分解為分解為 的形式的形式p1,p2,pk是是k個(gè)素?cái)?shù)且個(gè)素?cái)?shù)且p1p2pk，m1,m2,mk是是k個(gè)正整數(shù)個(gè)正整數(shù) 如果如果n是一個(gè)合數(shù)，則是一個(gè)合數(shù)，則n必有一個(gè)非平凡因子必有一個(gè)非平凡因子x，

14、1xn，使得，使得x可以整除可以整除n。給定一個(gè)合數(shù)給定一個(gè)合數(shù)n，求，求n的一個(gè)非平凡因子的問題稱的一個(gè)非平凡因子的問題稱為整數(shù)為整數(shù)n的因子分割問題。的因子分割問題。結(jié)合上節(jié)的素?cái)?shù)測試問題，整數(shù)因子分解問題實(shí)結(jié)合上節(jié)的素?cái)?shù)測試問題，整數(shù)因子分解問題實(shí)質(zhì)上可以轉(zhuǎn)化為整數(shù)的因子分割問題質(zhì)上可以轉(zhuǎn)化為整數(shù)的因子分割問題 kmkmmpppn2121試除法進(jìn)行因子分割試除法進(jìn)行因子分割int Split(int n) int k=floor(sqrt(double(n); for (int i=2; i1) & (dn) return d; if (i=k) y=x; k*=2; /end

15、while() 6.4.2 n皇后問題皇后問題問題描述問題描述n皇后問題要求將皇后問題要求將n個(gè)皇后放在個(gè)皇后放在nn棋盤的不同棋盤的不同行、不同列、不同斜線的位置，找出相應(yīng)的放置行、不同列、不同斜線的位置，找出相應(yīng)的放置方案方案 隨機(jī)化措施隨機(jī)化措施對某行放置皇后的有效位置進(jìn)行隨機(jī)對某行放置皇后的有效位置進(jìn)行隨機(jī)對某行所有列位置進(jìn)行隨機(jī)對某行所有列位置進(jìn)行隨機(jī)關(guān)鍵代碼分析關(guān)鍵代碼分析bool Queen:QueensLV( ) RandomNumber rnd; /隨機(jī)數(shù)產(chǎn)生器隨機(jī)數(shù)產(chǎn)生器int k=1; /下一個(gè)放置的皇后編號下一個(gè)放置的皇后編號int count=1;/記錄當(dāng)前要放置的第

16、記錄當(dāng)前要放置的第k個(gè)皇后在第個(gè)皇后在第k行的有效位置數(shù)行的有效位置數(shù)while(k0) count=0; for(int i=1;i0) xk+=yrnd.Random(count); return (count0); /count0表示放置成功表示放置成功bool Queen:QueensLV1(void) /棋盤上隨機(jī)放置棋盤上隨機(jī)放置n個(gè)皇后拉斯維加斯算法個(gè)皇后拉斯維加斯算法RandomNumber rnd; /隨機(jī)數(shù)產(chǎn)生器隨機(jī)數(shù)產(chǎn)生器int k=1; /下一個(gè)放置的皇后編號下一個(gè)放置的皇后編號int count=maxcout;/嘗試產(chǎn)生隨機(jī)位置的最大次數(shù)，用戶根據(jù)需要設(shè)嘗試產(chǎn)生隨機(jī)

17、位置的最大次數(shù)，用戶根據(jù)需要設(shè)置置while(k=n) int i=0; for(i=1;i=count;i+) xk=rnd.Random(n)+1; if(Place(k)break; /第第k個(gè)皇后在第個(gè)皇后在第k行的有效位置存于行的有效位置存于y數(shù)組數(shù)組 if(in); /kn表示放置成功表示放置成功6.5舍伍德算法舍伍德算法隨機(jī)快速排序隨機(jī)快速排序在在3.5節(jié)確定性算法的基礎(chǔ)上，引入隨機(jī)性操作。節(jié)確定性算法的基礎(chǔ)上，引入隨機(jī)性操作。隨機(jī)操作隨機(jī)操作隨機(jī)選擇基準(zhǔn)元素隨機(jī)選擇基準(zhǔn)元素關(guān)鍵代碼分析關(guān)鍵代碼分析int RandPartition(int a,int low,int high)

18、 /隨機(jī)劃分隨機(jī)劃分 RandomNumber random; int i=random(high-low+1)+low; swap(alow,ai); int j=Partition(a,low,high); return j;void rqs(int a,int left,int right)/隨機(jī)快速排序 if(leftright) int p=RandPartition(a,left,right);rqs(a,left,p-1); rqs(a,p+1,right); 6.5.2線性時(shí)間選擇線性時(shí)間選擇確定性算法中，首先分組，然后取每一組的確定性算法中，首先分組，然后取每一組的中位數(shù)，再取每組中位數(shù)的中位數(shù)，最后以中位數(shù)，再取每組中位數(shù)的中位數(shù)，最后以該中位數(shù)為基準(zhǔn)元素對該中位數(shù)為基準(zhǔn)元素對n個(gè)元素進(jìn)行劃分個(gè)元素進(jìn)行劃分 引入隨機(jī)性成分引入隨機(jī)性成分隨機(jī)選擇一個(gè)元素作為基準(zhǔn)元素隨機(jī)選擇一個(gè)元素作為基準(zhǔn)元素關(guān)鍵代碼分析關(guān)鍵代碼分析templateType select(Type a, int left, int right, int k) RandomNumber rnd; if(left=right) return aleft; int i=left, j=rnd.Random(right-left+1)+left； swap(ai, aj); j=Partitio