隨機算法是一個概念圖靈機，也就是在算法中引入隨機因素，即通過隨機數選擇算法的下一步操作。
基本介紹
- 中文名：隨即算法
- 外文名：randomized algorithm
基本概念,背景及歷史,重要方法,重要人物和工作,類型分類,時間複雜性,隨即算法的設計方法,隨機算法舉例,Quick Sort,Min Cut,
基本概念
一個隨機算法是一種算法，它採用了一定程度的隨機性作為其邏輯的一部分。該算法通常使用均勻隨機位作為輔助輸入來指導自己的行為，超過隨機位的所有可能的選擇實現了“平均情況下的”良好業績的希望。從形式上看，該算法的性能將會是一個隨機變數，由隨機位決定;因此無論是運行時間，或輸出（或兩者）是隨機變數。
在常見的實踐中，隨機化算法是使用近似的偽隨機數發生器代替隨機比特的真實來源的;這樣的實施可以從預期的理論行為偏離。
解問題P的隨機算法定義為：設I是問題P的一個實例，用算法解I的某些時刻，隨機選取
，由
b來決定算法的下一步動作。
優點：1、執行時間和空間，小於同一問題的已知最好的確定性算法；
2、實現比較簡單，容易理解；
三要素：輸入實例、隨機源和停止準則。
一種平衡：隨機算法可以理解為在時間、空間和隨機三大計算資源中的平衡。
背景及歷史
重要方法
Monte Carlo求定積分法
隨機K-選擇法
隨機快排序
素性判定的隨機算法
二階段隨機路由算法
重要人物和工作
de Leeuw等人提出了機率圖靈機（1955）
John Gill的隨機算法複雜性理論（1977）
Karp的算法機率分析方法（1985）
Shor的素因子分解量子算法（1994）
類型分類
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次出錯機率為
(6)本算法是一個Monte Carlo型算法
