[科普中國(guó)]-隨機(jī)算法

基本概念

一個(gè)隨機(jī)算法是一種算法，它采用了一定程度的隨機(jī)性作為其邏輯的一部分。該算法通常使用均勻隨機(jī)位作為輔助輸入來(lái)指導(dǎo)自己的行為，超過(guò)隨機(jī)位的所有可能的選擇實(shí)現(xiàn)了“平均情況下的”良好業(yè)績(jī)的希望。從形式上看，該算法的性能將會(huì)是一個(gè)隨機(jī)變量，由隨機(jī)位決定;因此無(wú)論是運(yùn)行時(shí)間，或輸出（或兩者）是隨機(jī)變量。

在常見(jiàn)的實(shí)踐中，隨機(jī)化算法是使用近似的偽隨機(jī)數(shù)發(fā)生器代替隨機(jī)比特的真實(shí)來(lái)源的;這樣的實(shí)施可以從預(yù)期的理論行為偏離。

解問(wèn)題P的隨機(jī)算法定義為：設(shè)I是問(wèn)題P的一個(gè)實(shí)例，用算法解I的某些時(shí)刻，隨機(jī)選取 ，由

b來(lái)決定算法的下一步動(dòng)作。

優(yōu)點(diǎn)：1、執(zhí)行時(shí)間和空間，小于同一問(wèn)題的已知最好的確定性算法；

2、實(shí)現(xiàn)比較簡(jiǎn)單，容易理解；

3、快速且易于并行化。

三要素：輸入實(shí)例、隨機(jī)源和停止準(zhǔn)則。

一種平衡：隨即算法可以理解為在時(shí)間、空間和隨機(jī)三大計(jì)算資源中的平衡。2

背景及歷史重要方法Monte Carlo求定積分法

隨機(jī)K-選擇法

隨機(jī)快排序

素性判定的隨機(jī)算法

二階段隨機(jī)路由算法

重要人物和工作de Leeuw等人提出了概率圖靈機(jī)（1955）

John Gill的隨機(jī)算法復(fù)雜性理論（1977）

Rabin的數(shù)論和計(jì)算幾何領(lǐng)域的工作（1976）

Karp的算法概率分析方法（1985）

Shor的素因子分解量子算法（1994）3

類型分類1、數(shù)值概率算法：用于數(shù)值問(wèn)題的求解。所得到的解幾乎都是近似解，近似解的精度

隨著計(jì)算時(shí)間的增加而不斷地提高。

2、拉斯維加斯算法（LasVegas）：要么給出問(wèn)題的正確答案，要么得不到答案。反復(fù)求解多次，可

使失效的概率任意小。

3、蒙特卡羅算法（MonteCarlo）：總能得到問(wèn)題的答案，偶然產(chǎn)生不正確的答案。重復(fù)運(yùn)行，每一次

都進(jìn)行隨機(jī)選擇，可使不正確答案的概率變得任意小。

4、舍伍德算法（Sherwood）：很多具有很好的平均運(yùn)行時(shí)間的確定性算法，在最壞的情況下性能很

壞。引入隨機(jī)性加以改造，可以消除或減少一般情況和最壞情況的差別。14

時(shí)間復(fù)雜性衡量確定性算法的時(shí)間復(fù)雜性，是取它的平均運(yùn)行時(shí)間。

衡量隨機(jī)算法的時(shí)間復(fù)雜性，是對(duì)確定實(shí)例I的期望運(yùn)行時(shí)間，即反復(fù)地運(yùn)行實(shí)例I，所取的平均運(yùn)行時(shí)間。

在隨機(jī)算法里，所討論的是最壞情況下的期望時(shí)間，和平均情況下的期望時(shí)間。4

隨即算法的設(shè)計(jì)方法1、挫敗對(duì)手（Foiling the Adversary）

將不同的算法組成算法群，根據(jù)輸入實(shí)例的不同隨機(jī)地或有選擇地選取不同的算法，以使性能達(dá)到最佳。

2、隨機(jī)采樣（Random Sampling）

用“小”樣本群的信息，指導(dǎo)整體的求解。

3、隨機(jī)搜索（Random Search）

是一種簡(jiǎn)單易行的方法，可以從統(tǒng)計(jì)角度分析算法的平均性能，如果將搜索限制在有解或有較多解的區(qū)域，可以大大提到搜索的成功概率。

4、指紋技術(shù)（Fingerprinting）

利用指紋信息可以大大減少對(duì)象識(shí)別的工作量。通過(guò)隨機(jī)映射的取值方法，Karp和Rabin得到了一個(gè)快速的串匹配隨即算法。

5、輸入隨機(jī)重組（Input Randomization）

對(duì)輸入實(shí)例進(jìn)行隨機(jī)重組后，可以改進(jìn)算法的平均性能。

6、負(fù)載平衡（Load Balancing）

在并行與分布計(jì)算、網(wǎng)絡(luò)通訊等問(wèn)題中，使用隨機(jī)選擇技術(shù)可以達(dá)到任務(wù)的負(fù)載平衡和網(wǎng)絡(luò)通訊的平衡。

7、快速混合Markov鏈（Rapidly Mixing Markov Chain）

使用該方法可以解決大空間中的均勻抽樣問(wèn)題。

8、孤立和破對(duì)稱技術(shù)（Isolation and Symmetry Breaking）

使用該技術(shù)可以解決處理的并行性，避免分布式系統(tǒng)的死鎖等問(wèn)題。如：

圖著色算法，部分獨(dú)立集問(wèn)題。

9、概率存在性證明（Probabilistic Methods and Existence Proofs）

如果隨機(jī)選取的物體具有某種特性的概率大于0，則具有該特性的物體一定存在。

10、消除隨機(jī)性（Derandomization）

許多優(yōu)秀的確定性算法是由隨機(jī)算法轉(zhuǎn)換而來(lái)的。3

隨機(jī)算法舉例Quick Sort（1）傳統(tǒng)的快排序算法

總是取第一個(gè)元素作為劃分元；

算法的最壞運(yùn)行時(shí)間是O( )，平均時(shí)間是O( );

因此存在一些輸入實(shí)例，使得算法達(dá)到最壞運(yùn)行時(shí)間

如：降序的序列；

（2）隨即快排序算法

隨機(jī)選擇一個(gè)元素作為劃分元；

任何一個(gè)輸入的期望時(shí)間是O（ ）；

這是一個(gè)Las Vegas算法；

Min Cut（1）最小截問(wèn)題定義：

給定一個(gè)無(wú)向圖G(V,E),找一個(gè)截（V1,V2）使得V1和V2間的連邊數(shù)最小。

（2）該問(wèn)題可以用確定性算法（max-flow min-cut algorithm）在O( )時(shí)間內(nèi)完成。

（3）隨機(jī)算法

隨機(jī)選一條邊，將兩頂點(diǎn)合一并除去頂點(diǎn)上的環(huán)；

直到圖中只剩下兩個(gè)頂點(diǎn)；

返回剩下兩頂點(diǎn)建德連邊數(shù)；

（4）示例：#cut=2

（5）出錯(cuò)概率

重復(fù)K次出錯(cuò)概率為

(6)本算法是一個(gè)Monte Carlo型算法3