[科普中國(guó)]-概率算法

提出

1976年雷兵提出了概率算法，這種算法的新穎之處是把隨機(jī)性注入到算法中，使得算法設(shè)計(jì)與分析的靈活性及解決問(wèn)題的能力大為改觀，這種算法曾一度運(yùn)用在密碼學(xué)，數(shù)字信號(hào)，數(shù)字簡(jiǎn)化信號(hào)和大系統(tǒng)的安全及故障容差中得到應(yīng)用。

很多算法的每一個(gè)計(jì)算步驟都是固定的，而概率算法允許算法在執(zhí)行的過(guò)程中隨機(jī)選擇下一個(gè)計(jì)算步驟。許多情況下，當(dāng)算法在執(zhí)行過(guò)程中面臨一個(gè)選擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇省時(shí)。因此概率算法可在很大程度上降低算法的復(fù)雜度。

基本特征（1）隨機(jī)決策。

（2）在同一實(shí)例上執(zhí)行兩次其結(jié)果可能不同。

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

期望時(shí)間對(duì)概率算法可以討論如下兩種期望時(shí)間：

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

（2）最壞的期望時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)間。

特點(diǎn)（1）不可再現(xiàn)性：在同一個(gè)輸入實(shí)例上，每次執(zhí)行結(jié)果不盡相同，例如N-皇后問(wèn)題，概率算法運(yùn)行不同次將會(huì)找到不同的正確解；找一給定合數(shù)的非平凡因子， 每次運(yùn)行的結(jié)果不盡相同，但確定算法每次運(yùn)行結(jié)果必定相同

(2) 分析困難：要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的知識(shí)。

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

數(shù)值概率算法常用于數(shù)值問(wèn)題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計(jì)算時(shí)間的增加不斷提高。在許多情況下，要計(jì)算出問(wèn)題的精確解是不可能或沒(méi)有必要的，因此用數(shù)值概率算法可得到相當(dāng)滿意的解。

蒙特卡羅算法用于求問(wèn)題的準(zhǔn)確解。蒙特卡洛算法1945年由馮諾依曼行核武模擬提出的。它是以概率和統(tǒng)計(jì)的理論與方法為基礎(chǔ)的一種數(shù)值計(jì)算方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計(jì)算，二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。

對(duì)于許多問(wèn)題來(lái)說(shuō)，近似解毫無(wú)意義。例如，一個(gè)判定問(wèn)題其解為“是”或“否”，二者必居其一，不存在任何近似解答。又如，我們要求一個(gè)整數(shù)的因子時(shí)所給出的解答必須是準(zhǔn)確的，一個(gè)整數(shù)的近似因子沒(méi)有任何意義。用蒙特卡羅算法能求得問(wèn)題的一個(gè)解，但這個(gè)解未必是正確的。求得正確解的概率依賴于算法所用的時(shí)間。算法所用的時(shí)間越多，得到正確解的概率就越高。蒙特卡羅算法的主要缺點(diǎn)就在于此。一般情況下，無(wú)法有效判斷得到的解是否肯定正確。

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

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