高級算法設計與分析

第二章概率分析與隨機算法2主要內容概率初步隨機算法雇用問題指示器隨機變量隨機算法概率分析和指示器隨機變量的進一步應用例子：爬樓梯、n皇后、背包問題

計數(shù)理論計數(shù)理論嘗試回答“多少”的問題加法規(guī)則與乘法規(guī)則加法規(guī)則指出，從兩個不相交集合之一中選擇一個元素時，方法的數(shù)目是這兩個集合的數(shù)目之和。例如，汽車牌照的每一位是一個字母或一個數(shù)字。因為字母有26種選擇，數(shù)字有10種選擇，因此每一位可能的數(shù)目是26+10=36。乘法規(guī)則指出，選擇一個有序對時，方法的數(shù)目是選擇第一個元素的方法數(shù)乘以選擇第二個元素的方法數(shù)。例如，如果冰淇淋店提供28種口味的冰淇淋和4種奶油，則由一勺冰淇淋和一種奶油組成的圣代冰淇淋的數(shù)目為28×4=112。S={0,1}，有限集合S的串是S中元素的一個序列。例如，有8個長度為3的二進制串： 000,001,010,011,100,101,110,111有時，將長度為k的串稱為k串。串s的子串s'是連續(xù)元素的一個有序序列。k子串是長度為k的子串。例如，010是01101001的一個3子串，但111不是01101001的子串。集合S的k串可以被看成笛卡兒積S

k

的一個元素，它是一個k元組。因此，有|S|k個長度為k的串。例如，二進制k串的個數(shù)是2k.4串Strings有限集合S的排列是S中所有元素的有序序列，且每個元素僅出現(xiàn)一次。例如，如果S={a,b,c}，則S有6種排列：abc,acb,bac,bca,cab,cba.一個有n個元素的集合有n!種排列，因為序列的第一個元素可以有n種選擇，第二個元素有n-1……集合S的k排列是S中k個元素的有序序列，且每個元素僅出現(xiàn)一次。集合{a,b,c,d}的12個2排列是：ab,ac,ad,ba,bc,bd,ca,cb,cd,da,db,dc.n元集合的k排列的數(shù)目:

排列組合n元集S的k組合就是S的k子集。例如，4元集{a,b,c,d}有6個2組合：{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}。n元集k組合的數(shù)目可以用其k排列的數(shù)目來表示。對每個k組合，它的元素恰好有k！種排列，每個都是n元集的一個不同的k排列。因此，n元集k組合的數(shù)目是其k排列的數(shù)目除以k！。根據(jù)式（C.1），這個數(shù)量是：對k=0，這個公式告訴我們從n元集中選擇0個元素有1種方法，因此0！=1。

7

二項式系數(shù)

概率

離散概率分布一副10張的紙牌，每張帶有一個1到10不同的數(shù)字，并通過洗牌將它們徹底打亂。每次從這副牌中抽一張(抽出后放回)，一共抽3張。這三張牌按升序被選中的概率是多少？10練習首先知道總共的事件數(shù)為：10*10*10=1000其次需要計算10個數(shù)中所有3升序的個數(shù)不妨這樣分析：顯然第一個數(shù)n只能是1-8n=8時,只有一種情況,為s=1=C(2,2)n=7時有三種情況s=3=C（2,3）n=6時有六種情況s=6=C(2,4)以此類推有總數(shù)目

S=C（2,2）+C(2,3)+C(3,4)+...+C(2,9)=120所以最終的概率為120/1000=12%11如果你是一個游戲的參加者，這個游戲的獎品放在三個幕布的其中一個后面。如果你進擇了正確的幕布，你就會贏得獎品。你選擇了一個幕布，但在你掀起幕布前，主持人配起其他兩個幕布之一，使你知道那個幕布里面是空的，并詢問你是否愿意改選剩下的別個幕布。如果你改選，你的機會將會如何變化？練習參考：/p/48254298枚舉法當選擇更換時，其贏得汽車的概率為2/3，

