算法設(shè)計(jì)與分析 課件 第七章 分支限界

計(jì)算機(jī)算法設(shè)計(jì)與分析第7章分支限界法7.1.1廣度優(yōu)先搜索策略廣度優(yōu)先搜索（Breadth-FirstSearch，BFS）策略是一種常用的圖遍歷搜索算法，用于在圖或樹結(jié)構(gòu)中搜索特定的目標(biāo)?；舅枷胍环N分層的搜索過程，它從給定的起始頂點(diǎn)開始，以廣度優(yōu)先的方式一層一層搜索圖中的節(jié)點(diǎn)，直到找到目標(biāo)節(jié)點(diǎn)或遍歷完整個(gè)圖。為了實(shí)現(xiàn)逐層訪問，算法中使用了一個(gè)隊(duì)列，以記憶待訪問的結(jié)點(diǎn)，以便于向下一層擴(kuò)展結(jié)點(diǎn)。給定圖G=(V，E)，創(chuàng)建一個(gè)隊(duì)列，用于存儲(chǔ)待訪問的結(jié)點(diǎn)；為避免重復(fù)訪問，需要?jiǎng)?chuàng)建一個(gè)輔助數(shù)組visited[]，給被訪問過的結(jié)點(diǎn)加標(biāo)記。廣度優(yōu)先搜索策略基本步驟為：（1）初始化，將起始結(jié)點(diǎn)放入隊(duì)列中，并將其標(biāo)記為已訪問。（2）當(dāng)隊(duì)列不空，執(zhí)行以下步驟：①從隊(duì)列中取出一個(gè)結(jié)點(diǎn)。②檢查該結(jié)點(diǎn)是否是目標(biāo)結(jié)點(diǎn)。如果是，則搜索結(jié)束。③如果該結(jié)點(diǎn)不是目標(biāo)結(jié)點(diǎn)，則將其所有未被訪問過的鄰居結(jié)點(diǎn)放入隊(duì)列中，并標(biāo)記它們?yōu)橐言L問。（3）重復(fù)步驟（2），直到找到目標(biāo)結(jié)點(diǎn)搜索成功而結(jié)束，或者隊(duì)列為空且沒有找到目標(biāo)結(jié)點(diǎn)，搜索失敗而結(jié)束。7.1.1廣度優(yōu)先搜索策略BFS的偽代碼BFS(start,target)begin

創(chuàng)建隊(duì)列Q，并初始化隊(duì)列;Q.queueAppend(start)//起始出發(fā)點(diǎn)入隊(duì)，queueAppend入隊(duì)操作visited[start]

true//置已訪問標(biāo)記whilenotQ.isEmpty()do//isEmpty()判隊(duì)空操作node=Q.queueDel()//queueDel出隊(duì)操作

ifnode==targetthennode結(jié)點(diǎn)處理;returntrue;endifforneighborinnode.neighborsdo//枚舉node的所有相鄰結(jié)點(diǎn)ifvisited[neighbor]=falsethen//相鄰且沒有被訪問過的結(jié)點(diǎn)Q.queueAppend(neighbor)//入隊(duì)visited[neighbor]

true//置已訪問標(biāo)記 endif endfor

