 |
 |
 |
| 24小時(shí)熱門(mén)版塊排行榜 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 1 | 1/1 | 返回列表 |
| 查看: 1057 | 回復(fù): 0 | |||
[交流]
【轉(zhuǎn)帖】概率算法簡(jiǎn)介
|
|
很多算法的每一個(gè)計(jì)算步驟都是固定的，而在下面我們要討論的概率算法，允許算法在執(zhí)行的過(guò)程中隨機(jī)選擇下一個(gè)計(jì)算步驟。許多情況下，當(dāng)算法在執(zhí)行過(guò)程中面臨一個(gè)選擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇省時(shí)。因此概率算法可在很大程度上降低算法的復(fù)雜度。 概率算法的一個(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)確解。對(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)性。 本文簡(jiǎn)要的介紹一下數(shù)值概率算法和舍伍德算法。 首先來(lái)談?wù)勲S機(jī)數(shù)。隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。 產(chǎn)生隨機(jī)數(shù)最常用的方法是線性同余法。由線性同余法產(chǎn)生的隨機(jī)序列a1,a2,...,an滿足 a0=d an=(ban-1+c)mod m n=1,2....... 其中,b>=0, c>=0, d>=m。d稱為該隨機(jī)序列的種子。 下面我們建立一個(gè)隨機(jī)數(shù)類RadomNumber，該類包含一個(gè)由用戶初始化的種子randSeed。給定種子之后，既可產(chǎn)生與之相應(yīng)的隨機(jī)數(shù)序列。randseed是一個(gè)無(wú)符號(hào)長(zhǎng)整型數(shù)，既可由用戶指定也可由系統(tǒng)時(shí)間自動(dòng)產(chǎn)生。 const unsigned long maxshort=65536L; const unsigned long multiplier=1194211693L; const unsigned long adder=12345L; class RandomNumber { private: //當(dāng)前種子 unsigned long randseed; public: //構(gòu)造函數(shù)，缺省值0表示由系統(tǒng)自動(dòng)產(chǎn)生種子 RandomNumber(unsigned long s=0); //產(chǎn)生0-n-1之間的隨機(jī)整數(shù) unsigned short Random(unsigned long n); //產(chǎn)生[0，1)之間的隨機(jī)實(shí)數(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在每次計(jì)算時(shí)，用線性同余式計(jì)算新的種子。它的高16位的隨機(jī)性較好，將randseed右移16位得到一個(gè)0-65535之間的隨機(jī)整數(shù)然后再將此隨機(jī)整數(shù)映射到0-n-1范圍內(nèi)。 對(duì)于函數(shù)fRandom,先用Random(maxshort)產(chǎn)生一個(gè)0-(maxshort-1之間的整型隨機(jī)序列)，將每個(gè)整型隨機(jī)數(shù)除以maxshort，就得到[0，1）區(qū)間中的隨機(jī)實(shí)數(shù)。 下面來(lái)看看數(shù)值概率算法的兩個(gè)例子： 1.用隨機(jī)投點(diǎn)法計(jì)算π 設(shè)有一半徑為r的圓及其外切四邊形，如圖所示。向該正方形隨機(jī)投擲n個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)在正方形上均勻分布，因而所投入點(diǎn)落入圓內(nèi)的概率為πr^2/4r^2，所以當(dāng)n足夠大時(shí)，k與n之比就逼近這一概率，即π/4。由此可得使用隨機(jī)投點(diǎn)法計(jì)算π值的數(shù)值概率算法。具體實(shí)現(xiàn)時(shí)，只需要在第一次象限計(jì)算即可。 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); } 再簡(jiǎn)單舉個(gè)舍伍德算法的例子。 我們?cè)诜治鲆粋�(gè)算法在平均情況下的計(jì)算復(fù)雜性時(shí)，通常假定算法的輸入數(shù)據(jù)服從某一特定的概率分布。例如，在輸入數(shù)據(jù)是均勻分布時(shí)，快速排序算法所需的平均時(shí)間是O(n logn)。但是如果其輸入已經(jīng)基本上排好序時(shí)，所用時(shí)間就大大增加了。此時(shí)，可采用舍伍德算法消除算法所需計(jì)算時(shí)間與輸入實(shí)例間的這種聯(lián)系。 在這里，我們用舍伍德型選擇算法隨機(jī)的選擇一個(gè)數(shù)組元素作為劃分標(biāo)準(zhǔn)。這樣既能保證算法的線性時(shí)間平均性能又避免了計(jì)算擬中位數(shù)的麻煩。非遞歸的舍伍德型算法可描述如下： template 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, a[j]); j=r+1; Type pivot=a[l]; while(true) { while(a[++i] if(i>=j) break; Swap(a, a[j]); } if(j-l+1==k) return pivot; a[l]=a[j]; a[j]=pivot; if(j-l+1 k=k-j+l-1; l=j+1; } else r=j-1; } } template Type Select(Type a[], int n, int k) { if(k<1||k>n) throw OutOfBounds(); return select(a, 0, n-1, k); } 平時(shí)我們一般開(kāi)始考慮的是一個(gè)有著很好平均性能的選擇算法，但在最壞情況下對(duì)某些實(shí)例算法效率較低。這時(shí)候我們用概率算法，將上述算法改造成一個(gè)舍伍德型算法，使得該算法對(duì)任何實(shí)例均有效。 不過(guò)在有些情況下，所給的確定性算法無(wú)法直接改造成舍伍德型算法。這時(shí)候就可以借助隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，同樣可以得到舍伍德算法的效果。還是剛才的例子，換一種方法實(shí)現(xiàn)： template void Shuffle(Type a[], int n) { static RandomNumber rnd; for(int i=1;i Swap(a, a[j]); } } 在上文里，我們對(duì)概率算法中的數(shù)值概率算法以及舍伍德算法舉例作了簡(jiǎn)要的介紹，希望能使大家對(duì)概率算法有一個(gè)初步的認(rèn)識(shí)，并且將這種思想運(yùn)用到自己平時(shí)的編程中。 本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/byxdaz/archive/2006/03/18/628403.aspx [ Last edited by zyj8119 on 2010-9-10 at 08:14 ] |
回復(fù)此樓» 猜你喜歡
一志愿中國(guó)海洋大學(xué)，生物學(xué)，301分，求調(diào)劑
已經(jīng)有6人回復(fù)
-
081700化工學(xué)碩調(diào)劑
已經(jīng)有3人回復(fù)
-
材料學(xué)碩318求調(diào)劑
已經(jīng)有4人回復(fù)
-
329求調(diào)劑
已經(jīng)有4人回復(fù)
-
一志愿吉林大學(xué)材料學(xué)碩321求調(diào)劑
已經(jīng)有11人回復(fù)
-
一志愿蘇州大學(xué)材料求調(diào)劑，總分315（英一）
已經(jīng)有3人回復(fù)
-
0703化學(xué)調(diào)劑
已經(jīng)有14人回復(fù)
-
320求調(diào)劑0856
已經(jīng)有3人回復(fù)
-
307求調(diào)劑
已經(jīng)有9人回復(fù)
-
288求調(diào)劑
已經(jīng)有15人回復(fù)
找到一些相關(guān)的精華帖子，希望有用哦~
獨(dú)立重復(fù)事件重復(fù)x次的概率算法
已經(jīng)有5人回復(fù)
- 求解“通過(guò)在一定的時(shí)間間隔t內(nèi)率r估計(jì)概率p的計(jì)算公式P=1-e（-r*t）”的具體算法
已經(jīng)有1人回復(fù)
- 【轉(zhuǎn)帖】蒙特卡羅算法計(jì)算圓周率
已經(jīng)有12人回復(fù)
- 【求助】生物柴油轉(zhuǎn)化率 有標(biāo)準(zhǔn)算法沒(méi)
已經(jīng)有8人回復(fù)
- 【討論】大家討論一下概率和統(tǒng)計(jì)的經(jīng)典教材吧！
已經(jīng)有24人回復(fù)
點(diǎn)擊這里搜索更多相關(guān)資源科研從小木蟲(chóng)開(kāi)始，人人為我，我為人人
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 zyj8119 的主題更新
| 1 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