當堅持初次選擇時，其贏得汽車的概率為1/3。概率的乘法公式MonteCarlomethod13一個監(jiān)獄看守從三個罪犯中隨機選擇一個予以釋放，其他兩個將被處死。警衛(wèi)知道哪個人是否會被釋放，但是不允許給罪犯任何關于其狀態(tài)的信息。讓我們分別稱罪犯為X,Y,Z。罪犯X私下問警衛(wèi)Y或Z哪個會被處死，因為他已經(jīng)知道他們中至少一個人會死，警衛(wèi)不能透露任何關于他本人狀態(tài)的信息。警衛(wèi)告訴X,Y將被處死。X感到很高興，因為他認為他或者Z將被釋放，這意味著他被釋放的概率是1/2。他正確嗎？或者他的機會仍是1/3？請解釋。/jlugene/archive/2010/12/07/1898565.html練習離散隨機變量對一個隨機變量來說，關于其分布的最簡單、最有效的概括是它具有取值的“平均”。一個離散隨機變量X的期望值（期望或中數(shù)）是:考慮一個拋兩個均質硬幣的游戲。有一個正面向上你贏3美元，有一個反面向上你輸2美元。表示收入的隨機變量X的期望值是:

期望17方差和標準差狂歡節(jié)游戲中使用一個帶有3個骰子的罩子。參加者可以在1到6的任意一個數(shù)字上押1美元。主持人搖動罩子，并按如下方法決定參加者獲得的回報。如果任何一個骰子都未出現(xiàn)參加者所押的數(shù)字，則他輸?shù)羲旱腻X。反之，如果他押的數(shù)字出現(xiàn)在三個骰子中k次，k=1,2,3，則他收回所押的錢并額外獲得k美元。莊家玩一次游戲的收入期望是多少？5*5*5/(6*6*6)-C(1,3)*5*5/(6*6*6)-2*C(2,3)*5/(6*6*6)-3*C(3,3)/(6*6*6)18練習有兩個藏寶地點，一個為真的，一個是假的；之間的距離代表到達藏寶地點的所需要天數(shù)；解讀藏寶圖要4天，然后就能知道真的藏寶地點再出發(fā)，但不允許出發(fā)后解讀；另外一個人每天會拿走一部分寶藏；有一個小精靈可告訴你如何解讀，但需支付相當于另外一個人3天拿走的寶藏。問題：如何做才能得到更多的寶藏？195天5天5天概率算法的設計思想假設得到藏寶圖時剩余寶藏價值是x，知道藏寶地點的那個人每天拿走寶藏價值是y，并且x>9y，可行方案有：用4天時間解讀藏寶圖，用5天時間到達藏寶地點，可獲得寶藏價值x-9y;接受小精靈的條件，用5天時間到達藏寶地點，并支付給小精靈寶藏價值3y，則可獲寶藏價值x-5y-3y=x-8y;投擲硬幣決定首先前往哪個地點，如果發(fā)現(xiàn)地點是錯的，就前往另一個地點。這樣有一半的機會獲得寶藏價值x-5y，另一半機會獲得寶藏價值x-10y，這樣最終可獲寶藏價值是x-7.5y。20概率算法的設計思想確定性算法，即算法的每一步都明確指定下一步該如何進行，對于任何合理的輸入，確定性算法都必須給出正確的輸出。概率算法把“對于所有合理的輸入都必須給出正確的輸出”這一求解問題的條件放寬，允許算法在執(zhí)行過程中隨機選擇下一步該如何進行，同時允許結果以較小的概率出現(xiàn)錯誤，并以此為代價，獲得算法運行時間的大幅度減少。21概率算法判斷表達式f(x1,x2,…,xn)是否恒等于0。首先生成一個隨機n元向量(r1,r2,…,rn)并計算f(r1,r2,…,rn)的值，如果f(r1,r2,…,rn)≠0，則f(x1,x2,…,xn)不恒等于0；如果f(r1,r2,…,rn)＝0，則或者f(x1,x2,…,xn)恒等于0，或者是(r1,r2,…,rn)比較特殊，重復幾次，繼續(xù)得到f(r1,r2,…,rn)＝0的結果，那么就可以得出f(x1,x2,…,xn)恒等于0的結論測試的隨機向量越多，這個結果出錯的可能性就越小。22概率算法一般情況下，概率算法具有以下基本特征：（1）概率算法的輸入包括兩部分，一部分是原問題的輸入，另一部分是一個供算法進行隨機選擇的隨機數(shù)序列；（2）概率算法在運行過程中，包括一處或若干處隨機選擇，根據(jù)隨機值來決定算法的運行；（3）概率算法的結果不能保證一定是正確的，但可以限定其出錯概率；（4）概率算法在不同的運行中，對于相同的輸入實例可以有不同的結果，因此，對于相同的輸入實例，概率算法的執(zhí)行時間可能不同。同一輸入實例運行同一概率算法求解兩次可能得到完全不同的效果（結果和所需時間），所以一旦概率算法失敗了，只需重啟算法又有成功的希望。另外運行幾次概率算法，有可能得到幾個不同的答案。23概率算法24概率算法的分類25數(shù)值概率算法：求π

