概率算法也叫隨機化算法。概率算法允許算法在執行過程中隨機地選擇下一個計算步驟。在很多情況下，算法在執行過程中面臨選擇時，隨機性選擇比最優選擇省時，因此概率算法可以在很大程度上降低算法的復雜度。概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。

概率算法大致分為四類：

數值概率算法

蒙特卡羅（Monte Carlo）算法

拉斯維加斯（Las Vegas）算法

舍伍德（Sherwood）算法

基本特征

隨機決策。

在同一實例上執行兩次其結果可能不同。

在同一實例上執行兩次的時間亦可能不太相同。

特點

不可再現性：在同一個輸入實例上，每次執行結果不盡相同，例如N-皇后問題，概率算法運行不同次將會找到不同的正確解；找一給定合數的非平凡因子， 每次運行的結果不盡相同，但確定算法每次運行結果必定相同

分析困難：要求有概率論，統計學和數論的知識。

大致分類（四類）

概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。
數值概率算法
數值概率算法常用于數值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數值概率算法可得到相當滿意的解。

蒙特卡羅算法
蒙特卡羅算法用于求問題的準確解。蒙特卡洛算法1945年由馮諾依曼行核武模擬提出的。它是以概率和統計的理論與方法為基礎的一種數值計算方法，它是雙重近似：
1 . 用概率模型模擬近似的數值計算；
2 . 用偽隨機數模擬真正的隨機變量的樣本。
對于許多問題來說，近似解毫無意義。例如，一個判定問題其解為“是”或“否”，二者必居其一，不存在任何近似解答。又如，我們要求一個整數的因子時所給出的解答必須是準確的，一個整數的近似因子沒有任何意義。用蒙特卡羅算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴于算法所用的時間。算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅算法的主要缺點就在于此。一般情況下，無法有效判斷得到的解是否肯定正確。

拉斯維加斯算法
拉斯維加斯算法不會得到不正確的解，一旦用拉斯維加斯算法找到一個解，那么這個解肯定是正確的。但是有時候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似。拉斯維加斯算法得到正確解的概率隨著它用的計算時間的增加而提高。對于所求解問題的任一實例，用同一拉斯維加斯算法反復對該實例求解足夠多次，可使求解失效的概率任意小。

舍伍德算法
舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關聯性。

總結

以上是生活随笔為你收集整理的概率算法（随机化算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。