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

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

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

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

花4天的時(shí)間計(jì)算出準(zhǔn)確的藏寶地點(diǎn),然后出發(fā)尋寶,一旦出發(fā)，不能返回。方案2

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

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

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

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

一次成功所得：x-5y，機(jī)會(huì)1/2

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

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

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

要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的知識(shí)。§概率算法的特點(diǎn)第1講概率法§概率算法的分類數(shù)值概率算法（Numerical）蒙特卡羅算法（MonteCarlo)拉斯維加斯算法（LasVegas）舍伍德算法（Sherwood）很多人將所有概率算法(尤其是數(shù)值概率算法)稱為MonteCarlo算法第1講概率法

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

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

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

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

投幣法計(jì)算π值

計(jì)算定積分

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

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

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

經(jīng)典實(shí)例:

主元素問題

素?cái)?shù)測(cè)試

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

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

經(jīng)典實(shí)例:

n后問題

整數(shù)因子分解

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

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

Sherwood算法

經(jīng)典實(shí)例:

線性時(shí)間選擇算法

跳躍表

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

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

模擬退火算法

遺傳算法

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

蟻群優(yōu)化算法

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

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

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