的值26對于確定性算法，通常分析在平均情況下以及最壞情況下的時間復雜性。對于概率算法，通常分析在平均情況下以及最壞情況下的期望時間復雜性，即由概率算法反復運行同一輸入實例所得的平均運行時間。需要強調的是，“隨機”并不意味著“隨意”。如手工運行算法，可通過擲骰子來得到一個隨機結果，在計算機中則通過隨機數(shù)發(fā)生器來實現(xiàn)。概率算法的時間性能目前，在計算機上產(chǎn)生隨機數(shù)還是一個難題，因為在原理上，這個問題只能近似解決。計算機中產(chǎn)生隨機數(shù)的方法通常采用線性同余法，產(chǎn)生的隨機數(shù)序列為a0,a1,…,an，滿足：

其中，b≥0，c≥0，m＞0，d≤m。d稱為隨機數(shù)發(fā)生器的隨機種子（RandomSeed），當b、c和m的值確定后，給定一個隨機種子，由上式產(chǎn)生的隨機數(shù)序列也就確定了。27隨機數(shù)發(fā)生器計算機語言提供的隨機數(shù)發(fā)生器，一般會輸出一個分布在開區(qū)間（0,1）上的隨機小數(shù)，并且需要一個隨機種子，這個隨機種子可以是系統(tǒng)當前的日期或時間。下面給出利用C++語言中的隨機函數(shù)rand產(chǎn)生的分布在任意區(qū)間[a,b]上的隨機數(shù)算法。—隨機數(shù)發(fā)生器

intRandom(inta,intb){returnrand()%(b-a)+a;//rand()產(chǎn)生(0,32767)之間的隨機整數(shù)

}C++描述28隨機數(shù)發(fā)生器分析確定性算法在平均情況下的時間復雜性時，通常假定算法的輸入實例滿足某一特定的概率分布。事實上，很多算法對于不同的輸入實例，其運行時間差別很大。此時，可以采用舍伍德型概率算法來消除算法的時間復雜性與輸入實例間的這種聯(lián)系。29舍伍德(Sherwood)型概率算法隨機洗牌

