計算機算法設計與分析--第7章隨機化算法-資料下載頁
2025-10-07 14:35本頁面
【正文】 ，則有： 解此方程可得： ))()())((1()()()( xtxexpxsxpxt ????)()( )(1)()( xexp xpxsxt ???2021年 11月 12日 20 提綱 一、隨機化算法的基本思想 二、隨機數(shù) 三、數(shù)值隨機化算法 四、 舍伍德 （ Sherwood） 算法 五、拉斯維加斯（ Las Vegas）算法 六、蒙特卡羅（ Monte Carlo）算法 2021年 11月 12日 21 六、 Monte Carlo算法 基本思想 ?在實際應用中常會遇到一些問題，不論采用確定性算法或概率算法都無法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。 ?設 p是一個實數(shù)，且 1/2p1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于 p，則稱該蒙特卡羅算法是 p正確 的，且稱 p1/2是該算法的 優(yōu)勢 。 ?如果對于同一實例，蒙特卡羅算法不會給出 2個不同的正確解答，則稱該蒙特卡羅算法是 一致的 。 ?有些蒙特卡羅算法除了具有描述問題實例的輸入?yún)?shù)外，還具有描述錯誤解可接受概率的參數(shù)。這類算法的計算時間復雜性通常由問題的實例規(guī)模以及錯誤解可接受概率的函數(shù)來描述。 2021年 11月 12日 22 對于一個一致的 p正確蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干次，并選擇出現(xiàn)頻次最高的解即可。 如果重復調(diào)用一個一致的 (1/2+?)正確的蒙特卡羅算法 2m1次，得到正確解的概率至少為 1?，其中， mii mimi ??????4)41()41(221 2210????????????? ???對于一個解所給問題的蒙特卡羅算法 MC(x)，如果存在問題實例的子集 X使得： (1)當 x?X時， MC(x)返回的解是正確的； (2)當 x?X時，正確解是 y0，但 MC(x)返回的解未必是 y0。 稱上述算法 MC(x)是 偏 y0的算法 。 重復調(diào)用一個一致的， p正確偏 y0蒙特卡羅算法 k次，可得到一個O(1(1p)k)正確的蒙特卡羅算法，且所得算法仍是一個一致的偏 y0蒙特卡羅算法。 六、 Monte Carlo算法 基本思想
教學課件相關推薦
鄂ICP備17016276號-1