概率算法簡介
很多算法的每一個計算步驟都是固定的，而在下面我們要討論的概率算法，允許算法在執(zhí)行的過程中隨機選擇下一個計算步驟。許多情況下，當算法在執(zhí)行過程中面臨一個選擇時，隨機性選擇常比最優(yōu)選擇省時。因此概率算法可在很大程度上降低算法的復雜度。
概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結(jié)果可能會有相當大的差別。一般情況下，可將概率算法大致分為四類:數(shù)值概率算法，蒙特卡羅（Monte
Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
數(shù)值概率算法常用于數(shù)值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數(shù)值概率算法可得到相當滿意的解。
蒙特卡羅算法用于求問題的準確解。對于許多問題來說，近似解毫無意義。例如，一個判定問題其解為“是”或“否”，二者必居其一，不存在任何近似解答。又如，我們要求一個整數(shù)的因子時所給出的解答必須是準確的，一個整數(shù)的近似因子沒有任何意義。用蒙特卡羅算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴于算法所用的時間。算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅算法的主要缺點就在于此。一般情況下，無法有效判斷得到的解是否肯定正確。
拉斯維加斯算法不會得到不正確的解，一旦用拉斯維加斯算法找到一個解，那么這個解肯定是正確的。但是有時候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似。拉斯維加斯算法得到正確解的概率隨著它用的計算時間的增加而提高。對于所求解問題的任一實例，用同一拉斯維加斯算法反復對該實例求解足夠多次，可使求解失效的概率任意小。
舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設(shè)法消除這種最壞行為與特定實例之間的關(guān)聯(lián)性。
本文簡要的介紹一下數(shù)值概率算法和舍伍德算法。
首先來談談隨機數(shù)。隨機數(shù)在概率算法設(shè)計中扮演著十分重要的角色。在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在概率算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)。
產(chǎn)生隨機數(shù)最常用的方法是線性同余法。由線性同余法產(chǎn)生的隨機序列a1,a2,...,an滿足
a0=d
an=(ban-1+c)mod m n=1,2.......
其中,b>=0, c>=0, d>=m。d稱為該隨機序列的種子。
下面我們建立一個隨機數(shù)類RadomNumber，該類包含一個由用戶初始化的種子randSeed。給定種子之后，既可產(chǎn)生與之相應的隨機數(shù)序列。randseed是一個無符號長整型數(shù)，既可由用戶指定也可由系統(tǒng)時間自動產(chǎn)生。
const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;
class RandomNumber
{
private:
//當前種子
unsigned long randseed;
public:
//構(gòu)造函數(shù)，缺省值0表示由系統(tǒng)自動產(chǎn)生種子
RandomNumber(unsigned long s=0);
//產(chǎn)生0-n-1之間的隨機整數(shù)
unsigned short Random(unsigned long n);
//產(chǎn)生[0，1)之間的隨機實數(shù)
double fRandom(void);
};
RandomNumber::RandomNumber(unsigned long s)
{
if(s==0)
randseed=time(0);
else
randseed=s;
}
unsigned short RandomNumber::Random(unsigned long n)
{
randseed=multiplier*randseed+adder;
return (unsigned short)((randseed>>16)%n);
}
double RandomNumber::fRandom(void)
{
return Random(maxshort)/double(maxshort);
}
函數(shù)Random在每次計算時，用線性同余式計算新的種子。它的高16位的隨機性較好，將randseed右移16位得到一個0-65535之間的隨機整數(shù)然后再將此隨機整數(shù)映射到0-n-1范圍內(nèi)。
對于函數(shù)fRandom,先用Random(maxshort)產(chǎn)生一個0-(maxshort-1之間的整型隨機序列)，將每個整型隨機數(shù)除以maxshort，就得到[0，1）區(qū)間中的隨機實數(shù)。
下面來看看數(shù)值概率算法的兩個例子：
1.用隨機投點法計算π
設(shè)有一半徑為r的圓及其外切四邊形，如圖所示。向該正方形隨機投擲n個點。設(shè)落入圓內(nèi)的點在正方形上均勻分布，因而所投入點落入圓內(nèi)的概率為πr^2/4r^2，所以當n足夠大時，k與n之比就逼近這一概率，即π/4。由此可得使用隨機投點法計算π值的數(shù)值概率算法。具體實現(xiàn)時，只需要在第一次象限計算即可。
double Darts(int n)
{
static RandomNumber dart;
int k=0;
for(int i=1;i<=n;i++){
double x=dart.fRandom();
double y=dart.fRandom();
if((x*x+y*y)<1)
k++;
}
return 4*k/double(n);
}
再簡單舉個舍伍德算法的例子。
我們在分析一個算法在平均情況下的計算復雜性時，通常假定算法的輸入數(shù)據(jù)服從某一特定的概率分布。例如，在輸入數(shù)據(jù)是均勻分布時，快速排序算法所需的平均時間是O(n
logn)。但是如果其輸入已經(jīng)基本上排好序時，所用時間就大大增加了。此時，可采用舍伍德算法消除算法所需計算時間與輸入實例間的這種聯(lián)系。
在這里，我們用舍伍德型選擇算法隨機的選擇一個數(shù)組元素作為劃分標準。這樣既能保證算法的線性時間平均性能又避免了計算擬中位數(shù)的麻煩。非遞歸的舍伍德型算法可描述如下：
template<class Type>
Type select(Type a[], int l, int r, int k)
{
static RandomNumber rnd;
while(true){
if(l>=r)
return a[l];
int i=l, j=l=rnd.Random(r-l+1);
Swap(a[i], a[j]);
j=r+1;
Type pivot=a[l];
while(true)
{
while(a[++i]<pivot);
while(a[--j]>pivot);
if(i>=j)
break;
Swap(a[i], a[j]);
}
if(j-l+1==k)
return pivot;
a[l]=a[j];
a[j]=pivot;
if(j-l+1<k)
{
k=k-j+l-1;
l=j+1;
}
else
r=j-1;
}
}
template <class Type>
Type Select(Type a[], int n, int k)
{
if(k<1||k>n)
throw OutOfBounds();
return select(a, 0, n-1, k);
}
平時我們一般開始考慮的是一個有著很好平均性能的選擇算法，但在最壞情況下對某些實例算法效率較低。這時候我們用概率算法，將上述算法改造成一個舍伍德型算法，使得該算法對任何實例均有效。
不過在有些情況下，所給的確定性算法無法直接改造成舍伍德型算法。這時候就可以借助隨機預處理技術(shù)，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可以得到舍伍德算法的效果。還是剛才的例子，換一種方法實現(xiàn)：
template<class Type>
void Shuffle(Type a[], int n)
{
static RandomNumber rnd;
for(int i=1;i<n;i++){
int j=rnd.Random(n-i)+i;
Swap(a[i], a[j]);
}
}
在上文里，我們對概率算法中的數(shù)值概率算法以及舍伍德算法舉例作了簡要的介紹，希望能使大家對概率算法有一個初步的認識，并且將這種思想運用到自己平時的編程中。
----------------------------------------------
