數(shù)據(jù)結(jié)構(gòu)課件-第16章 高級(jí)算法設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)領(lǐng)域本科教育教學(xué)改革試點(diǎn)工作計(jì)劃（“101計(jì)劃”）研究成果101高級(jí)算法設(shè)計(jì)第16章16.1近似算法16.2啟發(fā)式搜索算法16.3隨機(jī)算法動(dòng)機(jī)16.1近似算法針對(duì)難以在多項(xiàng)式時(shí)間內(nèi)精確求得最優(yōu)解的問題，一種可行的替代方案是：不追求最優(yōu)解，而是退而求其次，找到一種方法能夠在多項(xiàng)式時(shí)間內(nèi)求得近似最優(yōu)解。在實(shí)際應(yīng)用中，近似最優(yōu)解往往能滿足實(shí)際需要。求得近似最優(yōu)解的算法就稱為近似算法。近似算法的性能比16.1近似算法

例：頂點(diǎn)覆蓋問題16.1近似算法

無向圖的頂點(diǎn)覆蓋是圖中一些頂點(diǎn)的集合，使得圖中的每條邊都至少以該集合中的一個(gè)頂點(diǎn)為端點(diǎn)。形式化地，無向圖G=（V，E）的一個(gè)頂點(diǎn)覆蓋是一個(gè)頂點(diǎn)子集V'

V，若(u,v)是G的一條邊，則必有u

V'或v

V'，即G中每條邊都至少有一個(gè)端點(diǎn)在V’中。頂點(diǎn)覆蓋問題是指在給定的無向圖中，找出一個(gè)包含頂點(diǎn)數(shù)最少的頂點(diǎn)覆蓋，稱這樣的頂點(diǎn)覆蓋為最優(yōu)頂點(diǎn)覆蓋。目前尚無精確求解該問題的多項(xiàng)式時(shí)間算法。例：頂點(diǎn)覆蓋問題16.1近似算法算法16.1頂點(diǎn)覆蓋問題的近似算法VertexCoverApproximation(E)輸入：圖的邊集合E輸出：近似最優(yōu)頂點(diǎn)覆蓋集合CInitSet(C) //將頂點(diǎn)覆蓋集合初始化為空whileIsEmpty(E)≠truedo |從E中任意選取一條邊(u,v)|Insert(C,u,v)//將頂點(diǎn)u和v插入頂點(diǎn)覆蓋集合|Delete(E,u,v)//從E中刪除以頂點(diǎn)u或頂點(diǎn)v為端點(diǎn)的所有邊endreturnC例：頂點(diǎn)覆蓋問題16.1近似算法例：頂點(diǎn)覆蓋問題16.1近似算法定理16-1算法VertexCoverApproximation的近似比為2。證明：設(shè)A為算法每次迭代過程中選出的邊（u，v）的集合，C*為最優(yōu)頂點(diǎn)覆蓋。在算法迭代過程中，若一條邊被選中，與該邊有共同端點(diǎn)的邊隨后都將被刪去，故A中的邊沒有共同的端點(diǎn)。這意味著C*中的一個(gè)頂點(diǎn)最多只能覆蓋A中的一條邊，故C*中的頂點(diǎn)個(gè)數(shù)大于等于A中的邊數(shù)，即：|C*|

|A|又由于A中每次被選出的1條邊的2個(gè)端點(diǎn)均被放入集合C中，故C中頂點(diǎn)個(gè)數(shù)等于A中邊數(shù)的2倍，即：|C|=2|A|綜上，有：|C|=2|A|

2|C*|例：離散背包問題16.1近似算法約定：假定一共有n個(gè)物品，編號(hào)為1至n。第i個(gè)物品的重量記為wi，第i個(gè)物品的價(jià)值記為vi。算法：通過每次選取剩余物品中“價(jià)值最大”的物品獲得一個(gè)貪心解S1，通過每次選取剩余物品中“單位重量下價(jià)值最大”的物品獲得一個(gè)貪心解S2，然后從這兩個(gè)解中選取總價(jià)值最大的解作為最終解。性能：上述算法的近似比為2。A算法與A*算法16.2啟發(fā)式搜索算法A算法和A*算法是經(jīng)典的啟發(fā)式搜索算法，首先介紹A算法。在A算法中，定義如下評(píng)價(jià)函數(shù)對(duì)某一狀態(tài)X進(jìn)行評(píng)估f(X)=g(X)+h(X)其中，X表示當(dāng)前狀態(tài)，g(X)表示從初始狀態(tài)到達(dá)當(dāng)前狀態(tài)X已經(jīng)花費(fèi)的代價(jià)，例如在圖搜索中，可以是起點(diǎn)到當(dāng)前點(diǎn)的路徑長(zhǎng)度；h(X)稱為啟發(fā)函數(shù)，表示從當(dāng)前狀態(tài)X到目標(biāo)狀態(tài)所需最小代價(jià)的估計(jì)值，例如在圖搜索中，可表示當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的最短路徑長(zhǎng)度的估計(jì)值。

