0.概論

包括四種算法，數(shù)值概率算法（數(shù)值問題的求解，最優(yōu)化問題的近似解）、蒙特羅卡算法（判定問題的準(zhǔn)確解，不一定正確）、拉斯維加斯算法（不一定會得到解，但得到的解一定是正確解）、舍伍德算法（總能求得一個解，且一定是正確解）。

1.隨機(jī)數(shù)

隨機(jī)數(shù)生成，線性同余法

d 為用戶輸入隨機(jī)數(shù)；m 足夠大，一般為最大機(jī)器數(shù)；b為一質(zhì)數(shù)；c>=0

2.舍伍德算法（對輸入進(jìn)行處理，使得計算時間復(fù)雜度對所有實例相對均勻）

這篇寫的很好：http://www.cnblogs.com/hxsyl/p/3219621.html

其實就是在確定性算法中引入隨機(jī)性。其優(yōu)點是其計算時間復(fù)雜性對所有實例而言相對均勻，但與其相應(yīng)的確定性算法相比，其平均時間復(fù)雜度沒有改進(jìn)。

如一般快速排序都是以第一個元素作為基準(zhǔn)元素，而舍伍德版的快速排序是隨機(jī)選擇一個元素作為基準(zhǔn)元素（代碼見章二分治學(xué)習(xí)記錄）。那么當(dāng)一個確定性算法無法直接改造成舍伍德版本的時候，就可以對輸入進(jìn)行洗牌。以下是洗牌算法（O( n )）。

#include<iostream> #include<algorithm> #include<cstdlib> #include<vector> using namespace std; int random(int e) {return rand()%e; } template <class T> void shuffle(vector<T> &x) {int num=x.size();for(int i=0;i<num;i++){int j=random(num-i)+i;//產(chǎn)生一個大于i的數(shù) swap(x[i],x[j]);} }概率算法的一個特點是對同一實例多次運用同一概率算法結(jié)果可能不同。舍伍德算法總能求的問題的一個正確解，當(dāng)一個確定性算法在最壞情況和平均情況下差別較大時可在這個確定性算法中引入隨機(jī)性將之改造成一個舍伍德算法；引入隨機(jī)性不是為了消除最壞，而是為了減少最壞和特定實例的關(guān)聯(lián)性。

跳躍表

有序鏈表S，搜索其中一個元素需要花費線性時間。為提高搜索效率，可以在部分節(jié)點上增設(shè)附加指針，這種向前附加指針的有序鏈表稱為跳躍表

完全跳躍表，如(c)所示，每個k級節(jié)點都有k+1個指針，分別跳過2^k-1，2^(k-1)-1，...，2^0-1個中間結(jié)點，完全跳躍表與完全二叉樹一樣，插入和刪除會破壞它的平衡性，用舍伍德隨機(jī)的思想，在插入節(jié)點上以概率1/2引入1級指針，概率1/4引入2級指針，....

3.我們把隨機(jī)算法分成兩類：

• • 蒙特卡羅算法：采樣越多，越近似最優(yōu)解；
  • 拉斯維加斯算法：采樣越多，越有機(jī)會找到最優(yōu)解；
  • 這兩類隨機(jī)算法之間的選擇，往往受到問題的局限。如果問題要求在有限采樣內(nèi)，必須給出一個解，但不要求是最優(yōu)解，那就要用蒙特卡羅算法。反之，如果問題要求必須給出最優(yōu)解，但對采樣沒有限制，那就要用拉斯維加斯算法。對于機(jī)器圍棋程序而言，因為每一步棋的運算時間、堆棧空間都是有限的，而且不要求最優(yōu)解，所以ZEN涉及的隨機(jī)算法，肯定是蒙特卡羅式的。
    

4.拉斯維加斯算法

而拉斯維加斯算法，則是另一種情況。假如有一把鎖，給我100把鑰匙，只有1把是對的。于是我每次隨機(jī)拿1把鑰匙去試，打不開就再換1把。我試的次數(shù)越多，打開（最優(yōu)解）的機(jī)會就越大，但在打開之前，那些錯的鑰匙都是沒有用的。這個試鑰匙的算法，就是拉斯維加斯的——盡量找最好的，但不保證能找到。

