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