隨機(jī)算法比較

1、精選優(yōu)質(zhì)文檔-傾情為你奉上問(wèn)題：對(duì)比舍伍德算法、拉斯維加斯算法、蒙特卡洛算法的適用范圍以及它們的優(yōu)缺點(diǎn)。一、舍伍德算法：l 特點(diǎn)舍伍德算法總能求得問(wèn)題的一個(gè)解，且所求得的解總是正確的。當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大的差別時(shí)，可在這個(gè)確定性算法中引入隨機(jī)性將它改造成一個(gè)舍伍德算法，消除或減少問(wèn)題的好壞實(shí)例間的這種差別。舍伍德算法的精髓不是避免算法的最壞情形行為，而是設(shè)法消除這種最壞情形行為與特定實(shí)例之間的關(guān)聯(lián)性。舍伍德算法不會(huì)從整體上或平均的改善問(wèn)題求解的時(shí)間復(fù)雜度，但可以對(duì)一些特別耗時(shí)的特定輸入改善至較適中的時(shí)間復(fù)雜度。設(shè)A是一個(gè)確定性算法，當(dāng)它的輸

2、入實(shí)例為x時(shí)所需的計(jì)算時(shí)間記為tA(x)。設(shè)Xn是算法A的輸入規(guī)模為n的實(shí)例的全體，則當(dāng)問(wèn)題的輸入規(guī)模為n時(shí)，算法A所需的平均時(shí)間為 這顯然不能排除存在xXn使得 tA(x)>>tA(n)的可能性。 希望獲得一個(gè)概率算法B，使得對(duì)問(wèn)題的輸入規(guī)模為n的每一個(gè)實(shí)例均有 這就是舍伍德算法設(shè)計(jì)的基本思想。當(dāng)s(n)與tA(n)相比可忽略時(shí)，舍伍德算法可獲得很好的平均性能。l 適用范圍：1. 快速排序算法2. 線(xiàn)性時(shí)間選擇算法上述兩算法選擇合適的劃分基準(zhǔn)，舍伍德算法隨機(jī)地選擇一個(gè)數(shù)組元素作為劃分基準(zhǔn)，這樣既能保證算法的線(xiàn)性時(shí)間平均性能，又避免了計(jì)算擬中位數(shù)的麻煩。 3. 搜索有序表利用數(shù)組的

3、小標(biāo)的索引性質(zhì)，可以設(shè)計(jì)一個(gè)隨機(jī)化搜索算法，以改進(jìn)算法的搜索時(shí)間復(fù)雜性。即隨機(jī)抽取數(shù)組元素若干次，從較近搜索元素x的位置開(kāi)始做順序搜索。4. 跳躍表在跳躍表中隨機(jī)增加附加指針，以及在該結(jié)點(diǎn)處應(yīng)隨機(jī)增加指針。二、拉斯維加斯算法：l 特點(diǎn)：拉斯維加斯算法不會(huì)得到不正確的解。一旦用拉斯維加斯算法找到一個(gè)解，這個(gè)解就一定是正確解。與蒙特卡羅算法類(lèi)似，拉斯維加斯算法找到正確解的概率隨著它所用的計(jì)算時(shí)間的增加而提高。但對(duì)所求解的問(wèn)題，用同一個(gè)拉斯維加斯算法反復(fù)求解多次，可以使得求解失效的概率任意小。拉斯維加斯算法能顯著改進(jìn)算法的有效性。甚至于對(duì)某些迄今為止找不到有效算法的問(wèn)題，也能得到滿(mǎn)意的結(jié)果。拉斯維加

4、斯算法的一個(gè)顯著特征是它所做出的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。因此通常用一個(gè)bool型函數(shù)來(lái)表示拉斯維加斯型算法。當(dāng)算法找到一個(gè)解時(shí)返回true，否則返回false。拉斯維加斯算法的典型調(diào)用形式為bool success=LV(x,y)；其中x是輸入?yún)?shù)；當(dāng)success的值為true時(shí)，y返回問(wèn)題的解。當(dāng)success的值為false時(shí)，算法未能找到問(wèn)題的解。此時(shí)可以對(duì)同一實(shí)例再次獨(dú)立的調(diào)用相同的算法。l 適用范圍：1. n后問(wèn)題在棋盤(pán)上相繼的各行中隨機(jī)地放置皇后，并且注意使新放置的皇后與已放置的皇后互不攻擊，直至n個(gè)皇后均已經(jīng)相容地放置好，或已沒(méi)有下一個(gè)皇后的可放置位置為止。2.

5、 整數(shù)因子分解3. 字符串匹配基于哈希計(jì)算的字符串匹配算法是拉斯維加斯型概率算法，母串的子串與模式串的哈希值相等時(shí)并不能保證匹配成功，而需要用樸素的方式進(jìn)行驗(yàn)證三、蒙特卡羅算法：l 特點(diǎn)：蒙特卡羅算法總能得到問(wèn)題的答案，但偶爾會(huì)產(chǎn)生不正確的答案。有時(shí)并不能判斷給出的答案是否正確。不存在任何近似解答。重復(fù)運(yùn)行算法使得產(chǎn)生不正確解的概率任意小。在實(shí)際應(yīng)用中，我們常會(huì)遇到一些問(wèn)題，不論是采用確定性的算法亦或者是隨機(jī)算法都無(wú)法保證每次都能得到正確的解。蒙特卡羅算法則在一般情況下可以保證對(duì)問(wèn)題的所有實(shí)例都以高概率給出正確的解，但是通常無(wú)法判斷一個(gè)具體解是否正確。設(shè)p是實(shí)數(shù)，且。如果一個(gè)蒙特卡羅算法對(duì)于問(wèn)題的任意實(shí)例得到正確解的概率不小于p，則稱(chēng)該蒙特卡羅算法是p正確的。且稱(chēng)是該算法的優(yōu)勢(shì)。如果對(duì)同一實(shí)例，蒙特卡羅算法不會(huì)給出兩個(gè)不同的正確答案，則稱(chēng)該蒙特卡羅算法是一致的。對(duì)于一致的p正確的蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干次，并選擇出頻次最高的解即可。l 適用范圍：1. 主元素問(wèn)題2. 素?cái)?shù)測(cè)試3. 二次探測(cè)4. 費(fèi)馬定理舍伍德算法拉斯維加斯算法蒙特卡羅算法優(yōu)點(diǎn) 一個(gè)正確解 盡量消除這種最壞情形與特定實(shí)例之間的關(guān)聯(lián)性 對(duì)實(shí)例的計(jì)算時(shí)