廈門大學(xué)-算法分析-6

算法設(shè)計與分析——概率算法概率算法概率算法同前幾章算法的區(qū)別概率算法允許算法在執(zhí)行過程中隨機地選擇下一個計算步驟。在許多情況下，當(dāng)算法在執(zhí)行過程中面臨一個選擇時，隨機性選擇常比最優(yōu)選擇省時。概率算法的一個基本特征：對所求解問題的同一實例用同一概率算法求解兩次，可能得到完全不同的效果。反映在求解時間、結(jié)果質(zhì)量等方面。概率算法的主要類型概率算法的主要類型數(shù)值概率算法蒙特卡羅算法拉斯維加斯算法舍伍德算法數(shù)值概率算法數(shù)值概率算法常用于數(shù)值問題的求解，得到的往往是近似解解的精度隨計算時間的增加而提高在許多情況下，計算出問題的精確解是不可能或沒必要蒙特卡羅算法蒙特卡羅算法用于求解問題的準(zhǔn)確解在有些情況下，近似解沒有意義，比如“0/1”判定問題可以求得問題的一個解，但該解未必正確求得正確解的概率依賴于算法的計算時間蒙特卡羅算法的主要缺點就在于無法有效判定所得到的解是否肯定正確。拉斯維加斯算法拉斯維加斯算法不會得到不正確的解但有時找不到問題的解找到正確解的概率隨算法計算時間的增加而提高用同一拉斯維加斯算法反復(fù)對問題實例求解足夠多次，可使求解失敗的概率任意小。舍伍德算法舍伍德算法總能求解得到問題的一個解，而且所求得得解總是正確的。當(dāng)一個確定性算法在最壞情況下的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有較大差別時，可在這個確定算法中引入隨機性，將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的差別。舍伍德算法的精髓不是避免算法的最壞情況，而是設(shè)法消除這種最壞情形行為與特定實例之間的關(guān)聯(lián)性。提綱隨機數(shù)數(shù)值概率算法舍伍德算法拉斯維加斯算法蒙特卡羅算法本章小結(jié)提綱隨機數(shù)數(shù)值概率算法舍伍德算法拉斯維加斯算法蒙特卡羅算法本章小結(jié)隨機數(shù)隨機數(shù)在科學(xué)計算中扮演非常重要的角色?，F(xiàn)有的隨機數(shù)產(chǎn)生器所產(chǎn)生的隨機數(shù)都是偽隨機數(shù)在一定程度上是隨機的常用的隨機數(shù)產(chǎn)生方法線性同余法線性同余法該隨機序列的種子如何選取常數(shù)b、c、m將直接影響到所產(chǎn)生隨機序列的隨機性。隨機序列的產(chǎn)生與實驗隨機序列的產(chǎn)生參看教材242RandomfRandom模擬拋硬幣實驗參看教材244提綱隨機數(shù)數(shù)值概率算法舍伍德算法拉斯維加斯算法蒙特卡羅算法本章小結(jié)通過實例學(xué)習(xí)數(shù)值概率算法用隨機投點法計算π值計算定積分解非線性方程組用隨機投點法計算π值計算定積分解非線性方程組用隨機投點法計算π值算法思想設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機投擲n個點。落入圓內(nèi)的點數(shù)為k。用隨機投點法計算π值計算定積分解非線性方程組計算定積分用隨機投點法計算定積分用平均值法計算定積分用隨機投點法計算定積分Y=f(x)Gxy101用平均值法計算定積分滿足概率分布函數(shù)f(x)的要求算法實現(xiàn)用隨機投點法計算定積分參看教材246用平均值法計算定積分參看教材247用隨機投點法計算π值計算定積分解非線性方程組解非線性方程組求解過程會出現(xiàn)一些麻煩，甚至使方法失效而無法獲得一個近似解利用概率算法求解方法直觀、簡單，但工作量較大算法改進概率算法在求解非線性方程組時，雖然有些耗時，但實際應(yīng)用中還是比較有效的，對于那些精度要求較高的問題，概率算法往往會為其提供一個較好的初始值。算法實現(xiàn)過程參看教材249提綱隨機數(shù)數(shù)值概率算法舍伍德算法拉斯維加斯算法蒙特卡羅算法本章小結(jié)舍伍德算法舍伍德算法目的：設(shè)法消除最壞情形行為與特定實例之間的關(guān)聯(lián)性。其計算時間復(fù)雜性對所有實例而言相對均勻，但同相應(yīng)的確定性算法相比，其平均時間復(fù)雜性沒有改進。實例說明線性時間選擇跳躍表線性時間選擇跳躍表線性時間選擇線性時間選擇問題所在：選擇合適的劃分基準(zhǔn)對于選擇問題，用擬中位數(shù)作為劃分基準(zhǔn)可以保證在最壞情況下用線性時間完成選擇。舍伍德型選擇算法隨機選擇一個組元素作為劃分基準(zhǔn)，既保證算法的線性時間平均性能，又可以避免計算中位數(shù)的麻煩。Select算法分析Select算法分析如何得到？考慮這種情況：無論n是奇數(shù)還是偶數(shù)，T(n/2)都出現(xiàn)2次結(jié)論結(jié)論非遞歸的舍伍德型選擇算法Select可以在O(n)平均時間內(nèi)找出ｎ個輸入元素中的第ｋ小元素提示對于某些確定性算法，可以將其改造成舍伍德算法，使得該算法以高概率對任何實例均有效。對于某些不能直接改造的情況，可以借助預(yù)處理技術(shù)，不改變原有的確定性算法，而僅對其輸入元素進行隨機洗牌，同樣可以收到舍伍德算法的效果。線性時間選擇跳躍表跳躍表跳躍表如果用有序鏈表來表示一個含有ｎ個元素的有序集合Ｓ，則在最壞情況下，搜索Ｓ中的一個元素需要Ω(n)計算時間。為了跳高效率，可以在部分結(jié)點處增加附加指針來提高搜索性能（借助這些附加指針，可以跳過鏈表中的若干結(jié)點，從而加快搜索速度）。這種增加了向前附加指針的有序鏈表稱為跳躍表。２３５７ＮＩＬ11131719230舉例說明沒有附加指針的有序鏈表２３５７ＮＩＬ111317192301２３５７ＮＩＬ1113171923012增加附加指針后的有序鏈表——跳躍表如何進行搜索？２３５７ＮＩＬ1113171923012問題：如何在該跳躍表中搜索元素８？如何在該跳躍表中搜索元素８？２３５７ＮＩＬ1113171923012元素８位置２３５７ＮＩＬ1113171923012２３５７ＮＩＬ1113171923012元素８位置？元素８不在集合Ｓ中有序鏈表

