-
隨機算法
鎖定
- 中文名
- 隨機算法
- 外文名
- randomized algorithm
- 所屬學科
- 計算機科學
隨機算法基本概念
一個隨機算法是一種算法，它採用了一定程度的隨機性作為其邏輯的一部分。該算法通常使用均勻隨機位作為輔助輸入來指導自己的行為，超過隨機位的所有可能的選擇實現了“平均情況下的”良好業績的希望。從形式上看，該算法的性能將會是一個隨機變量，由隨機位決定;因此無論是運行時間，或輸出（或兩者）是隨機變量。
在常見的實踐中，隨機化算法是使用近似的偽隨機數發生器代替隨機比特的真實來源的;這樣的實施可以從預期的理論行為偏離。
解問題P的隨機算法定義為：設I是問題P的一個實例，用算法解I的某些時刻，隨機選取
，由
b來決定算法的下一步動作。
優點：1、執行時間和空間，小於同一問題的已知最好的確定性算法；
2、實現比較簡單，容易理解；
三要素：輸入實例、隨機源和停止準則。
隨機算法背景及歷史
隨機算法重要方法
Monte Carlo求定積分法
隨機K-選擇法
隨機快排序
素性判定的隨機算法
二階段隨機路由算法
隨機算法重要人物和工作
de Leeuw等人提出了概率圖靈機（1955）
John Gill的隨機算法複雜性理論（1977）
Rabin的數論和計算幾何領域的工作（1976）
Karp的算法概率分析方法（1985）
隨機算法類型分類
1、數值概率算法：用於數值問題的求解。所得到的解幾乎都是近似解，近似解的精度
隨着計算時間的增加而不斷地提高。
2、拉斯維加斯算法（LasVegas）：要麼給出問題的正確答案，要麼得不到答案。反覆求解多次，可
使失效的概率任意小。
3、蒙特卡羅算法（MonteCarlo）：總能得到問題的答案，偶然產生不正確的答案。重複運行，每一次
都進行隨機選擇，可使不正確答案的概率變得任意小。
4、舍伍德算法（Sherwood）：很多具有很好的平均運行時間的確定性算法，在最壞的情況下性能很
隨機算法時間複雜性
衡量確定性算法的時間複雜性，是取它的平均運行時間。
衡量隨機算法的時間複雜性，是對確定實例I的期望運行時間，即反覆地運行實例I，所取的平均運行時間。
隨機算法設計方法
1、挫敗對手（Foiling the Adversary）
將不同的算法組成算法羣，根據輸入實例的不同隨機地或有選擇地選取不同的算法，以使性能達到最佳。
2、隨機採樣（Random Sampling）
用“小”樣本羣的信息，指導整體的求解。
3、隨機搜索（Random Search）
是一種簡單易行的方法，可以從統計角度分析算法的平均性能，如果將搜索限制在有解或有較多解的區域，可以大大提到搜索的成功概率。
4、指紋技術（Fingerprinting）
利用指紋信息可以大大減少對象識別的工作量。通過隨機映射的取值方法，Karp和Rabin得到了一個快速的串匹配隨即算法。
5、輸入隨機重組（Input Randomization）
對輸入實例進行隨機重組後，可以改進算法的平均性能。
6、負載平衡（Load Balancing）
在並行與分佈計算、網絡通訊等問題中，使用隨機選擇技術可以達到任務的負載平衡和網絡通訊的平衡。
7、快速混合Markov鏈（Rapidly Mixing Markov Chain）
使用該方法可以解決大空間中的均勻抽樣問題。
8、孤立和破對稱技術（Isolation and Symmetry Breaking）
使用該技術可以解決處理的並行性，避免分佈式系統的死鎖等問題。如：
圖着色算法，部分獨立集問題。
9、概率存在性證明（Probabilistic Methods and Existence Proofs）
如果隨機選取的物體具有某種特性的概率大於0，則具有該特性的物體一定存在。
10、消除隨機性（Derandomization）
隨機算法隨機算法舉例
隨機算法Quick Sort
（1）傳統的快排序算法
總是取第一個元素作為劃分元；
算法的最壞運行時間是O(
)，平均時間是O(
);
因此存在一些輸入實例，使得算法達到最壞運行時間
如：降序的序列；
（2）隨即快排序算法
隨機選擇一個元素作為劃分元；
任何一個輸入的期望時間是O（
）；
這是一個Las Vegas算法；
隨機算法Min Cut
（1）最小截問題定義：
給定一個無向圖G(V,E),找一個截（V1,V2）使得V1和V2間的連邊數最小。
（2）該問題可以用確定性算法（max-flow min-cut algorithm）在O(
)時間內完成。
（3）隨機算法
隨機選一條邊，將兩頂點合一併除去頂點上的環；
直到圖中只剩下兩個頂點；
返回剩下兩頂點建德連邊數；
（4）示例：#cut=2
最小截問題示例
（5）出錯概率
重複K次出錯概率為
