算法設(shè)計與分析 課件 許瑾晨 第九章 概率算法

算法設(shè)計與分析算法設(shè)計-概率算法信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版一二三算法引例算法基本思想算法分類隨機函數(shù)典型應(yīng)用快速排序N皇后求Pi主元素求解重點掌握：1.算法的基本思想2.不同概率算法的區(qū)別算法設(shè)計與分析概率算法-引例信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)1,2,2,3,2,4,2,4,2,2假設(shè)一定存在主元素方法一：排序，位置5的數(shù)即為主元素1222222344求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2方法二：士兵守陣地，留下的士兵就是主元素1223242422VS求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS1223242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS1223242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS23242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS23242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS23242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS242422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS2422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS2422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS2422求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS22求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS22求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守陣地，留下的士兵就是主元素VS22求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法三：上帝扔骰子，選擇后再判斷1223242422123456789103求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2方法三：上帝扔骰子，選擇后再判斷1223242422123456789102求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)假設(shè)一定存在主元素1,2,2,3,2,4,2,4,2,2求一串?dāng)?shù)中的主元素，即出現(xiàn)次數(shù)超過一半的數(shù)方法三：上帝投色子方法二：士兵守陣地方法一：排序確定算法概率算法允許算法執(zhí)行過程中隨機地選擇計算步驟，因此算法的每一次執(zhí)行過程可能都不完全相同。算法的每一計算步驟都是確定的，在輸入不變的情況下，不管重復(fù)執(zhí)行算法多少次，其結(jié)果都完全相同。確定算法：遞歸、分治、動規(guī)、貪心、搜索概率算法測試選擇題：本節(jié)課針對主元素求解問題給出的三種方法：排序法，士兵守陣地和概率算法，三種算法在平均情況下需要的計算次數(shù)分別表示為W1，W2和W3，三者從大到小排序正確的是（）A：W1，W2，W3B：W1，W3，W2C：W2，W3，W1D：W2，W1，W3E：W3，W2，W1F：W3，W1，W2算法設(shè)計與分析概率算法-舍伍德信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版當(dāng)一個確定性算法的平均和最壞時間復(fù)雜度差別較大時，可在確定性算法中引入隨機性將確定算法改造為概率算法。這類通過引入隨機性減少算法的最壞情形對應(yīng)輸入的出現(xiàn)次數(shù)的算法稱為舍伍德算法。

對確定性算法A，記輸入實例I的計算時間為tA(I)。設(shè)Dn是算法A的輸入規(guī)模為n的全體實例，可能存在I∈Dn使得。目標：實現(xiàn)概率算法B，使得對規(guī)模為n的問題的每個實例均有。其中，s(n)與相比可忽略。defkth_small(a,b,e,k):#在a[b]~a[e]中找第k小元素ifb>eork<1ork>e-b+1:return-1p=partition(a,b,e)m=p-bifk==m+1:returna[p]ifk<m+1:returnkth_small(a,b,p-1,k)returnkth_small(a,p+1,e,k-m-1)例：選擇第k小元素defpartition(a,b,e):#將a[b]~a[e]以基準數(shù)為標準分為三部分i=bj=e

x=a[b]whilei<j:#從兩邊開始搜索與基準數(shù)進行比較whilei<janda[j]>=x:j-=1ifi<j:a[i]=a[j]i+=1whilei<janda[i]<x:i+=1ifi<j:a[j]=a[i]j-=1a[i]=xreturni舍伍德算法實現(xiàn)：選擇第k小元素defpartition(a,b,e):#將a[b]~a[e]以基準數(shù)為標準分為三部分i=bj=ek=b+randint(0,e-b)#隨機選擇基準元素a[b],a[k]=a[k],a[b]#將隨機選擇的基準元素與首位元素互換x=a[b]whilei<j:whilei<janda[j]>=x:j-=1ifi<j:a[i]=a[j]i+=1whilei<janda[i]<x:i+=1ifi<j:a[j]=a[i]j-=1a[i]=xreturni優(yōu)勢：

