中國數(shù)學(xué)建模-編程交流-概率算法簡介

ID:21831754

大?。?1.00 KB

頁數(shù):9頁

時(shí)間:2018-10-25

中國數(shù)學(xué)建模-編程交流-概率算法簡介_第1頁
中國數(shù)學(xué)建模-編程交流-概率算法簡介_第2頁
中國數(shù)學(xué)建模-編程交流-概率算法簡介_第3頁
中國數(shù)學(xué)建模-編程交流-概率算法簡介_第4頁
中國數(shù)學(xué)建模-編程交流-概率算法簡介_第5頁
資源描述:

《中國數(shù)學(xué)建模-編程交流-概率算法簡介》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、中國數(shù)學(xué)建模-編程交流-概率算法簡介.txt﹃根網(wǎng)線''盡賺了多少人的青春い有時(shí)候感動(dòng)的就是身邊微不足道的小事。﹎破碎不是最殘酷的最殘酷的是踩著這些碎片卻假裝不疼痛固執(zhí)的尋找﹎將來就算我遇見再怎么完美的人,都有一個(gè)缺點(diǎn),他不是你,_____下輩子要做男生,娶一個(gè)像我這樣的女生。中國數(shù)學(xué)建模-編程交流-概率算法簡介├數(shù)學(xué)思想├編程交流├學(xué)術(shù)雜談├EnglishFans登錄注冊搜索風(fēng)格論壇狀態(tài)論壇展區(qū)社區(qū)服務(wù)社區(qū)休閑網(wǎng)站首頁我能做什么>>VC++,C,Perl,Asp...編程學(xué)習(xí),算法介紹.中國數(shù)學(xué)建?!鷮W(xué)術(shù)區(qū)→編程交流→概率算法簡介您是本帖的第10

2、10個(gè)閱讀者*貼子主題:概率算法簡介b等級:職業(yè)俠客文章:470積分:956門派:黑客帝國注冊:2003-8-28鮮花(0)雞蛋(0)樓主概率算法簡介很多算法的每一個(gè)計(jì)算步驟都是固定的,而在下面我們要討論的概率算法,允許算法在執(zhí)行的過程中隨機(jī)選擇下一個(gè)計(jì)算步驟。許多情況下,當(dāng)算法在執(zhí)行過程中面臨一個(gè)選擇時(shí),隨機(jī)性選擇常比最優(yōu)選擇省時(shí)。因此概率算法可在很大程度上降低算法的復(fù)雜度。概率算法的一個(gè)基本特征是對所求解問題的同一實(shí)例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時(shí)間甚至所得到的結(jié)果可能會(huì)有相當(dāng)大的差別。一般情況下,可將

3、概率算法大致分為四類:數(shù)值概率算法,蒙特卡羅(MonteCarlo)算法,拉斯維加斯(LasVegas)算法和舍伍德(Sherwood)算法。數(shù)值概率算法常用于數(shù)值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計(jì)算時(shí)間的增加不斷提高。在許多情況下,要計(jì)算出問題的精確解是不可能或沒有必要的,因此用數(shù)值概率算法可得到相當(dāng)滿意的解。蒙特卡羅算法用于求問題的準(zhǔn)確解。對于許多問題來說,近似解毫無意義。例如,一個(gè)判定問題其解為“是”或“否”,二者必居其一,不存在任何近似解答。又如,我們要求一個(gè)整數(shù)的因子時(shí)所給出的解答必須是準(zhǔn)確的,一個(gè)整數(shù)的近似因

4、子沒有任何意義。用蒙特卡羅算法能求得問題的一個(gè)解,但這個(gè)解未必是正確的。求得正確解的概率依賴于算法所用的時(shí)間。算法所用的時(shí)間越多,得到正確解的概率就越高。蒙特卡羅算法的主要缺點(diǎn)就在于此。一般情況下,無法有效判斷得到的解是否肯定正確。拉斯維加斯算法不會(huì)得到不正確的解,一旦用拉斯維加斯算法找到一個(gè)解,那么這個(gè)解肯定是正確的。但是有時(shí)候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似。拉斯維加斯算法得到正確解的概率隨著它用的計(jì)算時(shí)間的增加而提高。對于所求解問題的任一實(shí)例,用同一拉斯維加斯算法反復(fù)對該實(shí)例求解足夠多次,可使求解失效的概率任意小。舍伍德算法總

5、能求得問題的一個(gè)解,且所求得的解總是正確的。當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差別時(shí),可以在這個(gè)確定算法中引入隨機(jī)性將它改造成一個(gè)舍伍德算法,消除或減少問題的好壞實(shí)例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為,而是設(shè)法消除這種最壞行為與特定實(shí)例之間的關(guān)聯(lián)性。本文簡要的介紹一下數(shù)值概率算法和舍伍德算法。首先來談?wù)勲S機(jī)數(shù)。隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù),因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的,即偽隨機(jī)數(shù)。產(chǎn)生隨機(jī)數(shù)最常用的方法是線性同余法。由線

6、性同余法產(chǎn)生的隨機(jī)序列a1,a2,...,an滿足a0=dan=(ban-1+c)modmn=1,2.......其中,b>=0,c>=0,d>=m。d稱為該隨機(jī)序列的種子。下面我們建立一個(gè)隨機(jī)數(shù)類RadomNumber,該類包含一個(gè)由用戶初始化的種子randSeed。給定種子之后,既可產(chǎn)生與之相應(yīng)的隨機(jī)數(shù)序列。randseed是一個(gè)無符號長整型數(shù),既可由用戶指定也可由系統(tǒng)時(shí)間自動(dòng)產(chǎn)生。constunsignedlongmaxshort=65536L;constunsignedlongmultiplier=1194211693L;constunsi

7、gnedlongadder=12345L;classRandomNumber{private://當(dāng)前種子unsignedlongrandseed;public://構(gòu)造函數(shù),缺省值0表示由系統(tǒng)自動(dòng)產(chǎn)生種子RandomNumber(unsignedlongs=0);//產(chǎn)生0-n-1之間的隨機(jī)整數(shù)unsignedshortRandom(unsignedlongn);//產(chǎn)生[0,1)之間的隨機(jī)實(shí)數(shù)doublefRandom(void);};RandomNumber::RandomNumber(unsignedlongs){if(s==0)rands

8、eed=time(0);elserandseed=s;}unsignedshortRandomNumber::Random

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時(shí)聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