拉斯維加斯算法的一個顯著的特征是：它所做的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。拉斯維加斯算法不一定能夠得到解，但如果得到了，那一定是正確解

nQueen拉斯維加斯+回溯

#include<iostream> #include<vector> #include<cmath> #include<cstdlib> using namespace std;vector<int> x;//臨時存放，x[i]=j表示在第i行，第j列放置皇后 vector<int> y;//最終數(shù)組 bool flag=true; int random(int n) {return rand()%n; } bool place(int k) {for(int i=0;i<k;i++){if(abs(x[i]-x[k])==abs(i-k)||x[k]==x[i]){return false;}}return true; } void backtrack(int k) {if(k>=x.size()){flag=false;for(int i=0;i<x.size();i++){y[i]=x[i];cout<<x[i]<<"\t";}cout<<endl;return;}else{for(int i=0;i<x.size();i++){x[k]=i;if(place(k)){backtrack(k+1);}}} } bool queenLV(int num)//num之前用拉斯維加斯 {int k=0;int count=1; while((k<num)&&(count>0)){count=0;vector<int> y1;//保存可用列 for(int i=0;i<=num;i++){x[k]=i;if(place(k))//可以放置 {y1.push_back(i);count++;}}if(count>0)//可用列個數(shù)大于0 {int j=random(count);x[k++]=y1[j];//隨機(jī)選擇一個可用列 }}return count>0; } void nQueen(int num,int xxx) {for(int i=0;i<num;i++){x.push_back(-1);y.push_back(-1);} while(!queenLV(xxx)){cout<<"GAN!"<<endl;} backtrack(xxx); } int main() {int num;int xxx;cin>>num>>xxx;nQueen(num,xxx); }不一定能產(chǎn)生解吧。如queenLV產(chǎn)生（1，5，2，6，3，0，4）時符合要求，這時每列都被占，backtrack只能選擇列7，但是| 7 - 2 |==| x[ 7 ] - x[ 2 ] |。

一種確定性算法，在應(yīng)用了像這樣隨機(jī)放解（random assignment）的情況，就稱為應(yīng)用了拉斯維加斯思想。如0-1背包問題，物品i可放，可不放，通過random(0,1)來決定此物品的存放與否。

5.蒙特卡羅算法

寫的很好：http://www.zhihu.com/question/20254139?utm_campaign=rss&utm_medium=rss&utm_source=rss&utm_content=title

舉個例子，假如筐里有100個蘋果，讓我每次閉眼拿1個，挑出最大的。于是我隨機(jī)拿1個，再隨機(jī)拿1個跟它比，留下大的，再隨機(jī)拿1個……我每拿一次，留下的蘋果都至少不比上次的小。拿的次數(shù)越多，挑出的蘋果就越大，但我除非拿100次，否則無法肯定挑出了最大的。這個挑蘋果的算法，就屬于蒙特卡羅算法——盡量找好的，但不保證是最好的。

定義為：計算機(jī)模擬，從總體抽取大量隨機(jī)樣本的計算方法統(tǒng)稱為蒙特羅卡方法。

查了網(wǎng)上的例子，看著都像是數(shù)值概率算法的例子。構(gòu)造一個隨機(jī)分布（可以是離散的，連續(xù)的），是這個隨機(jī)分布的某些數(shù)字特征等于所求的東西，或通過中心極限定理，大數(shù)定理等是這些數(shù)字特征與所求的東西掛上鉤，然后通過數(shù)字特征求解出一個近似解來。與數(shù)值概率算法不同的是，蒙特羅卡考慮到了解的真假性，置信程度

A.數(shù)值概率算法

a.隨機(jī)投點法（以求定積分為例）

b.平均值法（以求定積分為例）

基本思想：構(gòu)造一個隨機(jī)變量分布使其期望（這樣就可以直接相加除以n了）等于問題所求的值、對這個概率分布進(jìn)行抽樣、用樣本的均值作為問題所求值的估計。

總結(jié)

以上是生活随笔為你收集整理的概率算法（算法分析与设计）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。