對所有實例的計算時間相對均勻，計算總能求得問題的一個解，且求得的解總是正確的。關(guān)鍵：

與相應(yīng)的確定算法相比，其時間復(fù)雜性并沒有改進。測試判斷題：舍伍德算法可以降低算法的最壞時間復(fù)雜度A：

正確B：錯誤算法設(shè)計與分析概率算法-拉斯維加斯信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版

拉斯維加斯算法可以顯著地改進算法的有效性(得到正確解的可能性)，甚至對某些迄今為止找不到有效算法的問題，也能得到滿意的結(jié)果。

特征:隨機性決策有可能導(dǎo)致算法找不到所需的解。算法找到正確解的概率隨所用計算時間的增加而提高，得到的解一定是正確解，但算法可能找不到解。對同一個問題，用拉斯維加斯算法反復(fù)求解多次，可使求解失敗的概率任意小。

拉斯維加斯算法應(yīng)用形式：反復(fù)調(diào)用拉斯維加斯算法LV(x,y)，直到找到問題的一個解。voidobstinate(Objectx,Objecty){booleansuccess=false;while(!success)success=lv(x,y);}n后問題：

在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQN皇后問題的拉斯維加斯算法實現(xiàn)：

算法是否得到正確解一方面取決于隨機性，更重要的則取決于算法運行的時間，只要有足夠的運行時間，就可以得到正確解。測試判斷題：拉斯維加斯算法可能得不到問題的解，但若得到一個解，解一定是正確的。A：

正確B：錯誤算法設(shè)計與分析概率算法-蒙特卡羅信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版思政：國防--催生新技術(shù)的源動力“曼哈頓計劃”摩納哥

蒙特卡羅馮·諾伊曼目標：

求問題的準確解特征：求得的解不一定正確，且無法判定所得解是否肯定正確。設(shè)p是0.5到1間的實數(shù)。若算法得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且p-1/2是該算法的優(yōu)勢。求得正確解的概率依賴于算法所用時間，時間越多，得到正確解的概率越高此外，若對于同一問題，蒙特卡羅算法不會給出不同的正確解答，則稱該蒙特卡羅算法是一致的。應(yīng)用：數(shù)值問題求解

求近似解

近似解精度隨計算時間的增加而不斷提高。例1：計算

值隨機投點法半徑為r的圓的外切四邊形內(nèi)投點

defdarts(n):k=0foriinrange(1,n+1):x=random()#在[0，1)內(nèi)隨機選擇一個數(shù)作為xy=random()#在[0，1)內(nèi)隨機選擇一個數(shù)作為yifx**2+y**2<=1:k+=1return4*k/n例1：計算

值測試判斷題：針對計算Pi值的蒙特卡羅算法實現(xiàn)代碼，當(dāng)n=1000時，獨立運行兩次程序，會得到一樣的結(jié)果。A：正確 B：錯誤例2：計算定積分

設(shè)f(x)是[0,1]上的連續(xù)函數(shù)，且0f(x)1。需要計算的積分為。

假設(shè)向單位正方形內(nèi)隨機地投入n個點(xi,yi)。如果有m個點落入積分區(qū)域內(nèi)，則defdarts(n):k=0foriinrange(1,n+1):x=random()#在[0，1)內(nèi)隨機選擇一個數(shù)作為xy=random()#在[0，1)內(nèi)隨機選擇一個數(shù)作為yify<=f(x):k+=1returnk/n例2：計算定積分例3：主元素問題

設(shè)數(shù)組T[1:n]含有n個元素。當(dāng)|{i|T[i]=x}|>n/2時，稱元素x是數(shù)組T的主元素。defmajority(t):n=len(t)-1i=randint(1,n)x=t[i]#隨機選擇數(shù)組元素k=0forjinrange(1,n+1):ift[j]==x:k+=1returnk>n/2#k>n/2時t含有主元素返回true時，一定含有主元素，但返回false時，數(shù)組未必不含主元素重復(fù)調(diào)用主元素蒙特卡羅算法boolmajority2(int[]t,intn){if(majority(t,n))returntrue;e