endwhilereturnfalseend效率分析鄰接矩陣存儲(chǔ)的圖進(jìn)行廣度優(yōu)先搜索算法，每個(gè)結(jié)點(diǎn)查找的鄰接頂點(diǎn)所需時(shí)間為O(|V|)，則總時(shí)間復(fù)雜度為O(|V|2)?？臻g復(fù)雜度為O(|V|2)，另外我們需要使用一個(gè)隊(duì)列和一個(gè)輔助數(shù)組來存儲(chǔ)結(jié)點(diǎn)和訪問狀態(tài)。鄰接表存儲(chǔ)的圖進(jìn)行廣度優(yōu)先搜索算法的時(shí)間復(fù)雜度為O(|V|+|E|)，其中|V|是結(jié)點(diǎn)的數(shù)量，|E|是邊的數(shù)量。這是因?yàn)槲覀冃枰闅v所有的結(jié)點(diǎn)和邊。計(jì)算機(jī)算法設(shè)計(jì)與分析第7章分支限界法7.2.1分支限界方式分支限界法根據(jù)從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的方式，可分為隊(duì)列式分支限界和優(yōu)先隊(duì)列式分支限界。（1）隊(duì)列式分支限界法隊(duì)列式（FIFO）式分支限界法的基本思想：（1）首先將初始狀態(tài)節(jié)點(diǎn)放入活結(jié)點(diǎn)隊(duì)列中。（2）若隊(duì)列非空，則重復(fù)下列步驟：①出隊(duì)，將出隊(duì)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。②判斷當(dāng)前擴(kuò)展結(jié)點(diǎn)是否為目標(biāo)結(jié)點(diǎn)，若是目標(biāo)結(jié)點(diǎn)，則搜索到一個(gè)可行解而結(jié)束。③對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)進(jìn)行擴(kuò)展。在擴(kuò)展節(jié)點(diǎn)時(shí)，一次性產(chǎn)生它的所有子結(jié)點(diǎn)，并利用剪枝函數(shù)檢測(cè)，把滿足約束和限界條件的的子結(jié)點(diǎn)依次加入活結(jié)點(diǎn)隊(duì)列。（3）重復(fù)（2），直到隊(duì)列為空，則搜索失敗結(jié)束。（2）優(yōu)先隊(duì)列式分支限界法將活結(jié)點(diǎn)表組成一個(gè)優(yōu)先隊(duì)列，按照優(yōu)先隊(duì)列中指定的結(jié)點(diǎn)優(yōu)先級(jí)，選取優(yōu)先級(jí)最高的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，以優(yōu)先隊(duì)列儲(chǔ)存活結(jié)點(diǎn)。結(jié)點(diǎn)的優(yōu)先級(jí)常用一個(gè)與該結(jié)點(diǎn)相關(guān)的限界函數(shù)值來表示。也稱為最小耗費(fèi)優(yōu)先分支限界法(LC)該策略與隊(duì)列式分支限界法的主要區(qū)別是：優(yōu)先隊(duì)列式分支限界法的活結(jié)點(diǎn)表組成一個(gè)優(yōu)先隊(duì)列，每個(gè)活結(jié)點(diǎn)入隊(duì)時(shí)會(huì)計(jì)算其優(yōu)先級(jí)，優(yōu)先級(jí)最高的活結(jié)點(diǎn)位于隊(duì)首位置。（2）優(yōu)先隊(duì)列式分支限界法優(yōu)先隊(duì)列通常采用堆數(shù)據(jù)結(jié)構(gòu)來組織，通過維護(hù)堆屬性，可以保證優(yōu)先隊(duì)列的入隊(duì)操作時(shí)按結(jié)點(diǎn)元素優(yōu)先級(jí)重新排序，也即隊(duì)列中優(yōu)先級(jí)最高的結(jié)點(diǎn)元素始終位于隊(duì)列首部位置。每次出隊(duì)的隊(duì)首結(jié)點(diǎn)總是當(dāng)前隊(duì)列中具有優(yōu)先級(jí)最高（最有利）的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹有最優(yōu)解的分支方向快速推進(jìn)，以便快速找到問題的最優(yōu)解。優(yōu)先隊(duì)列式分支限界法基本思想（1）確定合理的限界函數(shù)，并根據(jù)限界函數(shù)確定問題的目標(biāo)函數(shù)的上（下）界，又稱耗費(fèi)函數(shù)值或代價(jià)值。（2）初始化一個(gè)空的優(yōu)先隊(duì)列H，并將初始狀態(tài)加入隊(duì)列。初始化一個(gè)變量best_score用于保存當(dāng)前找到的最優(yōu)解（初值=無窮大）。（3）當(dāng)隊(duì)列H不為空時(shí)，執(zhí)行以下步驟：優(yōu)先隊(duì)列式分支限界法基本思想

①出隊(duì)結(jié)點(diǎn)保存為node。

②ifnode結(jié)點(diǎn)對(duì)應(yīng)更優(yōu)的解then更新當(dāng)前最優(yōu)解best_score的值。③fornode的每一個(gè)子結(jié)點(diǎn)child：a.計(jì)算child結(jié)點(diǎn)的目標(biāo)函數(shù)限界值。

b.if

child滿足解的約束條件且耗費(fèi)函數(shù)值不超過

