《算法設(shè)計(jì)與分析》第七章隨機(jī)算法及計(jì)算復(fù)雜性課件

第七章隨機(jī)算法及NP完全問題7.1隨機(jī)算法引言7.2隨機(jī)算法的類型7.3隨機(jī)數(shù)發(fā)生器7.4數(shù)值概率算法7.5舍伍德(Sherwood)算法7.6拉斯維加斯（LasVegas）算法7.7蒙特卡羅（MonteCarlo）算法7.8NP完全問題7.1隨機(jī)算法引言確定性的算法：算法的每一個(gè)計(jì)算步驟都是確定的，對(duì)于相同的輸出，每一次執(zhí)行過程都會(huì)產(chǎn)生相同的輸出。隨機(jī)算法：非形式描述隨機(jī)算法為使用隨機(jī)函數(shù)產(chǎn)生器的算法。算法中的一些判定依賴于隨機(jī)函數(shù)產(chǎn)生器的輸出。隨機(jī)算法對(duì)于相同的輸入，在不同的運(yùn)行過程中會(huì)得到不同的輸出。對(duì)于相同的輸入，隨機(jī)算法的執(zhí)行時(shí)間也可能隨不同的運(yùn)行過程而不同。8.1隨機(jī)算法引言隨機(jī)算法的優(yōu)點(diǎn)：1、執(zhí)行時(shí)間和空間，小于同一問題的已知最好的確定性算法；2、實(shí)現(xiàn)比較簡(jiǎn)單，容易理解。很多確定性的算法，其性能很壞?？捎秒S機(jī)選擇的方法來改善算法的性能。某些方面可能不正確，對(duì)特定的輸入，算法的每一次運(yùn)行不一定得到相同結(jié)果。出現(xiàn)這種不正確的可能性很小，以致可以安全地不予理睬。7.2隨機(jī)算法的類型1、數(shù)值概率算法：用于數(shù)值問題的求解。所得到的解幾乎都是近似解，近似解的精度隨著計(jì)算時(shí)間的增加而不斷地提高。2、舍伍德（Sherwood）算法：很多具有很好的平均運(yùn)行時(shí)間的確定性算法，在最壞的情況下性能很壞。引入隨機(jī)性加以改造，可以消除或減少一般情況和最壞情況的差別。7.2隨機(jī)算法的類型3、拉斯維加斯（LasVegas）算法：要么給出問題的正確答案，要么得不到答案。反復(fù)求解多次，可使失效的概率任意小。4、蒙特卡羅（MonteCarlo）算法：總能得到問題的答案，偶然產(chǎn)生不正確的答案。重復(fù)運(yùn)行，每一次都進(jìn)行隨機(jī)選擇，可使不正確答案的概率變得任意小。7.3隨機(jī)數(shù)發(fā)生器產(chǎn)生隨機(jī)數(shù)的公式：

