計算機算法設計與分析

計算機算法設計與分析第一頁，共三十頁，編輯于2023年，星期五2學習要點理解產(chǎn)生偽隨機數(shù)的算法掌握數(shù)值隨機化算法的設計思想掌握蒙特卡羅算法的設計思想掌握拉斯維加斯算法的設計思想掌握舍伍德算法的設計思想第二頁，共三十頁，編輯于2023年，星期五3隨機數(shù)隨機數(shù)在隨機化算法設計中扮演著十分重要的角色。在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在隨機化算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)。線性同余法是產(chǎn)生偽隨機數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機序列a0,a1,…,an滿足其中b0，c0，dm。d稱為該隨機序列的種子。如何選取該方法中的常數(shù)b、c和m直接關系到所產(chǎn)生的隨機序列的隨機性能。這是隨機性理論研究的內容，已超出本書討論的范圍。從直觀上看，m應取得充分大，因此可取m為機器大數(shù)，另外應取gcd(m,b)=1，因此可取b為一素數(shù)。第三頁，共三十頁，編輯于2023年，星期五4數(shù)值隨機化算法

第四頁，共三十頁，編輯于2023年，星期五常求解數(shù)值問題。往往得到近似解。近似解的精度隨計算時間增加而提高。5第五頁，共三十頁，編輯于2023年，星期五6用隨機投點法計算值

設有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設落入圓內的點數(shù)為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內的概率為。所以當n足夠大時，k與n之比就逼近這一概率。從而doubleDarts(intn){//用隨機投點法計算值

staticRandomNumberdart;intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if((x*x+y*y)<=1)k++;}return4*k/double(n);}第六頁，共三十頁，編輯于2023年，星期五7計算定積分設f(x)是[0，1]上的連續(xù)函數(shù)，且0f(x)1。需要計算的積分為,積分I等于圖中的面積G。在圖所示單位正方形內均勻地作投點試驗，則隨機點落在曲線下面的概率為假設向單位正方形內隨機地投入n個點(xi,yi)。如果有m個點落入G內，則隨機點落入G內的概率第七頁，共三十頁，編輯于2023年，星期五8解非線性方程組求解下面的非線性方程組其中，x1,x2,…,xn是實變量，fi是未知量x1,x2,…,xn的非線性實函數(shù)。要求確定上述方程組在指定求根范圍內的一組解

在指定求根區(qū)域D內，選定一個隨機點x0作為隨機搜索的出發(fā)點。在算法的搜索過程中，假設第j步隨機搜索得到的隨機搜索點為xj。在第j+1步，計算出下一步的隨機搜索增量xj。從當前點xj依xj得到第j+1步的隨機搜索點。當x<時，取為所求非線性方程組的近似解。否則進行下一步新的隨機搜索過程。第八頁，共三十頁，編輯于2023年，星期五9舍伍德算法

