随機化算法

百科的介紹：

随機化算法（randomized algorithm），是這樣一種算法，在算法中使用了随機函數，且随機函數的傳回值直接或者間接的影響了算法的執行流程或執行結果。就是将算法的某一步或某幾步置于運氣的控制之下，即該算法在運作的過程中的某一步或某幾步涉及一個随機決策，或者說其中的一個決策依賴于某種随機事件。

算法課本：

在許多情況下，當算法在執行過程中面臨一個選擇時，随機化選擇常比最優選擇省事。是以随機化算法在很大程度上降低算法的複雜度。随機化算法的一個基本特征是對所求問題的同一執行個體用同一随機化算法求解兩次可能得到完全不同的效果。不僅是結果，甚至是時間都有可能相差很大。一般情況下，将随機化算法大緻分為四類：

• 數值随機化算法
• 蒙特卡羅算法
• 拉斯維加斯算法
• 舍伍德算法

數值化随機算法常用于數值問題求解。這類算法得到的往往是近似解，且近似解的精度随着計算時間的增加而不斷提高。在許多情況下，要計算出問題的精确解是不可能的或沒有必要的，用數值化稅基算法可得到相當滿意的解。

數值類問題常用，多見于MATLAB , 各種積分微分，數學計算中。

蒙特卡羅算法用于求問題的準确解。對許多問題，近似解是毫無意義的。用蒙特卡羅算法能求得問題的一個解，但這個解未必是正确的。其求得正确解的機率依賴算法所用的時間。算法所用時間越多，得到正确解的機率就越高。蒙特卡羅算法的主要缺點也在于此。一般情況下，無法有效的判斷所得到的解是否可定正确。（非一般情況是可以判定的！）

設p為實數，且1/2<p<1。如果一個蒙特卡羅算法對于問題的任一執行個體得到正确解的機率不小于p，則稱該蒙特卡羅算法是p正确的，且稱p-1/2是該算法的優勢。按照這種情況，隻要執行次數足夠多，則可以得到正确解。不過當p小于1/2的時候就無能為力了。不過大多數蒙特卡羅算法經重複調用之後正确率快速上升。

拉斯維加斯算法不會得到不正确的解。一旦用拉斯維加斯算法找到一個解，這個解就一定是正确解。但有時用拉斯維加斯算法會找不到解。拉斯維加斯算法找到正确解的機率會随着它所用的計算時間的增加而提高。位于所求解問題的任一執行個體，用同一拉斯維加斯算法反複随該執行個體求解足夠多次，可使解失效的機率任一小。

它可以顯著地改進算法的有效性，甚至對某些迄今為止找不到有效算法的問題，也能得到滿意的結果。n皇後問題利用此算法可以有效的解決，算法的思路是每次放置保證不跟已經放入的起沖突即可，直到無法放入或者皇後已經放完為止。

舍伍德算法總能求得問題的一個解，而且所得的解總是正确的。當一個确定性算法在最壞情況下的計算複雜性與其平均情況下的計算複雜性有較大差别時，可在這個确定性算法中引入随機性将它改造成一個舍伍德算法，消除或減少問題的好壞執行個體間的這種差别。舍伍德算法的精髓不是避免算法的最壞情形，而是設法消除這種最壞情形行為與特定執行個體之間的關聯性。當出現這種情況時，在算法中增加随機性處理，隻要随機性處理和目前确定性算法時間相比遠低于它的時間複雜度數量級就可以。快速排序就是它的一個執行個體。舍伍德算法并不能改變算法的時間複雜度，但算法的時間複雜性相對均勻。

基于舍伍德算法的設計思想還可以設計高效的資料結構，跳躍表就是其中一例。具體跳躍表的執行個體可以從網上搜尋。私下在閱讀相關資料的時候，覺得跳躍表的執行個體應該可以在資料庫的索引設計底層中出現，它是一種犧牲空間增加跳躍索引換取查詢速度的，查詢算法的效率可以參考快速排序，不過增加和删除的效率有點低。