voidRandomShuffle(intn,intr[]){for(i=0;i<n;i++){j=Random(0,n-i-1);r[i]←→r[j];//交換r[i]和r[j]}}C++描述如果一個確定性算法無法直接改造成舍伍德型概率算法，可借助于隨機預處理技術，即不改變原有的確定性算法，僅對其輸入實例隨機排列（稱為洗牌）。假設輸入實例為整型，下面的隨機洗牌算法可在線性時間實現(xiàn)對輸入實例的隨機排列。30舍伍德(Sherwood)型概率算法舍伍德型概率算法總能求得問題的一個解，并且所求得的解總是正確的。但與其相對應的確定性算法相比，舍伍德型概率算法的平均時間復雜性沒有改進。舍伍德型概率算法不是避免算法的最壞情況行為，而是設法消除了算法的不同輸入實例對算法時間性能的影響，對所有輸入實例而言，舍伍德型概率算法的運行時間相對比較均勻，其時間復雜性與原有的確定性算法在平均情況下的時間復雜性相當。31舍伍德(Sherwood)型概率算法快速排序算法的關鍵在于一次劃分中選擇合適的軸值作為劃分的基準，如果軸值是序列中最?。ɑ蜃畲螅┯涗洠瑒t一次劃分后，由軸值分割得到的兩個子序列不均衡，使得快速排序的時間性能降低。舍伍德型概率算法在一次劃分之前，根據(jù)隨機數(shù)在待劃分序列中隨機確定一個記錄作為軸值，并把它與第一個記錄交換，則一次劃分后得到期望均衡的兩個子序列，從而使算法的行為不受待排序序列的不同輸入實例的影響，使快速排序在最壞情況下的時間性能趨近于平均情況的時間性能。32快速排序一次劃分結果［61319］23［313528］初始鍵值序列6131923313558一次劃分結果6［131923313558］初始鍵值序列6131923313558隨機選擇一個2313196313558記錄與6交換(a)以最小值6為軸值，劃分不均衡(b)隨機選擇軸值，劃分均衡33快速排序—隨機快速排序

voidQuickSort(intr[],intlow,inthigh){if(low<high){i=Random(low,high);r[low]←→r[i];k=Partition(r,low,high);QuickSort(r,low,k-1);QuickSort(r,k+1,high);}}C++描述34快速排序

算法在最壞情況下的時間復雜性仍是O(n2)，這是由于隨機數(shù)發(fā)生器在第i次隨機產(chǎn)生的軸值記錄恰好都是序列中第i小（或第i大）記錄。但是，作為隨機數(shù)發(fā)生器，這種情況的出現(xiàn)概率是微乎其微的。事實上，輸入記錄的任何排列，都不可能出現(xiàn)使算法行為處于最壞的情況。因此，該算法的期望時間復雜性是O(nlog2n)。

35快速排序

拉斯維加斯型概率算法不時地做出可能導致算法陷入僵局的選擇，并且算法能夠檢測是否陷入僵局，如果是，算法就承認失敗。這種行為對于一個確定性算法是不能接受的，因為這意味著它不能解決相應的問題實例。但是，拉斯維加斯型概率算法的隨機特性可以接受失敗，只要這種行為出現(xiàn)的概率不占多數(shù)。當出現(xiàn)失敗時，只要在相同的輸入實例上再次運行概率算法，就又有成功的可能。36拉斯維加斯(LasVegas)型概率算法

拉斯維加斯型概率算法的一個顯著特征是，它所做的隨機性選擇有可能導致算法找不到問題的解，即算法運行一次，或者得到一個正確的解，或者無解。因此，需要對同一輸入實例反復多次運行算法，直到成功地獲得問題的解。由于拉斯維加斯型概率算法有時運行成功，有時運行失敗，因此，通常拉斯維加斯型概率算法的返回類型為bool，并且有兩個參數(shù)：一個是算法的輸入，另一個是當算法運行成功時保存問題的解。當算法運行失敗時，可對同一輸入實例再次運行，直到成功地獲得問題的解。37拉斯維加斯(LasVegas)型概率算法拉斯維加斯型概率算法的一般形式voidObstinate(inputx,solutiony){success=false;while(!success)success=LV(x,y);}38拉斯維加斯(LasVegas)型概率算法設p(x)是對輸入實例x調用拉斯維加斯型概率算法獲得問題的一個解的概率，則一個正確的拉斯維加斯型概率算法應該對于所有的輸入實例x均有p(x)>0。要求存在一個正的常數(shù)δ，使得對于所有的輸入實例x均有p(x)>δ。由于p(x)>δ，所以，只要有足夠的時間，對任何輸入實例x，拉斯維加斯型概率算法總能找到問題的一個解。拉斯維加斯型概率算法找到正確解的概率隨著計算時間的增加而提高。

39拉斯維加斯(LasVegas)型概率算法八皇后問題是在8×8的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。每一個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更像是隨機放置的。拉斯維加斯型概率算法：在棋盤上相繼的各行中隨機地放置皇后，并使新放置的皇后與已放置的皇后互不攻擊，直至八個皇后均已相容地放置好，或下一個皇后沒有可放置的位置。

40八皇后問題

由于棋盤的每一行上可以而且必須放置一個皇后，所以八皇后問題的可能解用一個向量X=(x1,x2,…,x8)表示，其中，1≤xi≤8并且1≤i≤8，即第i個皇后放置在第i行第xi列上。由于兩個皇后不能位于同一列上，所以，解向量X必須滿足約束條件：xi≠xj

若兩個皇后擺放的位置分別是(i,xi)和(j,xj)，在棋盤上斜率為-1的斜線上，滿足條件i-j=xi-xj，在棋盤上斜率為1的斜線上，滿足條件i＋j=xi＋xj，綜合兩種情況，由于兩個皇后不能位于同一斜線上，所以，解向量X必須滿足約束條件：

|i-xi|≠|j-xj|滿足約束的向量X=(x1,x2,…,xi)表示已放置的i個皇后（1≤i≤8）互不攻擊，也就是不發(fā)生沖突。

41八皇后問題

八皇后問題

1.將數(shù)組x[8]初始化為0；試探次數(shù)count初始化為0；

2．for(i=1;i<=8;i++)2.1產(chǎn)生一個[1,8]的隨機數(shù)j；

2.2count=count+1，進行第count次試探；

2.3若皇后i放置在位置j不發(fā)生沖突，則x[i]=j；count=0；轉步驟2放置下一個皇后；

2.4若(count==8)，則無法放置皇后i，算法運行失?。环駝t，轉步驟2.1重新放置皇后i；

3.將元素x[1]～x[8]作為八皇后問題的一個解輸出；偽代碼42八皇后問題

將上述隨機放置策略與回溯法相結合，則會獲得更好的效果?？梢韵仍谄灞P的若干行中隨機地放置相容的皇后，然后在其他行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。在棋盤中隨機放置的皇后越多，回溯法搜索所需的時間就越少，但失敗的概率也就越大。例如八皇后問題，隨機地放置兩個皇后再采用回溯法比完全采用回溯法快大約兩倍；隨機地放置三個皇后再采用回溯法比完全采用回溯法快大約一倍；而所有的皇后都隨機放置比完全采用回溯法慢大約一倍。不能忽略產(chǎn)生隨機數(shù)所需的時間，當隨機放置所有的皇后時，八皇后問題的求解大約有70%的時間都用在了產(chǎn)生隨機數(shù)上。

43八皇后問題

對于許多問題來說，近似解毫無意義。如布爾型的解，或像整數(shù)因子劃分問題的解必須是準確的。蒙特卡羅型概率算法用于求問題的準確解。因為屬于概率算法，該算法偶爾也會出錯，但無論任何輸入實例，總能以很高的概率找到一個正確解。求得正確解的概率依賴于算法所用的時間，所用的時間越多，得到正確解的概率就越高。44蒙特卡羅(MonteCarlo)型概率算法蒙特卡羅型概率算法是P正確：如果該算法對于問題的任一輸入實例得到正確解的概率不小于P（P是屬于(1/2,1)間的實數(shù)）。蒙特卡羅型概率算法是一致：如果對于同一輸入實例，該算法不會給出兩個不同的正確解。蒙特卡羅型概率算法的參數(shù)除了問題輸入實例I外，還有描述錯誤解可接受概率的參數(shù)，其時間復雜性由函數(shù)T(n,ε)描述。45蒙特卡羅(MonteCarlo)型概率算法設T[n]是一個含有n個元素的數(shù)組，x是數(shù)組T的一個元素，如果數(shù)組中有一半以上的元素與x相同，則稱元素x是數(shù)組T的主元素（MajorElement）。例如，在數(shù)組T[7]={3,2,3,2,3,3,5}中，元素3就是主元素。求解主元素的簡單方法是統(tǒng)計每個元素在數(shù)組中出現(xiàn)的次數(shù)，如某個元素出現(xiàn)次數(shù)大于n/2，則該元素就是數(shù)組的主元素，如沒有出現(xiàn)次數(shù)超過n/2的元素，則不存在主元素。顯然，該算法的時間復雜性是O(n2)

46

主元素問題蒙特卡羅型概率算法求解主元素問題:隨機地選擇數(shù)組中的一個元素T[i]進行統(tǒng)計，如果該元素出現(xiàn)的次數(shù)大于n/2，則該元素就是數(shù)組的主元素，算法返回true；否則隨機選擇的這個元素T[i]不是主元素，算法返回false。數(shù)組中可能有主元素也可能沒有主元素。如果數(shù)組中存在主元素，則非主元素的個數(shù)小于n/2。因此，算法將以大于1/2的概率返回true，以小于1/2的概率返回false，這說明算法出現(xiàn)錯誤的概率小于1/2。如果連續(xù)運行算法k次，算法返回false的概率將減少為2-k，則算法發(fā)生錯誤的概率為2-k。47

主元素問題主元素問題

boolMajority(intT[],intn){i=Random(0,n-1);x=T[i];//隨機選擇一個數(shù)組元素

k=0;for(j=0;j<n;j++)if(T[j]==x)k++;if(k>n/2)//k>n/2時含有主元素為T[i]returntrue;elsereturnfalse;}boolMajorityMC(intT[],intn,doublee){k=log(1/

)/log(2);for(i=1;i<=k;i++)if(Majority(T,n))returntrue;returnfalse;}C++描述48對于任何給定的

>0，算法MajorityMC重復調用

log2(1/

)

次算法Majority，其錯誤概率小于

，時間復雜性顯然是O(nlog2(1/

))。49

主元素問題假設得到藏寶圖時剩余寶藏價值是x，知道藏寶地點的那個人每天拿走寶藏價值是y，并且x>9y，可行方案有：用4天時間解讀藏寶圖，用5天時間到達藏寶地點，可獲得寶藏價值x-9y;接受小精靈的條件，用5天時間到達藏寶地點，并支付給小精靈寶藏價值3y，則可獲寶藏價值x-5y-3y=x-8y;投擲硬幣決定首先前往哪個地點，如果發(fā)現(xiàn)地點是錯的，就前往另一個地點。這樣有一半的機會獲得寶藏價值x-5y，另一半機會獲得寶藏價值x-10y，這樣最終可獲寶藏價值是x-7.5y。

你更接受哪個方案？是否一定選3方案？50

更多討論對風險的一個更深層次的探討Followourheart，請選擇你愿意給你1萬塊？50%的概率給你2萬塊，50的概率什么都不給你？你愿意給你5塊錢還是給你一張彩票，該彩票中500萬的概率為百萬分之一你愿意給你10塊錢還是給你一張價值5萬的彩票，該彩票中500萬的概率為百萬分之一人們不愿意后悔，厭惡風險損失很小的情況下，人們愿意冒險52對風險的一個更深層次的探討不同人的風險偏好不同效用與風險偏好人的決策選擇取決于結果與展望（即預期、設想）的差距，而非結果本身。人在決策時會在心里預設一個參考點，然后衡量每個結果是高于還是低于這個參考點。對于高于參考點的收益型結果，人們往往表現(xiàn)出風險厭惡，偏好確定的小收益；對于低于參考點的損失型結果，人們又表現(xiàn)出風險喜好，寄希望于好運氣來避免損失。另一方面，人對于概率的反應也有一些非線性，對于小概率會反應過敏，對大概率則會估計不足。這一現(xiàn)象導致阿萊悖論，但卻是人的真實心理反應。展望理論1、大多數(shù)人在面臨獲利的時候是風險規(guī)避的；2、大多數(shù)人在面臨損失的時候是風險偏好的；3、大多數(shù)人對損失比對獲得更為敏感。確定性效應：在確定的收益和“賭一把”之間選擇確定的收益。反射效應：在確定的損失和“賭一把”之間選擇“賭一把”。損失規(guī)避：對損失和獲得的敏感程度不同，面對損失的痛苦感要大大超過面對獲得的快樂感。小概率迷戀：即使小概率事件很少發(fā)生，很多人還是熱衷于買彩票、買保險。參照依賴：一般人對一個決策結果的評價，是通過計算該結果相對某一個參照點的變化而完成