第6章-第1講-概率算法介紹-1

第六章概率算法每節(jié)一經(jīng)典走好運，造機遇----隨機算法

第1講概率法§1.1引言故事：想象自己是神化故事的主人公,你有一張不易懂的地圖,上面描述了一處寶藏的藏寶地點.經(jīng)分析你能確定最有可能的兩個地點是藏寶的地點,但二者相距甚遠.假設：你到達其中一處,就立即知道該處是否為藏寶地點（一看便知）.從其中一處到另一處的距離是5天的行程.進一步假設有一條惡龍,每晚光顧寶藏并從中拿走一部分財寶（d）。假設你取寶藏的方案有兩種：第1講概率法§1.1引言5天5天5天??

藏寶地點藏寶地點走哪邊最容易找到寶藏？第1講概率法§1.1引言方案1

花4天的時間計算出準確的藏寶地點,然后出發(fā)尋寶,一旦出發(fā)，不能返回。方案2

有一個小精靈告訴你地圖的秘密,但你必須付給他報酬,相當于惡龍3晚上拿走的財寶。若忽略可能的冒險和出發(fā)尋寶的代價,你是否接受小精靈的幫助？顯然,應該接受小精靈的幫助,因為你只需給出3晚上被盜竊的財寶量(3d),否則你將失去4晚被盜財寶量(4d)。方案3:但是,若冒險,你可能做得更好！問題理解第1講概率法§1.1引言設x是你決定之前當日的寶藏價值，設y是惡龍每晚盜走的寶藏價值，并設x>9y

方案1：4天計算確定地址，行程5天，你得到的寶藏價值為：x-9y

方案2：3y付給小精靈，行程5天失去5y，你得到的寶藏價值為：x-8y

方案3：投硬幣決定先到一處，失敗后到另一處(冒險方案)

一次成功所得：x-5y，機會1/2

二次成功所得：x-5y-5y=x-10y，機會1/2}期望贏利:x-7.5y數(shù)學模型平均（期望）贏利=(x-5y)*(1/2)+(x-10y)*(1/2)=x-7.5y第1講概率法§1.1引言該故事告訴我們：當一個算法面臨某種選擇時,有時隨機選擇比花費更多時間（耗時）做最優(yōu)選擇更好,尤其是當最優(yōu)選擇所花的時間大于隨機選擇的平均時間的時侯。第1講概率法概率算法是指選擇下一步執(zhí)行步驟時，用隨機（概率）方法進行選擇，而不是用邏輯上確定的方法進行選擇.§概率算法定義允許算法在執(zhí)行的過程中隨機選擇下一個計算步驟。許多情況下，當算法在執(zhí)行過程中面臨一個選擇時，隨機性選擇常比最優(yōu)選擇省時。因此概率算法可在很大程度上降低算法的復雜度。

p1p2p3p4p5第1講概率法隨機決策不可再現(xiàn)性

在同一實例上執(zhí)行兩次其結果可能不同;在同一實例上執(zhí)行兩次的時間亦可能不太相同。分析困難

要求有概率論，統(tǒng)計學和數(shù)論的知識?！旄怕仕惴ǖ奶攸c第1講概率法§概率算法的分類數(shù)值概率算法（Numerical）蒙特卡羅算法（MonteCarlo)拉斯維加斯算法（LasVegas）舍伍德算法（Sherwood）很多人將所有概率算法(尤其是數(shù)值概率算法)稱為MonteCarlo算法第1講概率法

數(shù)值概率算法數(shù)值算法常用于數(shù)值問題的求解.最早用于求數(shù)值問題的近似解。

特點:概率算法獲得的答案一般是近似的,但通常算法執(zhí)行的時間越長,精度就越高,誤差就越小.使用的理由：

精確解存在但無法在可行的時間內(nèi)求得。

有時答案是以置信區(qū)間的形式給出的。經(jīng)典實例

投幣法計算π值

計算定積分

解非線性方程組第1講概率法