目標(biāo)函數(shù)的當(dāng)前限界thenc.將child加入隊(duì)列H。（4）重復(fù)（3）直到隊(duì)列H為空（5）返回這時(shí)的best_score作為最優(yōu)解。計(jì)算機(jī)算法設(shè)計(jì)與分析第7章分支限界法7.3.1裝載問題一個(gè)農(nóng)場(chǎng)需要將大量農(nóng)產(chǎn)品運(yùn)輸?shù)绞袌?chǎng)上去，假設(shè)農(nóng)場(chǎng)現(xiàn)有n種不同的農(nóng)產(chǎn)品和一輛載重量為c的車輛，農(nóng)產(chǎn)品i的重量為wi，價(jià)值為vi，每種農(nóng)產(chǎn)品只有裝車和不裝車兩種選擇。如何選擇裝入車輛的農(nóng)產(chǎn)品，使得車輛不超重的情況下一次裝下的農(nóng)產(chǎn)品總重量最大。

7.3.1裝載問題以n=4種農(nóng)產(chǎn)品為例，車輛載重量c=10，每種農(nóng)產(chǎn)品的重量W={6,7,2,4}，即w1=6，w2=7,w3=2,w4=4。4種農(nóng)產(chǎn)品的裝載可以表示為一個(gè)四元組X=(x1,x2,x3,x4)，xi代表第i種農(nóng)產(chǎn)品裝車的數(shù)量，由于每種農(nóng)產(chǎn)品裝載只有裝與不裝兩種情況，所以xi(i=1,2,3,4，表示農(nóng)產(chǎn)品種編號(hào))只能等于0或1，其中0表示不裝車，1表示轉(zhuǎn)入車輛。

裝載問題4類農(nóng)產(chǎn)品裝載問題的解向量空間樹如圖所示

裝載問題c：表示車輛的載重量。xi：表示第i種農(nóng)產(chǎn)品裝入車輛的數(shù)量，取值0或1。wi：表示第i種農(nóng)產(chǎn)品的重量。wt：表示當(dāng)前已裝入車的農(nóng)產(chǎn)品總重量。bestw：表示當(dāng)前車上裝載的農(nóng)產(chǎn)品重量的最優(yōu)值。[wt，k]：表示解空間樹上一個(gè)結(jié)點(diǎn)的狀態(tài)，即從第1種農(nóng)產(chǎn)品到第k種農(nóng)產(chǎn)品完成裝載選擇時(shí)，該結(jié)點(diǎn)表示的車輛上農(nóng)產(chǎn)品總重量為wt。Wt(X)：表示解向量X時(shí)，車輛裝載的農(nóng)產(chǎn)品總重量。