產(chǎn)生0~65535的隨機(jī)數(shù)序列，b、c、d為正整數(shù)，稱為所產(chǎn)生的隨機(jī)序列的種子。常數(shù)b、c，對(duì)所產(chǎn)生的隨機(jī)序列的隨機(jī)性能有很大的關(guān)系，b通常取一素?cái)?shù)。7.4數(shù)值概率算法例：用隨機(jī)投點(diǎn)法計(jì)算值設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機(jī)地投擲n個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為k。由于所投入的點(diǎn)在正方形上均勻分布，因而所投入的點(diǎn)落入圓內(nèi)的概率為。所以當(dāng)n足夠大時(shí)，k與n之比就逼近這一概率。從而7.4數(shù)值概率算法publicdoubledarts(intn){//用隨機(jī)投點(diǎn)法計(jì)算值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;}7.5舍伍德(Sherwood)算法一、確定性算法的平均運(yùn)行時(shí)間TA(x)：確定性算法對(duì)輸入實(shí)例的運(yùn)行時(shí)間。Xn：規(guī)模為的所有輸入實(shí)例全體。算法的平均運(yùn)行時(shí)間：存在實(shí)例，。例：快速排序算法當(dāng)輸入數(shù)據(jù)均勻分布時(shí)，運(yùn)行時(shí)間是。當(dāng)輸入數(shù)據(jù)按遞增或遞減順序排列時(shí)，算法的運(yùn)行時(shí)間變壞7.5舍伍德(Sherwood)算法隨機(jī)快速排序算法算法9.1隨機(jī)選擇樞點(diǎn)的快速排序算法輸入：數(shù)組A,數(shù)組元素的的起始位置low,終止位置high輸出：按非降順序排序的數(shù)組A

1.template<classType>2.voidquicksort_random(TypeA[],intlow,inthigh)3.{4.random_seed(0);/*選擇系統(tǒng)當(dāng)前時(shí)間作為隨機(jī)數(shù)種子*/5.r_quicksort(A,low,high); /*遞歸調(diào)用隨機(jī)快速排序算法*/6.}7.5舍伍德(Sherwood)算法1.voidr_quicksort(TypeA[],intlow,inthigh)2.{3.intk;4.if(low<high){5.k=random(low,high);/*產(chǎn)生low到high之間的隨機(jī)數(shù)k*/6.swap(A[low],A[k]);/*把元素A[k]交換到數(shù)組的第一個(gè)位置*/7.k=split(A,low,high); /*按元素A[low]把數(shù)組劃分為兩個(gè)*/8.r_quicksort(A,low,k-1); /*排序第一個(gè)子數(shù)組*/9.r_quicksort(A,k+1,high); /*排序第二個(gè)子數(shù)組*/10.}11.}算法的期望運(yùn)行時(shí)間是。7.6拉斯維加斯（LasVegas）算法一、一般概念 拉斯維加斯算法有時(shí)運(yùn)行成功，有時(shí)失敗，需要反復(fù)運(yùn)行同一實(shí)例，直到成功為止。 BOOLlas_vegas()：解問題的某個(gè)實(shí)例的代碼段。運(yùn)行成功返回true，否則返回false。 拉斯維加斯算法反復(fù)地運(yùn)行下面的代碼段： while(!las_vegas(P(x))); 直到運(yùn)行成功返回為止。7.6拉斯維加斯（LasVegas）算法例：識(shí)別重復(fù)元素考慮一個(gè)有n個(gè)數(shù)字的數(shù)組a[]，其中有n/2個(gè)不同的元素，其余元素是另一個(gè)元素的拷貝，即數(shù)組中共有（n/2）+1個(gè)不同的元素。問題是要識(shí)別重復(fù)的元素。確定性算法： 至少需要（n/2）+2個(gè)時(shí)間步。7.6拉斯維加斯（LasVegas）算法拉斯維加斯（LasVegas）算法intRepeatedElement(Typea[],intn){while(1){inti=random()%n+1;intj=random()%n+1;if((i!=j)&&(a[i]==a[j]))return(i);}}7.6拉斯維加斯（LasVegas）算法while循環(huán)則任何一次迭代中退出的概率為p=.當(dāng)n≥10時(shí)，p≥1/5,則不退出的概率≤4/5。算法在前calogn(c為固定常數(shù))次迭代內(nèi)不退出的概率<(4/5)calogn=n-calog(4/5),若取c≥1/log(5/4),則其值<n-a,因此，算法在calogn次迭代以內(nèi)終止的概率≥1-n-a。每次迭代花費(fèi)O(1)的時(shí)間，算法的執(zhí)行時(shí)間為O(logn)。7.7蒙特卡羅（MonteCarlo）算法數(shù)組的主元素問題一、問題n個(gè)元素的數(shù)組A，A中元素x，若A中一半以上元素與x相同，稱x是A的主元素。例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法每個(gè)元素和其它元素比較，并計(jì)數(shù)。如果計(jì)數(shù)值大于n/2，該元素就是的主元素。元素比較次數(shù)為。7.7蒙特卡羅（MonteCarlo）算法三、蒙特卡羅算法1、隨機(jī)選擇元素A[i]進(jìn)行測(cè)試，若返回true，A[i]就是主元素；否則不是主元素。7.7蒙特卡羅（MonteCarlo）算法算法9.7求數(shù)組A的主元素輸入：n個(gè)元素的數(shù)組A[]輸出：數(shù)組A的主元素

BOOLmajority(TypeA[],Type&x,intn){inti,j,k; random_seed(0);i=random(0,n-1);k=0; for(j=0;j<n;j++) if(A[i]==A[j])k++; if(k>n/2){x=A[i];returnTRUE;}elsereturnFALSE;}7.7蒙特卡羅（MonteCarlo）算法BOOLmajority_monte(TypeA[],Type&x,intn,doublee){intt,s,i,j,k;BOOLflag=FALSE;random_seed(0);s=log(1/e);for(t=1;t<=s;t++){i=random(0,n-1);k=0;for(j=0;j<n;j++)if(A[i]==A[j])k++;if(k>n/2){x=A[i];flag=TRUE;break;}}returnflag;}算法的錯(cuò)誤概率小于所給參數(shù)e。算法的運(yùn)行時(shí)間為O(nlog(1/e))。7.7蒙特卡羅（MonteCarlo）算法素?cái)?shù)測(cè)試一、一般方法被測(cè)試的數(shù)除以2到的數(shù)，余數(shù)為0，是合數(shù)，否則是素?cái)?shù)。二、蒙特卡羅算法7.8NP難與NP完全問題