跳躍表存在的問題應(yīng)在哪些結(jié)點增加附加指針，增加多少？２３５７ＮＩＬ11131719230隨機算法的引入解決方案采用隨機化方法來確定附加指針的增加結(jié)點位置和數(shù)量。使得跳躍表可以在O(logn)平均時間內(nèi)支持關(guān)于有序集的搜索、插入和刪除等運算操作。實現(xiàn)方案參看教材256２３５７ＮＩＬ1113171923012如何保持附加指針的平衡性，如何隨機生成新插入結(jié)點的級別附加指針的平衡性可用于指導(dǎo)附加指針的設(shè)置解決方案具體實現(xiàn)說明請參看教材page254隨機生成新插入結(jié)點的級別解決方案在完全跳躍表中，具有i級指針的結(jié)點中有一半同時具有i+1級指針方案事先確定一個實數(shù)p(0<p<1)，并要求在跳躍表中維持在具有i級指針的結(jié)點中同時具有i+1級指針的結(jié)點所占比例為p。在插入一個新結(jié)點時，先將其結(jié)點級別初始化為0，然后隨機反復(fù)產(chǎn)生一個[0，1]間的隨機實數(shù)q。如果q<p，則使新結(jié)點級別增加1，直到q>=p為止。為避免出現(xiàn)過大的結(jié)點級別，用log1/pn作為新結(jié)點級別的上界——參看教材255跳躍表的算法實現(xiàn)跳躍表的算法實現(xiàn)參看教材259提綱隨機數(shù)數(shù)值概率算法舍伍德算法拉斯維加斯算法蒙特卡羅算法本章小結(jié)拉斯維加斯算法拉斯維加斯算法(LasVegas)能夠顯著改進算法的有效性，對某些目前還找不到有效算法的問題，也能得到較為滿意的算法不會得到不正確的解，但有時找不到問題的解