第九頁，共三十頁，編輯于2023年，星期五總能求得問題的一個解，且所求得的解總是正確的。在確定性算法中引入隨機性將其改造成一個舍伍德算法，可消除或減少問題好壞實例間的差別。10第十頁，共三十頁，編輯于2023年，星期五11舍伍德(Sherwood)算法設A是一個確定性算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設Xn是算法A的輸入規(guī)模為n的實例的全體，則當問題的輸入規(guī)模為n時，算法A所需的平均時間為這顯然不能排除存在x∈Xn使得的可能性。希望獲得一個隨機化算法B，使得對問題的輸入規(guī)模為n的每一個實例均有這就是舍伍德算法設計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德算法可獲得很好的平均性能。第十一頁，共三十頁，編輯于2023年，星期五12舍伍德(Sherwood)算法復習學過的Sherwood算法：（1）線性時間選擇算法（2）快速排序算法有時也會遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。此時可借助于隨機預處理技術，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德算法的效果。例如，對于確定性選擇算法，可以用下面的洗牌算法shuffle將數(shù)組a中元素隨機排列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。template<classType>voidShuffle(Typea[],intn){//隨機洗牌算法

staticRandomNumberrnd;for(inti=0;i<n;i++){intj=rnd.Random(n-i)+i;Swap(a[i],a[j]);}}第十二頁，共三十頁，編輯于2023年，星期五13搜索有序表用兩個數(shù)組表示所給的含有n個元素的有序集S，即用數(shù)組來模擬有序鏈表。用value[0:n]存儲有序集中的元素，link[0:n]存儲有序集種元素在數(shù)組value中的位置指針。Link[0]指向有序集中第1個元素（即value[link[0]]是集合中最小元素）。Value[0]是一個大數(shù)。一般地，若value[i]是所給有序集S中的第k個元素，則value[link[i]]是S中的第k+1個元素。S中元素有序表現(xiàn)為，對任意1≤i≤n有value[i]≤value[link[i]]。第十三頁，共三十頁，編輯于2023年，星期五14搜索有序表如有序集S={1,2,3,5,8,13,21}的一種表示如下：i01234567Value[i]∞231215218Link[i]42561703采用順序搜索方式對有序鏈表進行搜索，若S含n個元素，在最壞情況下，算法所需時間為O(n)。改進算法基本思想：隨機抽取數(shù)組元素若干次，從較接近搜索元素x的位置開始做順序搜索。若隨機抽取數(shù)組元素k=└√n┘次，則算法需平均計算時間為O（√n）。第十四頁，共三十頁，編輯于2023年，星期五15跳躍表舍伍德型算法的設計思想還可用于設計高效的數(shù)據(jù)結構。如果用有序鏈表來表示一個含有n個元素的有序集S，則在最壞情況下，搜索S中一個元素需要(n)計算時間。提高有序鏈表效率的一個技巧是在有序鏈表的部分結點處增設附加指針以提高其搜索性能。在增設附加指針的有序鏈表中搜索一個元素時，可借助于附加指針跳過鏈表中若干結點，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。應在跳躍表的哪些結點增加附加指針以及在該結點處應增加多少指針完全采用隨機化方法來確定。這使得跳躍表可在O(logn)平均時間內支持關于有序集的搜索、插入和刪除等運算。第十五頁，共三十頁，編輯于2023年，星期五16跳躍表在一般情況下，給定一個含有n個元素的有序鏈表，可以將它改造成一個完全跳躍表，使得每一個k級結點含有k+1個指針，分別跳過2k-1，2k-1-1，…，20-1個中間結點。第i個k級結點安排在跳躍表的位置i2k處，i0。這樣就可以在時間O(logn)內完成集合成員的搜索運算。在一個完全跳躍表中，最高級的結點是logn級結點。完全跳躍表與完全二叉搜索樹的情形非常類似。它雖然可以有效地支持成員搜索運算，但不適應于集合動態(tài)變化的情況。集合元素的插入和刪除運算會破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率。第十六頁，共三十頁，編輯于2023年，星期五17跳躍表為了在動態(tài)變化中維持跳躍表中附加指針的平衡性，必須使跳躍表中k級結點數(shù)維持在總結點數(shù)的一定比例范圍內。注意到在一個完全跳躍表中，50%的指針是0級指針；25%的指針是1級指針；…；(100/2k+1)%的指針是k級指針。因此，在插入一個元素時，以概率1/2引入一個0級結點，以概率1/4引入一個1級結點，…，以概率1/2k+1引入一個k級結點。另一方面，一個i級結點指向下一個同級或更高級的結點，它所跳過的結點數(shù)不再準確地維持在2i-1。經(jīng)過這樣的修改，就可以在插入或刪除一個元素時，通過對跳躍表的局部修改來維持其平衡性。第十七頁，共三十頁，編輯于2023年，星期五18跳躍表在一個完全跳躍表中，具有i級指針的結點中有一半同時具有i+1級指針。為了維持跳躍表的平衡性，可以事先確定一個實數(shù)0<p<1，并要求在跳躍表中維持在具有i級指針的結點中同時具有i+1級指針的結點所占比例約為p。為此目的，在插入一個新結點時，先將其結點級別初始化為0，然后用隨機數(shù)生成器反復地產(chǎn)生一個[0，1]間的隨機實數(shù)q。如果q<p，則使新結點級別增加1，直至qp。由此產(chǎn)生新結點級別的過程可知，所產(chǎn)生的新結點的級別為0的概率為1-p，級別為1的概率為p(1-p)，…，級別為i的概率為pi(1-p)。如此產(chǎn)生的新結點的級別有可能是一個很大的數(shù)，甚至遠遠超過表中元素的個數(shù)。為了避免這種情況，用作為新結點級別的上界。其中n是當前跳躍表中結點個數(shù)。當前跳躍表中任一結點的級別不超過第十八頁，共三十頁，編輯于2023年，星期五19拉斯維加斯(LasVegas)算法