裝載問題給定任意狀態(tài)[wt，k]，怎么來判斷其子結(jié)點(diǎn)是否可能得出可行解？約束函數(shù)剪枝過程約束函數(shù)剪枝過程擴(kuò)展A結(jié)點(diǎn)的左子結(jié)點(diǎn)，xk+1=1，wt’=wt+wk+1，如果這時(shí)wt’>c，說明裝入車輛的農(nóng)產(chǎn)品重量超過了車輛的載重量，顯然這時(shí)不可行的，需要被剪枝處理。而擴(kuò)展A結(jié)點(diǎn)的右子結(jié)點(diǎn)，xk+1=0，wt≤c，裝載的農(nóng)產(chǎn)品重量與父結(jié)點(diǎn)A是一樣的，因此擴(kuò)展右子結(jié)點(diǎn)總是可行的。裝載問題給定任意狀態(tài)[wt，k]，怎么來判斷其子結(jié)點(diǎn)是否可能得出最優(yōu)解？限界函數(shù)剪枝過程：限界函數(shù)擴(kuò)展A結(jié)點(diǎn)的右子結(jié)點(diǎn)，xk+1=0，其右子結(jié)點(diǎn)B的狀態(tài)為[wt，k+1]。限界函數(shù)設(shè)裝載問題的解向量為X=[X1,X2]，其中X1=[x1,x2,...,xk,0]，X2=[xk+2,...,xn]。X1表示第1種農(nóng)產(chǎn)品到第k+1種農(nóng)產(chǎn)品的裝車情況，是目前已得到的農(nóng)產(chǎn)品裝車結(jié)果；X2表示從第k+2種農(nóng)產(chǎn)品到第n種農(nóng)產(chǎn)品的裝車情況，是還未考慮過的未知裝車結(jié)果。限界函數(shù)對(duì)于解向量X裝載農(nóng)產(chǎn)品的總重量：第1種農(nóng)產(chǎn)品到第k+1種農(nóng)產(chǎn)品裝入車后的重量為Wt(X1)=wt；第k+2種農(nóng)產(chǎn)品到第n種農(nóng)產(chǎn)品裝入車后的重量是未知的，用Wt(X2)表示。限界函數(shù)我們只能去估計(jì)Wt(X2)值的一個(gè)上界bound(X2)，上界函數(shù)bound(X2)≥Wt(X2)。bestw表示當(dāng)前已得到的最優(yōu)值，如果Wt(X1)+bound(X2)≤bestw，則表示當(dāng)前已裝車的農(nóng)產(chǎn)品總重量加上未裝車農(nóng)產(chǎn)品重量的上界值比當(dāng)前已知的最優(yōu)解值還要小。因此，可以判定以A為根的結(jié)點(diǎn)擴(kuò)展其右子結(jié)點(diǎn)是不可能得到問題的最優(yōu)解的，可以剪去A結(jié)點(diǎn)的右分支。限界函數(shù)那么，如何來估算bound(X2)呢？我們可以將未裝車的農(nóng)產(chǎn)品全部裝入，得到bound(X2)=這就是限界函數(shù)剪枝過程。限界函數(shù)限界函數(shù)分析過程，對(duì)于bestw值什么時(shí)候去獲?。咳绻凑栈厮菟惴ǚ治鲞^程，當(dāng)?shù)玫絾栴}第一個(gè)完整解向量時(shí)，將這個(gè)可行解的值記作第一個(gè)bestw的值。但是，得到完整向量的可行解需要搜索到解空間樹的葉子結(jié)點(diǎn)才能完成。限界函數(shù)對(duì)于基于廣度優(yōu)先搜索的分支限界法，只能對(duì)后續(xù)的葉子結(jié)點(diǎn)進(jìn)行限界函數(shù)剪枝，而剪枝對(duì)于葉子結(jié)點(diǎn)來說已經(jīng)沒有實(shí)際意義。因此，這樣獲取的bestw無實(shí)際效果。限界函數(shù)實(shí)際上，我們?cè)跀U(kuò)展任意結(jié)點(diǎn)k的左分支時(shí)，若其左分支是一個(gè)可行解，我們將該左子結(jié)點(diǎn)之后的農(nóng)產(chǎn)品裝載全部選擇不裝車，也可以得到一個(gè)完整的解向量，即[x1,,...,xk,1,{0}]。我們可以以這樣一個(gè)可行解的值作為bestw的值，因此，在擴(kuò)展左分支時(shí)，只要可行（車輛不超重），就及時(shí)更新bestw的值。裝載問題的約束限界函數(shù)（1）進(jìn)入左分支的約束函數(shù)：wt+wk+1≤c（2）進(jìn)入右分支的限界函數(shù)：wt+bound>bestw實(shí)例采用隊(duì)列式分支限界法搜索n=4種農(nóng)產(chǎn)品（c=10，W={6,7,2,4}，農(nóng)產(chǎn)品種編號(hào)1~4）的裝載問題，隊(duì)列中的結(jié)點(diǎn)元素如下列步驟中的各個(gè)圖所示。我們來定義一個(gè)結(jié)點(diǎn)元素(wt,bound,k):wt已裝入車了農(nóng)產(chǎn)品的重量bound剩余未裝車農(nóng)產(chǎn)品的總重量k當(dāng)前被處理農(nóng)產(chǎn)品種編號(hào)n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}