f(X)反映了從初始狀態(tài)經(jīng)過X到達(dá)目標(biāo)狀態(tài)的路徑的最小代價(jià)估計(jì)值，f(X)越小意味著X越有可能在解路徑上。在搜索過程中，A算法每次選擇f(X)值最小的狀態(tài)進(jìn)行下一步搜索。八數(shù)碼問題16.2啟發(fā)式搜索算法

有一個(gè)3

3的九宮格棋盤，棋盤中放置8個(gè)棋子，每個(gè)棋子標(biāo)有1-8的某個(gè)數(shù)字，不同棋子上標(biāo)的數(shù)字各不相同。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。要解決的問題是：給定一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始狀態(tài)變換為目標(biāo)狀態(tài)的最優(yōu)方案，該方案使棋子的移動(dòng)步數(shù)最少。八數(shù)碼問題16.2啟發(fā)式搜索算法h(X)=狀態(tài)X對(duì)應(yīng)的棋盤中不在目標(biāo)位置的棋子個(gè)數(shù)搜索過程中，每次從OPEN表中選擇評(píng)價(jià)函數(shù)值最小的結(jié)點(diǎn)X進(jìn)行擴(kuò)展。如果X是目標(biāo)結(jié)點(diǎn)，則找到一個(gè)解，算法終止；若X不是目標(biāo)結(jié)點(diǎn)，則擴(kuò)展X。對(duì)于由X擴(kuò)展出的結(jié)點(diǎn)Y：若Y既不在OPEN表中，也不在CLOSED表中，說明Y之前沒有被擴(kuò)展過，將Y加入OPEN表中；若Y已經(jīng)在OPEN表中，意味著找到了從初始結(jié)點(diǎn)到Y(jié)的兩條路徑，保留其中代價(jià)小的路徑；若Y已經(jīng)在CLOSED表中，也意味著找到了從初始結(jié)點(diǎn)到Y(jié)的兩條路徑，如果新路徑的代價(jià)低，則將Y從CLOSED表中取出，重新放入OPEN表中，以備后續(xù)重新擴(kuò)展。重復(fù)以上過程，直至找到解或OPEN表為空。若算法以O(shè)PEN表為空結(jié)束，意味著該問題沒有解。A*算法16.2啟發(fā)式搜索算法如果啟發(fā)式函數(shù)h滿足h(X)

h*(X)，其中h*(X)是X到目標(biāo)狀態(tài)的最優(yōu)代價(jià)的實(shí)際值，則可以證明，當(dāng)問題存在解時(shí)，A算法一定能夠搜索到最優(yōu)解。啟發(fā)式函數(shù)滿足上述條件的A算法，稱作A*算法。A*算法的單調(diào)限制條件16.2啟發(fā)式搜索算法

從上面的搜索過程可以看出，某些已擴(kuò)展完畢的結(jié)點(diǎn)可能會(huì)從CLOSED表中取出，重新放入OPEN表中，后續(xù)重新被擴(kuò)展。從而導(dǎo)致一個(gè)結(jié)點(diǎn)可能被多次擴(kuò)展，影響搜索效率。

如果啟發(fā)式函數(shù)滿足如下條件：h(X)-h(Y)

C(X,Y)且h(T)=0其中Y是X的子結(jié)點(diǎn)，T是目標(biāo)結(jié)點(diǎn)，C(X,Y)是X到Y(jié)的代價(jià)，則稱啟發(fā)式函數(shù)h滿足單調(diào)限制條件。

可以證明，若算法使用的啟發(fā)式函數(shù)h滿足單調(diào)限制條件，搜索過程中不會(huì)發(fā)生一個(gè)結(jié)點(diǎn)被多次擴(kuò)展的情況。此外，滿足單調(diào)限制條件的啟發(fā)函數(shù)也一定滿足h(X)

h*(X)，即一定能找到最優(yōu)解。局部搜索算法16.2啟發(fā)式搜索算法

爬山算法是最簡(jiǎn)單的局部搜索算法之一。該方法首先設(shè)定一個(gè)評(píng)價(jià)函數(shù)來衡量解的質(zhì)量。假定求解最大化問題，即目標(biāo)是找使評(píng)價(jià)函數(shù)值最大的解。在搜索過程中，從一個(gè)初始解出發(fā)，每次對(duì)當(dāng)前解施加局部修改，得到其鄰域內(nèi)的所有解。然后，在這些解中選擇使評(píng)分值增加最多的解，繼續(xù)下一步搜索，直至某個(gè)解的鄰域內(nèi)沒有更好的解為止；即無論對(duì)該解進(jìn)行何種局部修改，都無法使解的評(píng)分值增加，則當(dāng)前解就是搜索到的局部最優(yōu)解。例：頂點(diǎn)覆蓋問題16.2啟發(fā)式搜索算法