第十九頁，共三十頁，編輯于2023年，星期五算法不會得到不正確的解。一旦用該算法找到一個解，就一定是正確解，但有時用該算法會找不到解。對所求問題的任一實例，用同一拉斯維加斯算法反復對該實例求解足夠多次，可是求解失效的概率任意小。20第二十頁，共三十頁，編輯于2023年，星期五21拉斯維加斯(LasVegas)算法拉斯維加斯算法的一個顯著特征是它所作的隨機性決策有可能導致算法找不到所需的解。voidobstinate(Objectx,Objecty){//反復調用拉斯維加斯算法LV(x,y)，直到找到問題的一個解yboolsuccess=false;while(!success)success=lv(x,y);}設p(x)是對輸入x調用拉斯維加斯算法獲得問題的一個解的概率。一個正確的拉斯維加斯算法應該對所有輸入x均有p(x)>0。設t(x)是算法obstinate找到具體實例x的一個解所需的平均時間,s(x)和e(x)分別是算法對于具體實例x求解成功或求解失敗所需的平均時間，則有：解此方程可得：第二十一頁，共三十頁，編輯于2023年，星期五22n后問題對于n后問題的任何一個解而言，每一個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機放置的。由此容易想到下面的拉斯維加斯算法。在棋盤上相繼的各行中隨機地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后均已相容地放置好，或已沒有下一個皇后的可放置位置時為止。如果將上述隨機放置策略與回溯法相結合，可能會獲得更好的效果。可以先在棋盤的若干行中隨機地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。stopVegaspset01.0000262.00--262.0050.503933.8847.2380.39120.046513.0010.20222.11第二十二頁，共三十頁，編輯于2023年，星期五23整數(shù)因子分解設n>1是一個整數(shù)。關于整數(shù)n的因子分解問題是找出n的如下形式的唯一分解式：其中，p1<p2<…<pk是k個素數(shù)，m1,m2,…,mk是k個正整數(shù)。如果n是一個合數(shù)，則n必有一個非平凡因子x，1<x<n，使得x可以整除n。給定一個合數(shù)n，求n的一個非平凡因子的問題稱為整數(shù)n的因子分割問題。intSplit(intn){intm=floor(sqrt(double(n)));for(inti=2;i<=m;i++)if(n%i==0)returni;return1;}事實上，算法split(n)是對范圍在1～x的所有整數(shù)進行了試除而得到范圍在1～x2的任一整數(shù)的因子分割。第二十三頁，共三十頁，編輯于2023年，星期五24Pollard算法在開始時選取0～n-1范圍內的隨機數(shù)，然后遞歸地由產(chǎn)生無窮序列對于i=2k，以及2k<j2k+1，算法計算出xj-xi與n的最大公因子d=gcd(xj-xi，n)。如果d是n的非平凡因子，則實現(xiàn)對n的一次分割，算法輸出n的因子d。voidPollard(intn){//求整數(shù)n因子分割的拉斯維加斯算法

RandomNumberrnd;inti=1;intx=rnd.Random(n);//隨機整數(shù)

inty=x;intk=2;while(true){i++;x=(x*x-1)%n;//intd=gcd(y-x,n);//求n的非平凡因子

if((d>1)&&(d<n))cout<<d<<endl;if(i==k){y=x;k*=2;}}}對Pollard算法更深入的分析可知，執(zhí)行算法的while循環(huán)約次后，Pollard算法會輸出n的一個因子p。由于n的最小素因子p，故Pollard算法可在O(n1/4)時間內找到n的一個素因子。第二十四頁，共三十頁，編輯于2023年，星期五25蒙特卡羅(MonteCarlo)算法

第二十五頁，共三十頁，編輯于2023年，星期五用于求解問題的準確解。求得正確解的概率依賴于算法所用的時間。算法所用時間越多，得到正確接的概率越高。主要缺點：一般無法有效判定所得的解是否肯定正確。26第二十六頁，共三十頁，編輯于2023年，星期五27蒙特卡羅(MonteCarlo)算法在實際應用中常會遇到一些問題，不論采用確定性算法或隨機化算法都無法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。設p是一個實數(shù)，且1/2<p<1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢。如果對于同一實例，蒙特卡羅算法不會給出2個不同的正確解答，則稱該蒙特卡羅算法是一致的。有些蒙特卡羅算法除了具有描述問題實例的輸入?yún)?shù)外，還具有描述錯誤解可接受概率的參數(shù)。這類算法的計算時間復雜性通常由問題的實例規(guī)模以及錯誤解可接受概率的函數(shù)來描述。第二十七頁，共三十頁，編輯于2023年，星期五28蒙特卡羅(MonteCarlo)算法對于一個一致的p正確蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干次，并選擇出現(xiàn)頻次最高的解即可。如果重復調用一個一致的(1/2+)正確的蒙特卡羅算法2m-1次，得到正確解的概率至少為1-，其中，對于一個解所給問題的蒙特卡羅算法MC(x)，如果存在問題實例的子集X使得：(1)當xX時，MC(x)返回的解是正確的；(2)當xX時，正確解是y0，但MC(x)返回的解未必是y0。稱上述算法MC(x)是偏y0的算法。重復調用一個一致的，p正確偏y0蒙特卡羅算法k次，可得到一個O(1-(1-p)k)正確的蒙特卡羅算法，且所得算法仍是一個一致的偏y0蒙特卡羅算法。第二十八頁，共三十頁，編輯于2023年，星期五29主元素問題設T[1:n]是一個含有n個元素的數(shù)組。當|{i|T[i]=x}|>n/2時，稱元素x是數(shù)組T的主元素。template<classType>boolMajority(Type*T,intn){//判定主元素的蒙特卡羅算法

inti=rnd.Random(n)+1;Typex=T[i];//隨機選擇數(shù)組元素

intk=0;for(intj=1;j<=n;j++)if(T[j]==x)k++;return(k>n/2);//k>n/2時T含有主元素}template<classType>boolMajorityMC(Type*T,intn,doublee){//重復調用算法Majorityintk=ceil(log(1/e)/log(2));for(inti=1;i<=k;i++)if(Majority(T,n))returntrue;returnfalse;}對于任何給定的>0，算法majorityMC重復調用log(1/)

次算法majority。它是一個偏真蒙特卡羅算法，且其錯誤概率小于。算法majorityMC所需的計算時間顯然是O(nlog(1/))。第二十九頁，共三十頁，編輯于2023年，星期五30素數(shù)測試Wilson定理：對于給定的正整數(shù)n，判定n是一個素數(shù)的充要條件是(n