數據結構計算機領域本科教育教學改革試點工作計劃（“101計劃”）研究成果101高級算法設計第16章16.1近似算法16.2啟發式搜索算法16.3隨機算法動機16.1近似算法針對難以在多項式時間內精確求得最優解的問題，一種可行的替代方案是：不追求最優解，而是退而求其次，找到一種方法能夠在多項式時間內求得近似最優解。在實際應用中，近似最優解往往能滿足實際需要。求得近似最優解的算法就稱為近似算法。近似算法的性能比16.1近似算法

例：頂點覆蓋問題16.1近似算法

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

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

V'或v

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

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

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

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

有一個3

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

h*(X)，其中h*(X)是X到目標狀態的最優代價的實際值，則可以證明，當問題存在解時，A算法一定能夠搜索到最優解。啟發式函數滿足上述條件的A算法，稱作A*算法。A*算法的單調限制條件16.2啟發式搜索算法

從上面的搜索過程可以看出，某些已擴展完畢的結點可能會從CLOSED表中取出，重新放入OPEN表中，后續重新被擴展。從而導致一個結點可能被多次擴展，影響搜索效率。

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

C(X,Y)且h(T)=0其中Y是X的子結點，T是目標結點，C(X,Y)是X到Y的代價，則稱啟發式函數h滿足單調限制條件。

可以證明，若算法使用的啟發式函數h滿足單調限制條件，搜索過程中不會發生一個結點被多次擴展的情況。此外，滿足單調限制條件的啟發函數也一定滿足h(X)

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

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

模擬退火算法16.2啟發式搜索算法

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

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

若n是素數，且0<x<n，則x2

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

計算aimodn的冪取模算法PowMod(a,i,n)輸入：整數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素數測試算法MillerRabin-IsPrime(n,k)輸入：整數n,測試次數k輸出：若n是素數，返回true，否則返回falseifn=2then|returntrueendifn<2ornmod2=0then|returnfalse endfori

1tokdo |a

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

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

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

-1小的元素。

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