計(jì)算機(jī)算法設(shè)計(jì)與分析--第7章隨機(jī)化算法-在線瀏覽
2024-12-03 14:35本頁面
【正文】 二、隨機(jī)數(shù) 三、數(shù)值概率算法 四、 舍伍德 （ Sherwood） 算法 五、拉斯維加斯（ Las Vegas）算法 六、蒙特卡羅（ Monte Carlo）算法 2021年 11月 12日 4 ? 是一種使用概率和統(tǒng)計(jì)方法在其執(zhí)行過程中對于下一計(jì)算步驟作出隨機(jī)選擇的算法。 ? 隨機(jī)化算法把 “ 對于所有合理的輸入都必須給出正確的輸出 ” 這一求解問題的條件放寬，把 隨機(jī)性 的選擇注入到算法中，在算法執(zhí)行某些步驟時(shí)，可以隨機(jī)地選擇下一步該如何進(jìn)行，同時(shí) 允許結(jié)果以較小的概率出現(xiàn)錯(cuò)誤 ，并以此為代價(jià)，獲得算法運(yùn)行時(shí)間的大幅度減少。 隨機(jī)化算法首先生成一個(gè)隨機(jī) n元向量 (r1, r2, …, rn)，并計(jì)算 f(r1, r2, …, rn)的值，如果f(r1, r2, …, rn)≠0，則 f(x1, x2, …, xn)≠0；如果f(r1, r2, …, rn)＝ 0，則或者 f(x1, x2, …, xn)恒等于 0，或者是 (r1, r2, …, rn)比較特殊，如果這樣重復(fù)幾次，繼續(xù)得到 f(r1, r2, …, rn)＝0的結(jié)果，那么就可以得出 f(x1, x2, …, xn)恒等于 0的結(jié)論，并且測試的隨機(jī)向量越多，這個(gè)結(jié)果出錯(cuò)的可能性就越小。 2021年 11月 12日 7 隨機(jī)化算法的基本特征 ?隨機(jī)化算法的隨機(jī)性： ?對于同一實(shí)例的多次執(zhí)行 , 效果可能完全不同； ?時(shí)間復(fù)雜性的一個(gè)隨機(jī)變量； ?解的正確性和準(zhǔn)確性也是隨機(jī)的。 ? 線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。 d稱為該隨機(jī)序列的種子。這是隨機(jī)性理論研究的內(nèi)容，已超出本書討論的范圍。 2021年 11月 12日 13 提綱 一、隨機(jī)化算法的基本思想 二、隨機(jī)數(shù) 三、數(shù)值隨機(jī)化算法 四、 舍伍德 （ Sherwood） 算法 五、拉斯維加斯（ Las Vegas）算法 六、蒙特卡羅（ Monte Carlo）算法 2021年 11月 12日 14 ?值 設(shè)有一半徑為 r的圓及其外切四邊形。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為 k。所以當(dāng) n足夠大時(shí)， k與 n之比就逼近這一概率。 int k=0。i =n。 double y=()。 } return 4*k/double(n)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1