P類和NP類問題定義12.1是問題的一個(gè)算法。如果在處理問題的實(shí)例時(shí)，在算法的整個(gè)執(zhí)行過程中，每一步只有一個(gè)確定的選擇，就說算法是確定性的算法。定義12.2如果對(duì)某個(gè)判定問題，存在著一個(gè)非負(fù)整數(shù)k，對(duì)輸入規(guī)模為n的實(shí)例，能夠以O(shè)(nk)的時(shí)間運(yùn)行一個(gè)確定性的算法，得到y(tǒng)es或no的答案，則該判定問題π是一個(gè)p類判定問題。7.8NP難與NP完全問題

P類和NP類問題定義12.5如果對(duì)某個(gè)判定問題，存在著一個(gè)非負(fù)整數(shù)k，對(duì)輸入規(guī)模為n的實(shí)例，能夠以O(shè)(nk)的時(shí)間運(yùn)行一個(gè)非確定性的算法，得到y(tǒng)es或no的答案，則該判定問題π是一個(gè)NP類判定問題。特性： 存在確定性的算法，能夠以多項(xiàng)式時(shí)間，來檢查和驗(yàn)證在推測(cè)階段產(chǎn)生的答案。7.8NP難與NP完全問題

NP難問題NP難定義12.6令π是一個(gè)判定問題，如果對(duì)NP中的每一個(gè)問題π‘∈

NP，有，就說判定問題π是一個(gè)NP難題。7.8NP難與NP完全問題

NP完全問題NP完全問題定義12.7令π是一個(gè)判定問題，如果：(1)π∈

NP，并且：(2)對(duì)NP中的所有問題π‘∈

NP，都有； 則稱判定問題π是NP完全的。7.8NP難與NP完全問題

NP難題和NP完全問題的差別π是NP完全問題，π‘是NP難題，則π必定在NP類中，而π‘不一定在NP類中。7.8NP難與NP完全問題

1、歸約的傳遞性定理12.3令、和是三個(gè)判定問題，滿足，及，則有。7.8NP難與NP完全問題

NP完全問題的特性定理12.4令和是NP中的兩個(gè)問題，使得。如果是NP完全的，則也是NP完全的。7.8NP難與NP完全問題

NP完全問題的證明：證明下面兩件事情：(1)，并且：(2)存在一個(gè)NP完全問題，使得；7.8NP難與NP完全問題

定理12.5（Cook定理）可滿足性問題SATISFIABILITY是NP完全的。Cook定理的意義：Cook定理給出了第一個(gè)NP完全問題，使得對(duì)任何問題，只要能夠證明，并且SATISFIABILITY