概率型算法思想是允許算法執(zhí)行某些步驟時，可以隨機地選擇下一步該如何進行，同時允許結(jié)果以較小的概率出現(xiàn)錯誤，并以此為代價，獲得算法允許時間的大幅度較少。隨機選擇的關(guān)鍵是產(chǎn)生一個隨機數(shù)用于下一步的選擇，此時涉及到隨機種子，用于確定隨機數(shù)的開始點，然后按照某個隨機發(fā)生器(產(chǎn)生隨機數(shù)的算法)產(chǎn)生隨機數(shù)，由于只是一定程度上的隨機，應(yīng)該將隨機數(shù)稱為偽隨機數(shù)。

1．???????????舍伍德型概率算法：消除算法的時間復(fù)雜性與輸入實例間的聯(lián)系，即通過隨機選擇下一步的執(zhí)行，使算法的時間復(fù)雜度與輸入實例的順序次序無關(guān)。如快速排序（隨機選擇軸元素），選擇問題中可以運用。

2．???????????拉斯維加斯概率型算法：隨機選擇輸入看是否能夠得到問題的解。隨機性的選擇可能導(dǎo)致算法陷入僵局，并且算法能夠檢測是否陷入僵局。它做的隨機性選擇有可能導(dǎo)致算法找不到問題的解，即算法運行一次，或者得到正確的解，或者無解。因此需要對同一輸入實例反復(fù)多次運行，直到成功地獲得問題的解。可以改進算法的時間性能。典型的應(yīng)用是八皇后問題，整數(shù)因子分解問題。

素數(shù)測試方法：判斷一個整數(shù)n是不是素數(shù)，可以通過判斷2到根號下n之間的數(shù)有沒有可以被n的整除的，若沒有說明n是素數(shù)。

3．???????????蒙特卡洛型概率算法：（常用于true和false問題中）用于問題的準確解。一個蒙特卡洛型概率算法偶爾會出錯，但無論任何輸入實例，總能以較高的概率找到一個正確解。重復(fù)地運行算法，每一次運行都獨立的進行隨機選擇，可以使產(chǎn)生不正確解得概率變得任意小。可以應(yīng)用在主元素問題中。（主元素是指，數(shù)組中的某個元素占數(shù)組中的一半以上。）一般求解方法是統(tǒng)計每個元素在數(shù)組中出現(xiàn)的次數(shù)。蒙特卡洛型概率算法，是隨機選擇一個元素進行統(tǒng)計，測試是不是主元素，若是時返回，不是時重復(fù)測試k次，降低出錯的概率。

?

?

近似算法：某些問題要求得起最優(yōu)解時，往往時間代價很大，采用近似算法是用近似最優(yōu)解代替最優(yōu)解，以獲取算法設(shè)計上的簡化和時間復(fù)雜性的降低。近似比：將最優(yōu)解和近似最優(yōu)解兩者的比值稱為近似比，顯然近似比大于1，且近似比接近1時，我們說近似算法能求得較好的近似最優(yōu)解。

?????裝箱問題可以采用近似算法求解。（裝箱問題：設(shè)有n個物品和若干個容量為C的箱子，n個物品的體積分別為{s1,s2,…,sn}，如何用最少的箱子數(shù)把物品全部裝入箱子中。）有方法：首次適宜法，最適宜法，降序首次適宜發(fā)和降序最適宜法。

總結(jié)

以上是生活随笔為你收集整理的概率型算法近似算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。