概率算法ppt課件(已修改)
2025-05-13 02:28 本頁(yè)面
【正文】 1 第 7章 概率算法 2 隨機(jī)數(shù) 隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。 線性同余法 是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機(jī)序列 a0,a1,…,a n滿足 ???????? ?,2,1m o d)( 10nmcbaadann其中 b?0， c?0， d?m。 d稱為該隨機(jī)序列的種子。如何選取該方法中的常數(shù) b、 c和 m直接關(guān)系到所產(chǎn)生的隨機(jī)序列的隨機(jī)性能。這是隨機(jī)性理論研究的內(nèi)容，已超出本書討論的范圍。從直觀上看， m應(yīng)取得充分大，因此可取 m為機(jī)器大數(shù)，另外應(yīng)取 gcd(m,b)=1，因此可取 b為一素?cái)?shù)。 3 數(shù)值概率算法 4 用隨機(jī)投點(diǎn)法計(jì)算 ?值 設(shè)有一半徑為 r的圓及其外切四邊形。向該正方形隨機(jī)地投擲 n個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為 k。由于所投入的點(diǎn)在正方形上均勻分布，因而所投入的點(diǎn)落入圓內(nèi)的概率為 。所以當(dāng) n足夠大 時(shí)， k與 n之比就逼近這一概率。從而 。 44 22 ?? ?rrnk4??public static double darts(int n) { // 用隨機(jī)投點(diǎn)法計(jì)算 ?值 int k=0。 for (int i=1。i =n。i++) { double x=()。 double y=()。 if ((x*x+y*y)=1) k++。 } return 4*k/(double)n。 } 5 計(jì)算定積分 設(shè) f(x)是 [0， 1]上的連續(xù)函數(shù)，且 0?f(x)?1。 需要計(jì)算的積分為 ,積分 I等于圖中的面積 G。 ??10)( dxxfI在圖所示單位正方形內(nèi)均勻地作投點(diǎn)試驗(yàn)，則隨機(jī)點(diǎn)落在曲線下面的概率為 假設(shè)向單位正方形內(nèi)隨機(jī)地投入 n個(gè)點(diǎn) (xi,yi)。如果有 m個(gè)點(diǎn)落入 G內(nèi)，則隨機(jī)點(diǎn)落入 G內(nèi)的概率 ? ? ???? 10)(010)()}({xfr dxxfd y d xxfyPnm?I6 解非線性方程組 求解下面的非線性方程組 ??????????0),(0),(0),(21212211nnnnxxxfxxxfxxxf???????????其中， x1,x2,…,x n是實(shí)變量， fi是未知量 x1,x2,…,x n的非線性實(shí)函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解 **2*1 , nxxx ? 在指定求根區(qū)域 D內(nèi)，選定一個(gè)隨機(jī)點(diǎn) x0作為隨機(jī)搜索的出發(fā)點(diǎn)。在算法的搜索過程中，假設(shè)第 j步隨機(jī)搜索得到的隨機(jī)搜索點(diǎn)為 xj。在第 j+1步，計(jì)算出下一步的隨機(jī)搜索增量 ?xj。從當(dāng)前點(diǎn) xj依 ?xj得到第 j+1步的隨機(jī)搜索點(diǎn)。當(dāng) x?時(shí)，取為所求非線性方程組的近似解。否則進(jìn)行下一步新的隨機(jī)搜索過程。 7 舍伍德 (Sherwood)算法 設(shè) A是一個(gè)確定性算法，當(dāng)它的輸入實(shí)例為 x時(shí)所需的計(jì)算時(shí)間記為 tA(x)。設(shè) Xn是算法 A的輸入規(guī)模為 n的實(shí)例的全體，則當(dāng)問題的輸入規(guī)模為 n時(shí)，算法 A所需的平均時(shí)間為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1