通常用boolean型方法來表示拉斯維加斯算法找到解，返回true;未找到解，返回false;此時，可以對同一實例再次調(diào)用相同的算法由隨機算法的性質(zhì)決定效率分析Publicstaticvoidobstinate(Objectx,Objecty){booleansuccess=false;while(!success)success=lv(x,y)}反復(fù)調(diào)用拉斯維加斯算法lv(x,y)，直到找到問題的一個解y設(shè)p(x)是對輸入ｘ調(diào)用拉斯維加斯算法獲得問題一個解的概率，p(x)>0設(shè)t(x)是算法obstinate對于具體實例ｘ找到解的平均時間s(x)和e(x)分別是算法對于具體實例ｘ求解成功或失敗所需的平均時間實例說明實例說明Ｎ后問題整數(shù)因子分解Ｎ后問題整數(shù)因子分解Ｎ后問題Ｎ后問題問題描述：在n*n格的棋盤上放置彼此不受攻擊的ｎ個皇后。用回溯法求解時，算法系統(tǒng)地對整個解空間樹進行搜索，從而得到問題的解Ｎ＝８時問題的一個解被忽視的問題細(xì)節(jié)被忽視的問題細(xì)節(jié)對于Ｎ后問題的任意一個解，每個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性（更象是被隨機放置的）；可以在棋盤上相繼的各行中隨機放置皇后,注意使新位置上的皇后與已放置的皇后之間互不攻擊,直到N個皇后全部放置好(或下一個皇后沒有可以放置的位置)為止算法實現(xiàn)PublicstaticvoidnQueen(){x=newint[n+1];for(inti=0;i<=n;i++)x[i]=0;//初始化x//反復(fù)調(diào)用隨機放置Ｎ皇后的拉斯維加斯算法，直到放置成功while(!queensLV());}算法實現(xiàn)參看教材page260！存在的問題：一旦出現(xiàn)無法下一個皇后無法放置的情況，整個放置方案就需要推倒重來，而該方案中不排除包含部分合理的皇后位置設(shè)置解決方案隨機放置策略回溯法先按照隨機放置策略，在棋盤上的若干行上放置皇后（互不攻擊），然后在剩下的行中，利用回溯法來完成其余皇后的放置工作，直到所有皇后被放置完畢或無法為下一個皇后安排位置為止．隨機放置的皇后數(shù)越多，后續(xù)回溯搜索的時間就越少，但失敗概率也越大．*算法實現(xiàn)參看教材263隨機放置皇后數(shù)對算法效率的影響隨機放置皇后數(shù)pset０1.0000114.00-114.00１1.000039.63-39.63２0.875022.5339.6728.20３0.493113.4815.1029.01４0.261810.318.7935.10５0.16249.337.2946.92６0.13759.056.9853.50７0.12939.006.9755.93８0.12939.006.9755.93解８皇后問題的拉斯維加斯算法中，隨機放置皇后數(shù)所對應(yīng)的算法效率單純使用回溯法單純使用隨機放置策略Ｎ后問題整數(shù)因子分解整數(shù)因子分解用于整數(shù)因子分割的split算法privatestaticvoidsplit(n){intm=(int)Math.floor(Math.sqrt((double)n));for(inti=2;i<=m;i++) if(n%i==0)returnI;return1;}分析分析對于解整數(shù)因子分解問題，目前還沒有找到多項式時間算法；算法split(n)是對1~x的所有整數(shù)進行試除而得到范圍在1~x2的任意整數(shù)的因子分割；基于拉斯維加斯算法的整數(shù)因子分解問題求解方案Pollard算法——用split(n)算法相同的工作量可以得到在在1~x４范圍內(nèi)整數(shù)的因子分割．Pollard算法*算法實現(xiàn)參看教材page265花絮Shor算法量子計算機理論的重要里程碑算法顯示如何以量子計算機實現(xiàn)大數(shù)質(zhì)因子分解的最佳算法。P.W.Shor，Proceedingsofthe35thAnnu