MonteCarlo算法(MC算法)蒙特卡洛算法，1945年由J.VonNeumann進行核武模擬提出的.它是以概率和統(tǒng)計的理論與方法為基礎的一種數(shù)值計算方法,它是雙重近似:一是用概率模型模擬近似的數(shù)值計算,二是用偽隨機數(shù)模擬真正的隨機變量的樣本.這里我們指的MC算法是:若問題只有1個正確的解,而無近似解的可能時，使用MC算法。例如,判定問題只有真或假兩種可能性,沒有近似解,如因式分解,我們不能說某數(shù)幾乎是一個因子。第1講概率法

特點:MC算法總是能給出一個答案,但該答案未必正確,成功(即答案是正確的)的概率正比于算法執(zhí)行的時間。一般不能有效地確定算法的答案是否正確。

經(jīng)典實例:

主元素問題

素數(shù)測試

MonteCarlo算法(MC算法)第1講概率法

LasVegas算法(LV算法)LV算法絕不返回錯誤的答案。特點：獲得的答案必定正確,但有時找不到答案，和MC算法一樣,成功的概率亦隨算法執(zhí)行時間增加而增加.無論輸入何種實例,只要算法在該實例上運行足夠的次數(shù),則算法失敗的概率就任意小。

經(jīng)典實例:

n后問題

整數(shù)因子分解

模p平方根第1講概率法Sherwood算法總是給出正確的答案。當某些確定算法解決一個特殊問題的平均時間比最壞情況下所需時間快得多時,我們可以使用

Sherwood算法來減少甚至是消除“好的”和”壞的”實例之間的差別。

Sherwood算法

經(jīng)典實例:

線性時間選擇算法

跳躍表

隨機的預處理第1講概率法智能優(yōu)化算法

模擬自然過程“優(yōu)勝略劣汰”的算法一般稱之為智能算法。例如，根據(jù)動植物繁衍過程原理、物理或化學現(xiàn)象原理等設計的解決困難計算問題的算法，都可以稱為智能優(yōu)化算法。例如：

模擬退火算法

遺傳算法

神經(jīng)網(wǎng)絡算法

蟻群優(yōu)化算法

粒子群優(yōu)化算法

魚群算法……第1講概率法計算智能智能計算演化計算仿生計算進化計算……現(xiàn)代計算新方向：（以下含義基本相同）第1講概率法模擬退火算法物理學中，通過對固體退火過程的研究知道：高溫狀態(tài)下的物質(zhì)降溫時其內(nèi)能隨之下降；如果降溫過程充分緩慢，則在降溫過程中物質(zhì)體系始終處于平衡狀態(tài)；當降到某一低溫時，其內(nèi)能可能達到最??；稱這種降溫過程為退火過程，模擬退火過程的尋優(yōu)方法稱為模擬退火算法（simulatedannealing,SA）.Metropolis1953年提出。第1講概率法遺傳算法遺傳算法是模擬生物進化過程的智能優(yōu)化算法，由J.H.Holland60年代提出。關鍵思想是：1）對問題的解用染色體編碼表示（0，1編碼）；2）染色體結合時，雙親的遺傳基因的結合使子女具有雙親特征；3）染色體結合時，隨機的變異造成子女與雙親的不同。4）算子：選擇，交叉，變異例如：解編碼：雙親—交叉(后三位)—子女10011101111111111011

第1講概率法神經(jīng)網(wǎng)絡算法根據(jù)人腦組織結構和運行機制，40年代心理學家McCulloch和數(shù)學家Pitts提出了人工神經(jīng)網(wǎng)絡的數(shù)學模型。神經(jīng)網(wǎng)絡由大量神經(jīng)元互連而成，具有高速信息處理能力。例如：特點：分布并行第1講概率法神經(jīng)網(wǎng)絡算法根據(jù)人腦組織結構和運行機制，40年代心理學家McCulloch和數(shù)學家Pitts提出了人工神經(jīng)網(wǎng)絡的數(shù)學模型。神經(jīng)網(wǎng)絡由大量神經(jīng)元互連而成，具有高速信息處理能力。例如：特點：分布并行第1講概率法粒子群優(yōu)化算法粒子群優(yōu)化算法(PSO)是一種進化計算技術(evolutionarycomputation)，由Eberhart博士和kennedy博士發(fā)明（199