模擬退火算法16.2啟發(fā)式搜索算法

基本思想16.3隨機(jī)算法如果一個(gè)算法的行為不僅由輸入決定，而且也由隨機(jī)數(shù)決定，則可稱此類算法為隨機(jī)算法。與之對(duì)應(yīng)，未使用隨機(jī)數(shù)做決策的算法可稱為確定型算法。對(duì)于確定型算法，可能存在特定的輸入數(shù)據(jù)，其總能導(dǎo)致最壞情況的運(yùn)行時(shí)間。而對(duì)于隨機(jī)算法，以相同的輸入數(shù)據(jù)運(yùn)行兩次，往往會(huì)得到不同的運(yùn)行時(shí)間。對(duì)于一些問題，當(dāng)算法在執(zhí)行過程中面臨某種選擇時(shí)，隨機(jī)性選擇往往比最優(yōu)選擇省時(shí)，這種情況下將使得隨機(jī)算法的效率優(yōu)于確定型算法。而對(duì)于另一些問題，某些算法往往在平均情況下時(shí)間復(fù)雜度較低，僅在最壞情況下時(shí)間復(fù)雜度高，此時(shí)可以結(jié)合隨機(jī)策略，降低最壞情況發(fā)生的概率，從而設(shè)計(jì)出在平均情況下高效的算法。隨機(jī)算法的分類16.3隨機(jī)算法拉斯維加斯（LasVegas）型隨機(jī)算法：總能返回正確解，但算法的運(yùn)行時(shí)間隨機(jī)，往往由算法所選擇的隨機(jī)數(shù)決定，分析該類算法重點(diǎn)在于分析其期望時(shí)間復(fù)雜度。蒙特卡洛（MonteCarlo）型隨機(jī)算法：執(zhí)行步數(shù)確定，但求得的解未必是一定正確的，屬于啟發(fā)式算法的一種，可能會(huì)有一定概率產(chǎn)生錯(cuò)誤的解，分析該類算法重點(diǎn)往往在于分析其出錯(cuò)概率。例：素?cái)?shù)測(cè)試（蒙特卡洛型隨機(jī)算法）16.3隨機(jī)算法費(fèi)馬小定理：若n是素?cái)?shù)且0<a<n，則an-1

1(modn)。二次探測(cè)定理：

若n是素?cái)?shù)，且0<x<n，則x2

1(modn)僅有兩個(gè)解，分別為x=1或x=n-1。算法

計(jì)算aimodn的冪取模算法PowMod(a,i,n)輸入：整數(shù)a,i,n輸出：aimodnifi=0then|return1 endx

PowMod(a,i/2,n) ifx=0then|return0endy

(x

x)modn ify=1且x

1且x

n-1then |return0endifimod2=1then |y

(y

a)modn endreturny算法Miller-Rabin素?cái)?shù)測(cè)試算法MillerRabin-IsPrime(n,k)輸入：整數(shù)n,測(cè)試次數(shù)k輸出：若n是素?cái)?shù)，返回true，否則返回falseifn=2then|returntrueendifn<2ornmod2=0then|returnfalse endfori

1tokdo |a

Random(2,n-1) |ifPowMod(a,n-1,n)

1then||returnfalse|endendreturntrue例：隨機(jī)快速選擇（拉斯維加斯型隨機(jī)算法）16.3隨機(jī)算法

快速選擇問題是在包含n個(gè)元素的數(shù)組A中找第k（k<n）小的數(shù)。算法的基本思想是基于快速排序的Partition操作，將數(shù)組分為三部分：左部分A[1…j-1]、中間部分A[j]、右部分A[j+1…n]。如果左部分元素個(gè)數(shù)等于k-1，則A[j]即為第k小的元素，算法結(jié)束；如果左部分元素個(gè)數(shù)大于k-1，則第k小的元素必在左部分，對(duì)左部分子數(shù)組繼續(xù)遞歸查找第k小的元素；如果左部分元素個(gè)數(shù)小于k-1，則第k小的元素必在右部分，若左部分包含nL個(gè)元素，則對(duì)右部分子數(shù)組遞歸查找第k-nL

-1小的元素。

快速選擇算法的時(shí)間復(fù)雜度依賴于Partition操作中軸點(diǎn)的選取。若每次都選擇當(dāng)前子數(shù)組中位數(shù)作為軸點(diǎn)，則算法達(dá)到最好情況時(shí)間復(fù)雜度O(n)，若每次都選擇當(dāng)前子數(shù)組的最小元素或最大元素作為軸點(diǎn)，則算法達(dá)到最壞情況時(shí)間復(fù)雜度O(n2)?？梢?，數(shù)組已經(jīng)排好序或接近有序時(shí)，算法性能較差，而這種情況在現(xiàn)實(shí)中往往經(jīng)常出現(xiàn)。例：隨機(jī)快速選擇（拉斯維加斯型隨機(jī)算法）16.3隨機(jī)算法