第七章隨機(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完全問題第七章隨機(jī)算法及NP完全問題7.1隨機(jī)算法引言17.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)行過程而不同。7.1隨機(jī)算法引言確定性的算法：28.1隨機(jī)算法引言隨機(jī)算法的優(yōu)點(diǎn)：1、執(zhí)行時(shí)間和空間，小于同一問題的已知最好的確定性算法；2、實(shí)現(xiàn)比較簡單，容易理解。很多確定性的算法，其性能很壞?？捎秒S機(jī)選擇的方法來改善算法的性能。某些方面可能不正確，對(duì)特定的輸入，算法的每一次運(yùn)行不一定得到相同結(jié)果。出現(xiàn)這種不正確的可能性很小，以致可以安全地不予理睬。8.1隨機(jī)算法引言隨機(jī)算法的優(yōu)點(diǎn)：37.2隨機(jī)算法的類型數(shù)值概率算法拉斯維加斯（LasVegas）算法蒙特卡羅（MonteCarlo）算法舍伍德（Sherwood）算法。7.2隨機(jī)算法的類型數(shù)值概率算法47.2隨機(jī)算法的類型1、數(shù)值概率算法：用于數(shù)值問題的求解。所得到的解幾乎都是近似解，近似解的精度隨著計(jì)算時(shí)間的增加而不斷地提高。2、舍伍德（Sherwood）算法：很多具有很好的平均運(yùn)行時(shí)間的確定性算法，在最壞的情況下性能很壞。引入隨機(jī)性加以改造，可以消除或減少一般情況和最壞情況的差別。7.2隨機(jī)算法的類型1、數(shù)值概率算法：用于數(shù)值問題的求解。57.2隨機(jī)算法的類型3、拉斯維加斯（LasVegas）算法：要么給出問題的正確答案，要么得不到答案。反復(fù)求解多次，可使失效的概率任意小。4、蒙特卡羅（MonteCarlo）算法：總能得到問題的答案，偶然產(chǎn)生不正確的答案。重復(fù)運(yùn)行，每一次都進(jìn)行隨機(jī)選擇，可使不正確答案的概率變得任意小。7.2隨機(jī)算法的類型3、拉斯維加斯（LasVegas）算67.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.3隨機(jī)數(shù)發(fā)生器產(chǎn)生隨機(jī)數(shù)的公式：77.3隨機(jī)數(shù)發(fā)生器#define MULTIPLIER 0x015A4E35L;#define INCREMENT 1;staticunsignedlong seed;voidrandom_seed(unsignedlongd){if(d==0)seed=time(0);elseseed=d;}unsignedintrandom(unsignedlonglow,unsignedlonghigh){seed=MULTIPLIER*seed+INCREMENT;return((seed>>16)%(high–low)+low);}7.3隨機(jī)數(shù)發(fā)生器#define MULTIPLIER 087.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ù)值概率算法例：用隨機(jī)投點(diǎn)法計(jì)算值97.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.4數(shù)值概率算法publicdoubledarts(107.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)算法一、確定性算法的平均運(yùn)117.5舍伍德(Sherwood)算法二、舍伍德算法的基本思想消除不同輸入實(shí)例對(duì)算法性能的影響，使隨機(jī)算法對(duì)規(guī)模為的每一個(gè)實(shí)例，都有：三、期望運(yùn)行時(shí)間：

