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