左子結(jié)點(diǎn)采用約束函數(shù)wt≤c=10作為剪枝策略右子結(jié)點(diǎn)采用限界函數(shù)wt+bound>bestw作為剪枝策略（1）初始結(jié)點(diǎn)1的三個(gè)數(shù)據(jù)項(xiàng)值為（0，19，0），即wt=0，bound=19，k=0。bestw初值為0。初始結(jié)點(diǎn)1入隊(duì)。1（0,19,0）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（2）取隊(duì)首結(jié)點(diǎn)1，擴(kuò)展它的左子結(jié)點(diǎn)2，wt=6<10，滿足約束條件是可行的，x1=1，結(jié)點(diǎn)2的三個(gè)數(shù)據(jù)項(xiàng)值為（6,13,1），結(jié)點(diǎn)2入隊(duì)，同時(shí)修改bestw=6。然后再來擴(kuò)展1的右子結(jié)點(diǎn)3，wt+bound=0+19>bestw=6，滿足限界條件是可行的，x1=0，結(jié)點(diǎn)3的三個(gè)數(shù)據(jù)項(xiàng)為（0,13,1），結(jié)點(diǎn)3入隊(duì)。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)1出隊(duì)。之后隊(duì)列情況：2（6,13,1），3（0,13,1）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（3）取隊(duì)首元素結(jié)點(diǎn)2，擴(kuò)展它的左子結(jié)點(diǎn)4，wt=6+7=13>10，不滿足約束條件，是不可行的，結(jié)點(diǎn)4被剪枝處理。然后再來擴(kuò)展它的右子結(jié)點(diǎn)5，wt+bound=6+6>bestw，滿足限界條件是可行的，x2=0，結(jié)點(diǎn)5的三個(gè)數(shù)據(jù)項(xiàng)為（6,6,2），結(jié)點(diǎn)5入隊(duì)。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)2出隊(duì)。之后隊(duì)列情況：3（0,13,1），5（6,6,2）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（4）取隊(duì)首結(jié)點(diǎn)3，擴(kuò)展它的左子結(jié)點(diǎn)6，wt=0+7<10，滿足約束條件是可行的，x2=1，結(jié)點(diǎn)6的三個(gè)數(shù)據(jù)項(xiàng)值為（7,6,2），結(jié)點(diǎn)6入隊(duì)，同時(shí)修改bestw=7。然后再來擴(kuò)展它的右子結(jié)點(diǎn)7，wt+bound=0+6<bestw=7，不滿足限界條件，是不可能產(chǎn)生最優(yōu)解的，結(jié)點(diǎn)7被剪枝處理。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)3出隊(duì)。之后隊(duì)列情況：5（6,6,2），6（7,6,2）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（5）取隊(duì)首結(jié)點(diǎn)5，擴(kuò)展它的左子結(jié)點(diǎn)10，wt=6+4=10，滿足約束條件是可行的，x3=1，結(jié)點(diǎn)10的三個(gè)數(shù)據(jù)項(xiàng)值為（10,2,3），結(jié)點(diǎn)10入隊(duì)，同時(shí)修改bestw=10。然后再來擴(kuò)展它的右子結(jié)點(diǎn)11，wt+bound=6+2<bestw=10，不滿足限界條件，是不可能產(chǎn)生最優(yōu)解的，結(jié)點(diǎn)11被剪枝處理。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)5出隊(duì)。之后隊(duì)列情況：6（7,6,2），10（10,2,3）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（6）取隊(duì)首結(jié)點(diǎn)6，擴(kuò)展它的左子結(jié)點(diǎn)12，wt=7+4>10，不滿足約束條件，是不可行的，結(jié)點(diǎn)12被剪枝處理。然后再來擴(kuò)展它的右子結(jié)點(diǎn)13，wt+bound=7+2<bestw=10，不滿足限界條件，是不可能產(chǎn)生最優(yōu)解的，結(jié)點(diǎn)13被剪枝處理。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)6出隊(duì)。之后隊(duì)列情況：10（10,2,3）n=4種農(nóng)產(chǎn)品：c=10，W={6,7,2,4}（7）取隊(duì)首結(jié)點(diǎn)10，擴(kuò)展它的左子結(jié)點(diǎn)20，wt=10+2>10，不滿足約束條件，是不可行的，結(jié)點(diǎn)20被剪枝處理。然后再來擴(kuò)展它的右子結(jié)點(diǎn)21，wt+bound=10+0=bestw=10，是一個(gè)最優(yōu)解的，結(jié)點(diǎn)21（10,0,4）為葉子結(jié)點(diǎn)，結(jié)點(diǎn)21入隊(duì)。左右子結(jié)點(diǎn)擴(kuò)展完畢，隊(duì)首結(jié)點(diǎn)10出隊(duì)。之后隊(duì)列情況：21（10,0,4）（8）取隊(duì)首結(jié)點(diǎn)21，發(fā)現(xiàn)已為葉子結(jié)點(diǎn)，不用進(jìn)行結(jié)點(diǎn)擴(kuò)展，結(jié)點(diǎn)21直接出隊(duì)。（9）隊(duì)列為空，循環(huán)結(jié)束。計(jì)算機(jī)算法設(shè)計(jì)與分析第7章分支限界法7.3.2單源最短路徑問題給定帶權(quán)有向圖G=(V,E),其中每條邊的權(quán)是非負(fù)實(shí)數(shù).另外,還給定V中的一個(gè)頂點(diǎn),稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路徑的長(zhǎng)度是指路徑上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。單源最短路徑問題如圖所示的有向圖G，每一條邊都有一個(gè)非負(fù)權(quán)值，求源點(diǎn)S到圖中各個(gè)結(jié)點(diǎn)之間的最短路徑。算法分析采用優(yōu)先隊(duì)列式分支限界法求解單源最短路徑問題，可以構(gòu)建一個(gè)基于結(jié)點(diǎn)優(yōu)先級(jí)的小根堆來存放活動(dòng)結(jié)點(diǎn)表：結(jié)點(diǎn)的優(yōu)先級(jí)=源點(diǎn)到該結(jié)點(diǎn)的當(dāng)前路徑長(zhǎng)度初始時(shí)源點(diǎn)到其余個(gè)結(jié)點(diǎn)之間距離長(zhǎng)度dist[i]設(shè)置為無窮大，當(dāng)然源點(diǎn)本身的dist[S]=0，并將源點(diǎn)S加入優(yōu)先隊(duì)列（小根堆）。圖的鄰接矩陣存儲(chǔ)到二維數(shù)組edge內(nèi)。算法分析從小根堆中取出堆頂元作為當(dāng)前擴(kuò)展結(jié)點(diǎn)i，并依次檢查與結(jié)點(diǎn)i相鄰結(jié)點(diǎn)j是否滿足下列條件：dist[i]+edge[i][j]<dist[j]則更新結(jié)點(diǎn)j的優(yōu)先級(jí)dist[j]=dist[i]+edge[i][j]，并將j結(jié)點(diǎn)加入小根堆（優(yōu)先隊(duì)列）。否則被舍去處理。重復(fù)上述過程，直到小根堆(優(yōu)先隊(duì)列)為空為止。Sijdist[i]edge[i][j]dist[j]實(shí)例（1）開始時(shí)小根堆只有源點(diǎn)S，取堆頂元S作為擴(kuò)展結(jié)點(diǎn)，與S相鄰的結(jié)點(diǎn)A，B，C，都滿足更新其優(yōu)先級(jí)條件，所以更新A、B、C的優(yōu)先級(jí)，將A、B、C結(jié)點(diǎn)加入小根堆，結(jié)點(diǎn)加入小根堆的過程中會(huì)重新調(diào)整建堆。dist[A]=dist[S]+edge[S][A]=2dist[B]=dist[S]+edge[S][B]=3dist[C]=dist[S]+edge[S][C]=4此時(shí)的解空間樹如下圖所示。SABC實(shí)例（2）取小根堆的堆頂元為A結(jié)點(diǎn)，與A相鄰的B、E、F結(jié)點(diǎn)：dist[A]+edge[A][B]>dist[B]，剪枝由A擴(kuò)展的B結(jié)點(diǎn)。dist[E]=dist[A]+edge[A][E]=2+2=4dist[F]=dist[A]+edge[A][F]=2+7=9更新結(jié)點(diǎn)E,F的優(yōu)先級(jí)并將其加入堆、重新調(diào)整建堆。此時(shí)的解空間樹如下圖所示。ABCBCEF實(shí)例（3）此時(shí)，小根堆（優(yōu)先隊(duì)列）的堆頂元為優(yōu)先級(jí)最小的結(jié)點(diǎn)B，與B相鄰的C、D、E，只有結(jié)點(diǎn)D滿足優(yōu)先級(jí)更新條件而加入到堆，加入堆的過程中會(huì)重新調(diào)整建堆。dist[D]=dist[B]+edge[B][D]=3+2=5由B擴(kuò)展的結(jié)點(diǎn)C、E被剪枝舍去。此時(shí)的解空間樹如下圖所示。BCEFCDEF實(shí)例（4）此時(shí)，堆頂元為優(yōu)先級(jí)最小的結(jié)點(diǎn)C，取堆頂元C,與C相鄰的結(jié)點(diǎn)D不滿足優(yōu)先級(jí)更新條件，剪枝由C擴(kuò)展的結(jié)點(diǎn)D。此時(shí)的解空間樹如下圖所示。CDEFEDF實(shí)例（5）此時(shí)，堆頂元為結(jié)點(diǎn)E，取堆頂元E,與E相鄰的D、H，E擴(kuò)展的結(jié)點(diǎn)D因不滿足優(yōu)先級(jí)更新條件被剪枝舍去，dist[H]=dist[E]+edge[E][H]=4+3=7結(jié)點(diǎn)H加入堆。此時(shí)的解空間樹如下圖所示。EDFDFH實(shí)例（6）取堆頂元結(jié)點(diǎn)D，與D相鄰的結(jié)點(diǎn)I和H，因結(jié)點(diǎn)H不滿足優(yōu)先級(jí)更新條件而被舍去，dist[I]=dist[D]+edge[D][H]=5+1=6結(jié)點(diǎn)I更新優(yōu)先級(jí)并加入堆。此時(shí)的解空間樹如下圖所示。DFHIFH實(shí)例（7）此時(shí)的堆頂元為結(jié)點(diǎn)I，取堆頂元I，與I相鄰的H、T,因I擴(kuò)展的結(jié)點(diǎn)H不滿足優(yōu)先級(jí)更新條件被剪枝舍去dist[T]=dist[I]+edge[I][T]=6+2=8更新結(jié)點(diǎn)T優(yōu)先級(jí)并加入堆。此時(shí)的解空間樹如圖所示。IFHHFT實(shí)例（8）此時(shí)，結(jié)點(diǎn)H具有最高優(yōu)先級(jí)成為當(dāng)前堆頂元，取堆頂元H,與H相鄰的G、T，由H擴(kuò)展的結(jié)點(diǎn)T不滿足優(yōu)先級(jí)更新條件被剪枝舍去;dist[G]=dist[H]+edge[H][G]=7+2=9結(jié)點(diǎn)G加入堆。此時(shí)的解空間樹如下圖所示。HFTTFG實(shí)例（9）此時(shí)，結(jié)點(diǎn)T為小根堆的堆頂元。此時(shí)，若問題是求解源點(diǎn)S到終點(diǎn)T的的最短路徑，則已得到問題的解，可以提前結(jié)束循環(huán)。若需要求源點(diǎn)到圖中所有結(jié)點(diǎn)的最短路徑長(zhǎng)度，則還需要繼續(xù)執(zhí)行，直到堆（優(yōu)先隊(duì)列）為空才結(jié)束循環(huán)。這時(shí)取堆頂元T,因T沒有出度邊的鄰結(jié)點(diǎn)，出堆后無操作。此時(shí)G成為當(dāng)前堆頂元，擴(kuò)展的結(jié)點(diǎn)T，且不滿足約束條件被剪枝舍去。此時(shí)的解空間樹如下圖所示。TFGGFF實(shí)例（10）到了此時(shí)，優(yōu)先隊(duì)列（堆）只剩下一個(gè)結(jié)點(diǎn)F，也是當(dāng)前堆頂元，其擴(kuò)展結(jié)點(diǎn)E、H和G，都不滿足更新優(yōu)先級(jí)條件被剪枝。此時(shí)的解空間樹如下圖所示。F空（11）此時(shí)優(yōu)先隊(duì)列（堆）為空，循環(huán)結(jié)束，至此單源最短路徑求解全部完成。計(jì)算機(jī)算法設(shè)計(jì)與分析第7章分支限界法7.3.3八數(shù)碼問題280163754123804765初始狀態(tài)

目標(biāo)狀態(tài)

隊(duì)列式分支限界法71234589610161718201519111213142