當(dāng)s(n)與相比很小可以忽略時(shí)，舍伍德算法有很好的性能。對(duì)所有輸入實(shí)例而言，運(yùn)行時(shí)間相對(duì)均勻。時(shí)間復(fù)雜性與確定性算法的時(shí)間復(fù)雜性相當(dāng).7.5舍伍德(Sherwood)算法二、舍伍德算法的基本思127.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)算法隨機(jī)快速排序算法137.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.5舍伍德(Sherwood)算法1.voidr_q147.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）算法一、一般概念157.6拉斯維加斯（LasVegas）算法p(x)：對(duì)輸入實(shí)例成功地運(yùn)行l(wèi)as_vegas的概率若存在常數(shù)δ>0，使得對(duì)的所有實(shí)例p，都有p(x)>=δ，則失敗的概率小于1-δ。連續(xù)運(yùn)行k次，失敗的概率降低為(1-δ)k。k充分大，(1-δ)k趨于0。7.6拉斯維加斯（LasVegas）算法p(x)：對(duì)輸入167.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）算法例：識(shí)別重復(fù)元素177.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）算法拉斯維加斯（La187.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.6拉斯維加斯（LasVegas）算法while循環(huán)則197.7蒙特卡羅（MonteCarlo）算法蒙特卡羅算法則在一般情況下可以保證對(duì)問題的所有實(shí)例都以高概率給出正確解，但是通常無法判定一個(gè)具體解是否正確。設(shè)p是一個(gè)實(shí)數(shù)，且1/2<p<1。如果一個(gè)蒙特卡羅算法對(duì)于問題的任一實(shí)例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢(shì)。如果對(duì)于同一實(shí)例，蒙特卡羅算法不會(huì)給出2個(gè)不同的正確解答，則稱該蒙特卡羅算法是一致的。7.7蒙特卡羅（MonteCarlo）算法蒙特卡羅算法207.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）算法數(shù)組的主元素問217.7蒙特卡羅（MonteCarlo）算法三、蒙特卡羅算法1、隨機(jī)選擇元素A[i]進(jìn)行測(cè)試，若返回true，A[i]就是主元素；否則不是主元素。7.7蒙特卡羅（MonteCarlo）算法三、蒙特卡羅算227.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）算法算法9.7237.7蒙特卡羅（MonteCarlo）算法2、如果存在主元素，以大于1/2的概率返回true，小于1/2的概率返回false。連續(xù)運(yùn)行k次，返回的概率減少為2-k，算法錯(cuò)誤的概率為2-k。希望錯(cuò)誤概率小于ε，則令：2-k=ε

k=log(1/ε)算法修改為：7.7蒙特卡羅（MonteCarlo）算法2、如果存在主247.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）算法BOOLma257.7蒙特卡羅（MonteCarlo）算法素?cái)?shù)測(cè)試一、一般方法被測(cè)試的數(shù)除以2到的數(shù)，余數(shù)為0，是合數(shù)，否則是素?cái)?shù)。二、蒙特卡羅算法7.7蒙特卡羅（MonteCarlo）算法素?cái)?shù)測(cè)試26素?cái)?shù)測(cè)試Wilson定理：對(duì)于給定的正整數(shù)n，判定n是一個(gè)素?cái)?shù)的充要條件是(n-1)!-1(modn)。費(fèi)爾馬小定理：如果p是一個(gè)素?cái)?shù)，且0<a<p，則ap-1(modp)。二次探測(cè)定理：如果p是一個(gè)素?cái)?shù)，且0<x<p，則方程x21(modp)的解為x=1，p-1。intpower(inta,intp,intn){//計(jì)算apmodn，并實(shí)施對(duì)n的二次探測(cè)intx,result;if(p==0)result=1;else{x=power(a,p/2,n);//遞歸計(jì)算result=(x*x)%n;//二次探測(cè)if((result==1)&&(x!=1)&&(x!=n-1))composite=true;if((p%2)==1)//p是奇數(shù)result=(result*a)%n;}returnresult;}booleanprime(intn){//素?cái)?shù)測(cè)試的蒙特卡羅算法rnd=newRandom();inta,result;composite=false;a=rnd.random(n-3)+2;result=power(a,n-1,n);if(composite||(result!=1))returnfalse;elsereturntrue;}算法prime是一個(gè)偏假3/4正確的蒙特卡羅算法。通過多次重復(fù)調(diào)用錯(cuò)誤概率不超過(1/4)k。這是一個(gè)很保守的估計(jì)，實(shí)際使用的效果要好得多。素?cái)?shù)測(cè)試Wilson定理：對(duì)于給定的正整數(shù)n，判定n是一個(gè)素277.8NP難與NP完全問題一、易解的問題和難解的問題存在多項(xiàng)式時(shí)間算法的問題，稱為易解的問題指數(shù)時(shí)間算法或排列時(shí)間算法的問題，稱為難解的問題二、難解問題的計(jì)算相關(guān)性計(jì)算相關(guān)：某類問題可以歸約為另一類問題計(jì)算相關(guān)的問題，若它們之一可用多項(xiàng)式時(shí)間求解，則其它同類問題也可用多項(xiàng)式時(shí)間求解；若它們之一肯定不存在多項(xiàng)式時(shí)間算法，則同類的其它問題，也肯定不會(huì)找到多項(xiàng)式時(shí)間算法。7.8NP難與NP完全問題一、易解的問題和難解的問題287.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.1297.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完全問題

P類和NP類問題定義12.307.8NP難與NP完全問題

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

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

NP難問題NP難317.8NP難與NP完全問題

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

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

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

NP完全問題NP完全問題327.8NP難與NP完全問題

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

NP難題和NP完全問題的差別337.8NP難與NP完全問題

1、歸約的傳遞性定理12.3令、和是三個(gè)判定問題，滿足，及