概率算法

1976年雷兵提出了概率算法，這種算法的新穎之處是把隨機性注入到算法中，使得算法設計與分析的靈活性及解決問題的能力大為改觀，這種算法曾一度運用在密碼學，數字信號，數字簡化信號和大系統的安全及故障容差中得到應用。

很多算法的每一個計算步驟都是固定的，而概率算法允許算法在執行的過程中隨機選擇下一個計算步驟。許多情況下，當算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率算法可在很大程度上降低算法的複雜度。

（1）隨機決策。

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

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

對概率算法可以討論如下兩種期望時間：

（1）平均的期望時間：所有輸入實例上平均的期望執行時間。

（2）最壞的期望時間：最壞的輸入實例上的期望執行時間。

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

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

概率算法的一個基本特徵是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下，可將概率算法大致分為四類：數值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法。

數值概率算法常用於數值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數值概率算法可得到相當滿意的解。

蒙特卡羅算法用於求問題的準確解。蒙特卡洛算法1945年由馮諾依曼行核武模擬提出的。它是以概率和統計的理論與方法為基礎的一種數值計算方法，它是雙重近似：一是用概率模型模擬近似的數值計算，二是用偽隨機數模擬真正的隨機變量的樣本。

對於許多問題來説，近似解毫無意義。例如，一個判定問題其解為“是”或“否”，二者必居其一，不存在任何近似解答。又如，我們要求一個整數的因子時所給出的解答必須是準確的，一個整數的近似因子沒有任何意義。用蒙特卡羅算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴於算法所用的時間。算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅算法的主要缺點就在於此。一般情況下，無法有效判斷得到的解是否肯定正確。

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

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