算法第5章-第4講-圖搜索-優(yōu)先隊列分枝限界法

1、第第4 4講講 優(yōu)先隊列分支限界法優(yōu)先隊列分支限界法每節(jié)一經(jīng)典每節(jié)一經(jīng)典有選擇地搜索有選擇地搜索3654789第第4 4講講 分支限界法分支限界法 上節(jié)課，我們介紹了上節(jié)課，我們介紹了3 3種不同的分支搜索方式：種不同的分支搜索方式：FIFOFIFO、LIFOLIFO、優(yōu)先隊列，詳細(xì)分析了、優(yōu)先隊列，詳細(xì)分析了FIFOFIFO搜索方式。搜索方式。 當(dāng)然用當(dāng)然用LIFOLIFO搜索方式也同樣可以設(shè)計出對應(yīng)的算法，搜索方式也同樣可以設(shè)計出對應(yīng)的算法，請同學(xué)們嘗試！請同學(xué)們嘗試！ 本節(jié)我們將詳細(xì)分析如何用優(yōu)先隊列分支限界法來本節(jié)我們將詳細(xì)分析如何用優(yōu)先隊列分支限界法來解決類似問題。解決類似問題。 優(yōu)

2、先隊列式分支限界法：優(yōu)先隊列式分支限界法：3654789搜索算法：搜索算法：分支搜索分支搜索 （例：深度優(yōu)先，廣度優(yōu)先，均為按深度或?qū)挾软樌荷疃葍?yōu)先，廣度優(yōu)先，均為按深度或?qū)挾软?序，在全部解空間搜索序，在全部解空間搜索）分支限界搜索分支限界搜索（例：與分枝搜索類似，并加入結(jié)點限制，對不例：與分枝搜索類似，并加入結(jié)點限制，對不 滿足條件的結(jié)點為根的分枝子樹不再滿足條件的結(jié)點為根的分枝子樹不再 進(jìn)行進(jìn)行 搜索搜索）優(yōu)先隊列分支限界搜索優(yōu)先隊列分支限界搜索例：在例：在分支限界搜索基礎(chǔ)上，分支限界搜索基礎(chǔ)上，對搜索結(jié)點的順序按優(yōu)先隊列組對搜索結(jié)點的順序按優(yōu)先隊列組織，使每一步搜索向最優(yōu)解目標(biāo)靠近，

3、不滿足條件的結(jié)點為根織，使每一步搜索向最優(yōu)解目標(biāo)靠近，不滿足條件的結(jié)點為根的分支子樹不再進(jìn)行搜索，遇到葉結(jié)點，即可得到一個解的分支子樹不再進(jìn)行搜索，遇到葉結(jié)點，即可得到一個解）第第4 4講講 分支限界法分支限界法p 優(yōu)先隊列組織：結(jié)點優(yōu)先級確定后優(yōu)先隊列組織：結(jié)點優(yōu)先級確定后, ,簡單地按結(jié)點優(yōu)先簡單地按結(jié)點優(yōu)先 級進(jìn)行排序級進(jìn)行排序, ,就生成了優(yōu)先隊列就生成了優(yōu)先隊列. .但是但是, ,排序算法的時間排序算法的時間 復(fù)雜度較高。復(fù)雜度較高。p 考慮到搜索算法每次只擴(kuò)展一個結(jié)點考慮到搜索算法每次只擴(kuò)展一個結(jié)點, ,數(shù)據(jù)結(jié)構(gòu)中堆排數(shù)據(jù)結(jié)構(gòu)中堆排 序方法適合這一特點序方法適合這一特點, ,并且元

4、素比較和交換的次數(shù)最少并且元素比較和交換的次數(shù)最少. . 堆堆通常有兩類：最大堆通常有兩類：最大堆( (根部的數(shù)最大根部的數(shù)最大, ,由大到小構(gòu)造由大到小構(gòu)造堆堆 ) )，最小堆最小堆(根部的數(shù)最小根部的數(shù)最小,由小到大構(gòu)造堆由小到大構(gòu)造堆 )，第第4 4講講 分支限界法分支限界法定義：堆定義：堆(heap)(heap)是一個滿足下列條件的完全二叉數(shù)：是一個滿足下列條件的完全二叉數(shù)： （1 1）父結(jié)點比其左、右兒子結(jié)點都大（或小）。）父結(jié)點比其左、右兒子結(jié)點都大（或?。?（2 2）左、右兒子分別是一個堆。）左、右兒子分別是一個堆。即：即：n n個元素的序列個元素的序列kk1 1,k,k2 2

5、, ,k kn n,當(dāng)且僅當(dāng)滿足：當(dāng)且僅當(dāng)滿足： kik2i kik2i kik2i+1 ki k2i+1 堆定義堆定義或或(i=1,2, n/2 )第第4 4講講 分支限界法分支限界法例：例：6 6，4 4，7 7，9 9構(gòu)造的大堆（從根到葉子數(shù)值減?。?gòu)造的大堆（從根到葉子數(shù)值減?。?47969749674無序序列無序序列4篩選后的狀態(tài)篩選后的狀態(tài)建建 堆堆6篩選后建成堆篩選后建成堆第第4 4講講 分支限界法分支限界法例例: 3,8,7,4,5,9,1,6: 3,8,7,4,5,9,1,6構(gòu)造的小堆構(gòu)造的小堆( (從根到葉子數(shù)值增大從根到葉子數(shù)值增大) )初始堆初始堆根節(jié)點根節(jié)點1出隊，最

6、后節(jié)點出隊，最后節(jié)點6做根節(jié)點位后的狀態(tài)做根節(jié)點位后的狀態(tài)出出 堆堆6和和3交換后的狀態(tài)交換后的狀態(tài)135478696354781913654789第第4 4講講 分支限界法分支限界法例例: 3,8,7,4,5,9,1,6: 3,8,7,4,5,9,1,6構(gòu)造的小堆構(gòu)造的小堆( (從根到葉子數(shù)值增大從根到葉子數(shù)值增大) )6和和4交換后的狀態(tài)交換后的狀態(tài)出出 堆堆34567891第第4 4講講 分支限界法分支限界法例例: 3,8,7,4,5,9,6: 3,8,7,4,5,9,6構(gòu)造的小堆構(gòu)造的小堆( (從根到葉子數(shù)值增大從根到葉子數(shù)值增大) )初始堆初始堆進(jìn)進(jìn) 堆堆1進(jìn)堆后建成新堆演示過程進(jìn)堆

7、后建成新堆演示過程3468597134685971新新堆堆建建成成第第4 4講講 分支限界法分支限界法 優(yōu)先隊列式搜索優(yōu)先隊列式搜索通過結(jié)點的優(yōu)先級通過結(jié)點的優(yōu)先級,可以使搜索盡快可以使搜索盡快朝著解空間樹上能朝著解空間樹上能到達(dá)最優(yōu)解的分支推進(jìn)到達(dá)最優(yōu)解的分支推進(jìn),這樣當(dāng)前最這樣當(dāng)前最優(yōu)解一定較接近真正的最優(yōu)解優(yōu)解一定較接近真正的最優(yōu)解. 其后，我們將當(dāng)前最優(yōu)解作為一個其后，我們將當(dāng)前最優(yōu)解作為一個“界界”,對上界對上界(或下界或下界)不可能達(dá)到不可能達(dá)到(大于大于)這個界的分支則不去進(jìn)行搜這個界的分支則不去進(jìn)行搜索索(結(jié)點不入隊結(jié)點不入隊),這樣就能縮小搜索范圍，從而提高搜這樣就能縮小搜索

8、范圍，從而提高搜索效率索效率. 這種搜索策略稱為這種搜索策略稱為優(yōu)先隊列優(yōu)先隊列分支限界分支限界法，簡稱法，簡稱LC-檢索檢索(Least Cost Search )。優(yōu)先隊列式分支限界法：優(yōu)先隊列式分支限界法：第第4 4講講 分支限界法分支限界法p 結(jié)點擴(kuò)展方式：無論那種分支限界法，都需要有一結(jié)點擴(kuò)展方式：無論那種分支限界法，都需要有一 張活結(jié)點表。優(yōu)先隊列分支限界法將張活結(jié)點表。優(yōu)先隊列分支限界法將活結(jié)點活結(jié)點組織組織成成 一個一個優(yōu)先隊列優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級級 選取優(yōu)先級最高的活結(jié)點成為當(dāng)前擴(kuò)展結(jié)點選取優(yōu)先級最高的活結(jié)點成為當(dāng)前擴(kuò)展結(jié)點.

9、 .p 結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級通常是結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級通常是 一個與該結(jié)點相關(guān)的數(shù)值一個與該結(jié)點相關(guān)的數(shù)值p, ,它一般表示其接近最它一般表示其接近最優(yōu)優(yōu) 解的程度，裝載問題就可以解的程度，裝載問題就可以當(dāng)前結(jié)點的裝載上界當(dāng)前結(jié)點的裝載上界為為 該結(jié)點的優(yōu)先級。該結(jié)點的優(yōu)先級。結(jié)點是否入隊判定標(biāo)準(zhǔn)：結(jié)點裝載上界結(jié)點是否入隊判定標(biāo)準(zhǔn)：結(jié)點裝載上界 當(dāng)前最優(yōu)方案當(dāng)前最優(yōu)方案bestw,bestw,并并且從該結(jié)點到根的裝載方案下，裝載量不超過船裝載量且從該結(jié)點到根的裝載方案下，裝載量不超過船裝載量c1c1優(yōu)先隊列式分支限界法算法設(shè)計要點：優(yōu)先隊列式分支限界法算法設(shè)計要

10、點：第第4 4講講 分支限界法分支限界法例如：例如：裝載問題裝載問題 W=10，30，50，c1=60， 所構(gòu)成的子集樹所構(gòu)成的子集樹如下圖所表示：如下圖所表示：方框中方框中紅色數(shù)紅色數(shù)表示表示 該結(jié)點的裝載上界，該結(jié)點的裝載上界，作為結(jié)點的優(yōu)先級。作為結(jié)點的優(yōu)先級。裝載上界裝載上界=已裝入物品重量已裝入物品重量+未來可能裝入物品的重量未來可能裝入物品的重量注意：已經(jīng)注意：已經(jīng)“處理處理”過的物品過的物品( (已判斷是否裝入已判斷是否裝入) )不再計不再計算算為未來可能裝入物品的重量。為未來可能裝入物品的重量。AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=

11、1X3=1X2=0X2=0X3=0X3=0X3=0X3=090909090606040108080805050300第第4 4講講 分支限界法分支限界法例例4.4.裝載問題裝載問題: :有三個貨物，其重量為有三個貨物，其重量為 W=10W=10，3030，5050，有，有2 2輛貨輛貨車，其載重量為車，其載重量為c1=60c1=60，c2=50,c2=50,問：是否有方案把所有貨物運(yùn)走？問：是否有方案把所有貨物運(yùn)走？關(guān)鍵概念：關(guān)鍵概念：(1)每個字母表示車當(dāng)前裝貨狀態(tài)。每個字母表示車當(dāng)前裝貨狀態(tài)。(2)當(dāng)前狀態(tài)下剩余裝載量當(dāng)前狀態(tài)下剩余裝載量 (ew)：當(dāng)前狀：當(dāng)前狀 態(tài)下剩余裝載量。態(tài)下剩余

12、裝載量。(3)當(dāng)前狀態(tài)下裝載量上界當(dāng)前狀態(tài)下裝載量上界：已裝入貨物：已裝入貨物 和未和未 來可能來可能 裝入的貨物總重量裝入的貨物總重量(排除排除 已打已打 算不裝入的貨物重量算不裝入的貨物重量)。(4)當(dāng)前狀態(tài)當(dāng)前狀態(tài)最優(yōu)已最優(yōu)已裝載上界裝載上界：截至目前：截至目前 狀狀 態(tài)態(tài)(包包 括目前狀態(tài)括目前狀態(tài))，所有已搜索的，所有已搜索的 局局 部裝載方案中的最大裝載量部裝載方案中的最大裝載量(已裝入已裝入 的的 最大重量最大重量)。裝裝50裝裝10裝裝30裝裝50裝裝50裝裝30裝裝50不裝不裝10不裝不裝30第第4 4講講 分支限界法分支限界法1 1） 初始隊列中只有結(jié)點初始隊列中只有結(jié)點A

13、 A；2 2） 結(jié)點結(jié)點A A變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充B B入隊入隊, ,bestwbestw=10;=10;結(jié)點結(jié)點C C的裝載上界為的裝載上界為 30+50=80 30+50=80bestwbestw，也入隊；也入隊；3 3） 結(jié)點結(jié)點B B變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充D D入隊入隊, ,bestwbestw=40;=40;結(jié)點結(jié)點E E的裝載上界為的裝載上界為 60 60bestwbestw，也入隊；也入隊；4 4） 結(jié)點結(jié)點C C變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充F F入隊入隊, ,bestwbestw仍為仍為40;40;結(jié)點結(jié)點G G的裝載上界為的裝載上界為 50 50be

14、stwbestw, ,也入隊；也入隊；5 5） 結(jié)點結(jié)點D D變?yōu)樽優(yōu)镋-E-結(jié)點結(jié)點, ,葉結(jié)點葉結(jié)點H H超過容量超過容量, ,不入隊；葉結(jié)點不入隊；葉結(jié)點I I的裝載上界的裝載上界 為為40=bestw=40,40=bestw=40,不入隊；不入隊；6 6） 結(jié)點結(jié)點E E變?yōu)樽優(yōu)镋-E-結(jié)點結(jié)點, ,葉結(jié)點葉結(jié)點J J裝載上界為裝載上界為60bestw=40, 60bestw=40, 入隊，并將入隊，并將 bestw bestw更新為更新為60;60;葉結(jié)點葉結(jié)點K K的裝載上界為的裝載上界為10bestw=40,不入隊不入隊,即即被被 剪掉；剪掉；7 7） 結(jié)點結(jié)點F F變?yōu)樽優(yōu)镋-

15、E-結(jié)點，葉結(jié)點結(jié)點，葉結(jié)點L L超過容量，不入隊，超過容量，不入隊，bestwbestw仍為仍為6060； 葉結(jié)點葉結(jié)點M M的裝載上界為的裝載上界為3030+50=80bestwbestw, ,也入堆也入堆; ;堆中堆中B B上界為上界為9090，在，在 優(yōu)先隊列之首優(yōu)先隊列之首; ;3 3） 結(jié)點結(jié)點B B變?yōu)樽優(yōu)镋-E-結(jié)點擴(kuò)充結(jié)點擴(kuò)充D D入堆入堆, ,bestwbestw=40;=40;結(jié)點結(jié)點E E的裝載的裝載 上界為上界為6060bestwbestw, ,也入堆也入堆; ;此時堆中此時堆中D D上界為上界為9090，在優(yōu)，在優(yōu) 先隊列之首先隊列之首; ;4 4） 結(jié)點結(jié)點D D

16、變?yōu)樽優(yōu)镋-E-結(jié)點結(jié)點, ,葉結(jié)點葉結(jié)點H H超過容量超過容量, ,葉結(jié)點葉結(jié)點I I的裝載的裝載 上界為上界為40=bestw=40,40=bestw=40,入堆入堆; ;此時堆中此時堆中C C上界為上界為8080， 在優(yōu)先隊列之首。在優(yōu)先隊列之首。分支限界分支限界(LC)-搜索的過程如下：搜索的過程如下：優(yōu)先隊列分枝限界搜優(yōu)先隊列分枝限界搜索索第第4 4講講 分支限界法分支限界法5） 結(jié)點結(jié)點C變?yōu)樽優(yōu)镋-結(jié)點擴(kuò)充結(jié)點擴(kuò)充F入堆入堆,bestw仍為仍為40; 結(jié)點結(jié)點G 的裝載上界為的裝載上界為50bestw,也入堆也入堆;此時堆中此時堆中E 上界為上界為 60，在優(yōu)先隊列之首。，在優(yōu)先

17、隊列之首。6） 結(jié)點結(jié)點E變?yōu)樽優(yōu)镋-結(jié)點結(jié)點,葉結(jié)點葉結(jié)點J裝載量為裝載量為60，入堆，入堆, bestw變?yōu)樽優(yōu)?0; 葉結(jié)點葉結(jié)點K上界為上界為10parent=E; b-LChil = ch; HeapNode N; N.uweight = wt; N.level=lev; N.ptr=b; Insert(H，N) ; 第第4 4講講 分支限界法分支限界法 MaxLoading(float c, int n, int bestx)froat r100,Ew,bestw=0; rn = 0; For ( int j = n-1; j 0; j-) rj=rj+1 + wj+1; Int

18、i = 1; bbnode *E = 0; Ew = 0; / 搜索子集空間樹搜索子集空間樹while (i != n+1) / 不在葉子上不在葉子上 if ( Ew + wi = c) / 可行的左孩子可行的左孩子 AddLiveNode(E,Ew+wi+ri, 1, i+1); if (bestwEw+wi) bestw=Ew+wi; if( bestw 0; j-) bestxj = E-LChild; E = E-parent; return Ew; 第第4 4講講 分支限界法分支限界法 算法的復(fù)雜度仍為算法的復(fù)雜度仍為O(2O(2n n) )。但通過限界策略。但通過限界策略, ,并沒

19、有并沒有搜索子集樹中的所有結(jié)點搜索子集樹中的所有結(jié)點, ,由于每次都是選取的最接近由于每次都是選取的最接近最優(yōu)解的結(jié)點擴(kuò)展，所以一旦搜索到葉結(jié)點作最優(yōu)解的結(jié)點擴(kuò)展，所以一旦搜索到葉結(jié)點作E E結(jié)點時結(jié)點時算法就可以結(jié)束了算法就可以結(jié)束了, ,所以算法實際執(zhí)行時復(fù)雜度遠(yuǎn)遠(yuǎn)低所以算法實際執(zhí)行時復(fù)雜度遠(yuǎn)遠(yuǎn)低于于O(2n). .需要說明的是需要說明的是, ,算法結(jié)束時堆并不一定為空。算法結(jié)束時堆并不一定為空。 算法分析：算法分析：第第4 4講講 分支限界法分支限界法 FIFO限界算法搜索解空間的過程是按廣度優(yōu)先搜限界算法搜索解空間的過程是按廣度優(yōu)先搜索子集樹過程中生成的一般隊列的元素順序，搜索最索子集

20、樹過程中生成的一般隊列的元素順序，搜索最優(yōu)解，而優(yōu)先隊列限界搜索解空間的過程是按動搜索優(yōu)解，而優(yōu)先隊列限界搜索解空間的過程是按動搜索過程中態(tài)構(gòu)造的優(yōu)先隊列的首結(jié)點順序搜索最優(yōu)解。過程中態(tài)構(gòu)造的優(yōu)先隊列的首結(jié)點順序搜索最優(yōu)解。 看了上面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列法擴(kuò)展結(jié)點看了上面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列法擴(kuò)展結(jié)點的過程，一開始實際是在進(jìn)行類似的過程，一開始實際是在進(jìn)行類似“深度優(yōu)先深度優(yōu)先”的搜的搜索。索。第第4 4講講 分支限界法分支限界法p FIFO FIFO搜索或搜索或LIFOLIFO搜索也可以通過加入搜索也可以通過加入“限界限界”策略策略加加 速搜索嗎速搜索嗎? ?與優(yōu)先隊列式分支限界

21、法與優(yōu)先隊列式分支限界法LC檢索的檢索的 區(qū)別在哪兒呢？區(qū)別在哪兒呢？p 答案：由于答案：由于FIFO搜索或搜索或LIFO搜索是盲目擴(kuò)展結(jié)點搜索是盲目擴(kuò)展結(jié)點, 當(dāng)前最優(yōu)解距真正的最優(yōu)解距離較大當(dāng)前最優(yōu)解距真正的最優(yōu)解距離較大,作為作為“界界”所所起起 到的剪枝作用很有限到的剪枝作用很有限,不能有效提高搜索速度不能有效提高搜索速度p 其實其實,優(yōu)先隊列式擴(kuò)展結(jié)優(yōu)先隊列式擴(kuò)展結(jié) 點的過程，一開始實際是點的過程，一開始實際是在進(jìn)行類似在進(jìn)行類似“深度優(yōu)先深度優(yōu)先” 的的 搜索。搜索。討論：討論：第第4 4講講 分支限界法分支限界法 上一小節(jié)的例子是求最大值的最優(yōu)化問題，下面我們上一小節(jié)的例子是求最

22、大值的最優(yōu)化問題，下面我們以求解以求解”最小成本最小成本“的最優(yōu)化問題為例，給出的最優(yōu)化問題為例，給出FIFO分支分支搜索算法框架。搜索算法框架。 假定問題解空間樹為假定問題解空間樹為T,T至少包含一個解結(jié)點（即答至少包含一個解結(jié)點（即答案結(jié)點）案結(jié)點）. .u為當(dāng)前的最優(yōu)解為當(dāng)前的最優(yōu)解, ,初值為一個較大的數(shù)初值為一個較大的數(shù);E;E表示表示當(dāng)前擴(kuò)展的活結(jié)點當(dāng)前擴(kuò)展的活結(jié)點, ,x為為E E的兒子的兒子, ,s(x)為結(jié)點為結(jié)點x x下界函數(shù)下界函數(shù), ,當(dāng)當(dāng)其值比其值比u u大時大時, ,不可能為最優(yōu)解不可能為最優(yōu)解, ,不繼續(xù)搜索此分支不繼續(xù)搜索此分支, ,該結(jié)點該結(jié)點不入隊不入隊;

23、;當(dāng)其值比當(dāng)其值比u u小時小時, ,可能達(dá)到最優(yōu)解可能達(dá)到最優(yōu)解, ,繼續(xù)搜索此分支繼續(xù)搜索此分支, ,該結(jié)點入隊該結(jié)點入隊; ;cost(X)為當(dāng)前葉結(jié)點所在分支的解。為當(dāng)前葉結(jié)點所在分支的解。 舉一反三：舉一反三：找最小成本的分枝限界法和優(yōu)先隊列分枝限界法找最小成本的分枝限界法和優(yōu)先隊列分枝限界法第第4 4講講 分支限界法分支限界法search（T） /為找出最小成本答案結(jié)點檢索為找出最小成本答案結(jié)點檢索T T。 leaf=0; 初始化隊；初始化隊；ADDQ（T）；）； /根結(jié)點入隊根結(jié)點入隊 parent（E）=0； /記錄擴(kuò)展路徑，當(dāng)前結(jié)點的父結(jié)點記錄擴(kuò)展路徑，當(dāng)前結(jié)點的父結(jié)點 wh

24、ile （隊不空）隊不空）DELETEQ(E) /隊首結(jié)點出隊為新的隊首結(jié)點出隊為新的E E結(jié)點；結(jié)點；for （E E的每個兒子的每個兒子 X X） if (s（X）u) /當(dāng)是可能的最優(yōu)解時入隊當(dāng)是可能的最優(yōu)解時入隊 ADD Q（X）；）； parent（X）=E; if (X是解結(jié)點是解結(jié)點 ) /x/x為葉結(jié)點為葉結(jié)點 U=min（cost（X），），u）; leaf=x; /方案的葉結(jié)點存儲在方案的葉結(jié)點存儲在leafleaf中中 FIFO算法框架：算法框架：第第4 4講講 分支限界法分支限界法 print（”least cost=，u）；）； while （leaf0） /輸出最優(yōu)

25、解方案輸出最優(yōu)解方案 print（leaf）；）； leaf=parent（leaf）；）；第第4 4講講 分支限界法分支限界法 找最小成本的找最小成本的LC分支分支- -限界算法限界算法框架框架與與FIFO分支分支- -限限界算法界算法框架結(jié)構(gòu)大致相同，只是擴(kuò)展結(jié)點的順序不同，框架結(jié)構(gòu)大致相同，只是擴(kuò)展結(jié)點的順序不同，因而存儲活結(jié)點的數(shù)據(jù)結(jié)構(gòu)不同。因而存儲活結(jié)點的數(shù)據(jù)結(jié)構(gòu)不同。FIFO分支分支- -限界算限界算法用法用隊列隊列存儲活結(jié)點，存儲活結(jié)點，LC分枝分枝- -限界算法用限界算法用堆堆存儲活存儲活結(jié)點，以保證比較優(yōu)良的結(jié)點先被擴(kuò)展。且對于結(jié)點，以保證比較優(yōu)良的結(jié)點先被擴(kuò)展。且對于LCL

26、C分分支支- -限界算法，一旦擴(kuò)展到葉結(jié)點就已經(jīng)找到最優(yōu)解，限界算法，一旦擴(kuò)展到葉結(jié)點就已經(jīng)找到最優(yōu)解，可以停止搜索?？梢酝Ｖ顾阉?。而用而用FIFOFIFO算法需要隊列為空時才可以算法需要隊列為空時才可以停止搜索。停止搜索。找最小成本的找最小成本的LC分支分支-限界算法限界算法第第4 4講講 分支限界法分支限界法例例5：單源最短路徑問題（：單源最短路徑問題（LC算法）算法）給定帶權(quán)有向圖給定帶權(quán)有向圖G =(V,E),G =(V,E),其中每條邊的權(quán)是非負(fù)其中每條邊的權(quán)是非負(fù)實數(shù)實數(shù). .另外另外, ,還給定還給定V V中的一個頂點中的一個頂點, ,稱為源?，F(xiàn)在要計稱為源?，F(xiàn)在要計算從源到所有

27、其它各頂點的最短路長度。這里路的長算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為度是指路上各邊權(quán)之和。這個問題通常稱為單源最短單源最短路徑問題路徑問題。ISabcdefghijlmnopqrtu第第2 2講講 分支限界法分支限界法ISabcdefghilmnopqrtuj下面以一個例子來說明單源最短路徑問題下面以一個例子來說明單源最短路徑問題: :在有向圖在有向圖G G中中, ,每一邊都有一個非負(fù)邊權(quán)。求從源頂點每一邊都有一個非負(fù)邊權(quán)。求從源頂點I I到目標(biāo)頂點到目標(biāo)頂點S S之之間的最短路徑。間的最短路徑。單源最短路徑問題單源最短路徑問題具體問題實例具體

28、問題實例：IS2342239279l35122871ABCDEFGHJ用用優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法解有向解有向圖圖G G的單源最短路徑問題產(chǎn)生的解的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長字表示該結(jié)點所對應(yīng)的當(dāng)前路長I2342239279l35122871ABCDEFGHJI活節(jié)點入堆活節(jié)點入堆（解空間樹生成過程）（解空間樹生成過程）根節(jié)點出堆根節(jié)點出堆IIABC對出堆節(jié)點擴(kuò)展對出堆節(jié)點擴(kuò)展234構(gòu)造堆構(gòu)造堆A2B3C4A2B3C4判斷判斷B,E,F是否入堆是否入堆(只有只有E,F可入可入)注：判斷注：判斷A的

29、子節(jié)點的子節(jié)點E是否入堆的方法：從源是否入堆的方法：從源點經(jīng)過點經(jīng)過A到到E的路徑長度如果小于經(jīng)過目前解的路徑長度如果小于經(jīng)過目前解空間樹上從源點到空間樹上從源點到E的其他最短路徑長度，的其他最短路徑長度，則則E入堆，否則入堆，否則E不入堆。判定其他節(jié)點入堆不入堆。判定其他節(jié)點入堆的方法與此相同。的方法與此相同。用用優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法解有向解有向圖圖G G的單源最短路徑問題產(chǎn)生的解的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長字表示該結(jié)點所對應(yīng)的當(dāng)前路長I2342239279l35122871ABCDEFGH

30、J活節(jié)點入堆活節(jié)點入堆（解空間樹生成過程）（解空間樹生成過程）根節(jié)點出堆根節(jié)點出堆IABC對出堆節(jié)點擴(kuò)展對出堆節(jié)點擴(kuò)展234B3C4整理堆整理堆判斷判斷B,E,F是是否入堆否入堆B3C4E4F9B3EFD判斷判斷E,D是否入堆是否入堆(只有只有D可入可入)注：判斷注：判斷B的子節(jié)點的子節(jié)點E是否入堆的方法：從源點經(jīng)過是否入堆的方法：從源點經(jīng)過B到到E的路徑長度的路徑長度(12)如果小于經(jīng)過目前解空間樹上從源點到如果小于經(jīng)過目前解空間樹上從源點到E的其他最短路徑長度的其他最短路徑長度(4)，則則E入堆，否則入堆，否則E不入堆。不入堆。 判定其他節(jié)點入堆的方法與此相同。判定其他節(jié)點入堆的方法與此相

31、同。C4F9E4構(gòu)造堆構(gòu)造堆272用用優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法解有向解有向圖圖G G的單源最短路徑問題產(chǎn)生的解的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長字表示該結(jié)點所對應(yīng)的當(dāng)前路長I2342239279l35122871ABCDEFGHJ活節(jié)點入堆活節(jié)點入堆（解空間樹生成過程）（解空間樹生成過程）根節(jié)點出堆根節(jié)點出堆IABC對出堆節(jié)點擴(kuò)展對出堆節(jié)點擴(kuò)展234整理整理為堆為堆判斷判斷D是否是否入堆入堆（不）（不）C4E4F9C4EFDD5C4E4D5F9整理為堆E4D5F9整理為堆注：判斷注：判斷C的子節(jié)點的子節(jié)

32、點D是否入堆的方法：從源點經(jīng)過是否入堆的方法：從源點經(jīng)過C到到D的路徑長度的路徑長度(6)如果小于經(jīng)過目前解空間樹上其他源點到如果小于經(jīng)過目前解空間樹上其他源點到D的最短路徑長度的最短路徑長度(5)，則，則E入入堆，否則堆，否則D不入堆。不入堆。 D不入堆不入堆272用用優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法解有向解有向圖圖G G的單源最短路徑問題產(chǎn)生的解的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長字表示該結(jié)點所對應(yīng)的當(dāng)前路長I2342239279l35122871ABCDEFGHJ活節(jié)點入堆活節(jié)點入堆（解空間樹生成過程）（解

33、空間樹生成過程）根節(jié)點出堆根節(jié)點出堆IABC對出堆節(jié)點擴(kuò)展對出堆節(jié)點擴(kuò)展234判斷判斷H,D是否是否入堆入堆（H入）入）EFDE4D5F9整理為堆E4HD5F9H7D5判斷判斷H,J是否入是否入堆堆（J入）入）J整理為堆J6F9H7整理為堆D5F9D5F9H7H入入2721用用優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法解有向解有向圖圖G G的單源最短路徑問題產(chǎn)生的解的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長字表示該結(jié)點所對應(yīng)的當(dāng)前路長I2342239279l35122871ABCDEFGHJ活節(jié)點入堆活節(jié)點入堆（解空間樹生成過程

34、）（解空間樹生成過程）根節(jié)點出堆根節(jié)點出堆IABC對出堆節(jié)點擴(kuò)展對出堆節(jié)點擴(kuò)展234判斷判斷H,S是否入是否入堆堆（S入）入）EFD整理為堆HJJ6F9H7J6SH7F9S8H7判斷判斷S是否入堆是否入堆（S不入）不入）整理為堆S8F9S8因因S是葉子，結(jié)束；是葉子，結(jié)束；最優(yōu)解從最優(yōu)解從S到到I272312第第4 4講講 分支限界法分支限界法 while (true) / 搜索問題的解空間搜索問題的解空間 for (int j=1;j=n;j+) (cE.ijinf)&(E.length+cE.ijdistj) / 頂點頂點i到頂點到頂點j可達(dá)，且滿足控制約束可達(dá)，且滿足控制約束 distj

35、=enode.length+aenode.ij; pj=enode.i; HeapNode node = new HeapNode(j,distj); heap.put(node); / 加入活結(jié)點優(yōu)先隊列加入活結(jié)點優(yōu)先隊列 if (heap.isEmpty() break; else enode = (HeapNode) heap.removeMin();算法設(shè)計算法設(shè)計頂點頂點I I和和j j間有邊，且間有邊，且此路徑長小于原先從此路徑長小于原先從原點到原點到j(luò) j的路徑長的路徑長 (偽代碼偽代碼)第第4 4講講 分支限界法分支限界法動態(tài)規(guī)劃解單源最短路徑動態(tài)規(guī)劃解單源最短路徑p 由于圖的

36、關(guān)系復(fù)雜而無序由于圖的關(guān)系復(fù)雜而無序, ,一般難以呈現(xiàn)階段特征一般難以呈現(xiàn)階段特征( (除除 了特殊的圖，如多段圖了特殊的圖，如多段圖-參見參見例例5 5),),因此動態(tài)規(guī)劃在圖因此動態(tài)規(guī)劃在圖 論中的應(yīng)用不多論中的應(yīng)用不多. .但有一類圖但有一類圖, ,它的頂點卻是有序的它的頂點卻是有序的, ,這這 就是無環(huán)有向圖。就是無環(huán)有向圖。p 在無環(huán)有向圖中在無環(huán)有向圖中, ,我們可以對點進(jìn)行拓?fù)渑判蛭覀兛梢詫c進(jìn)行拓?fù)渑判? ,使其體使其體 現(xiàn)出有序的特征現(xiàn)出有序的特征, ,據(jù)此劃分階段據(jù)此劃分階段. .在有向無環(huán)圖中求最在有向無環(huán)圖中求最 短路徑的算法短路徑的算法, ,體現(xiàn)出簡單的動態(tài)規(guī)劃思想體

37、現(xiàn)出簡單的動態(tài)規(guī)劃思想. .請看下面請看下面 的例子。的例子。例例 5:單源最短路徑問題單源最短路徑問題 已知從已知從A A到到S S的路線及費(fèi)用如下圖，求從的路線及費(fèi)用如下圖，求從A A到到S S的最小的最小費(fèi)用路線。費(fèi)用路線。A32745542BCEFGS3第第4 4講講 單源最短路徑單源最短路徑第第4 4講講 單源最短路徑單源最短路徑問題的分析問題的分析A32745542BCEFGS3 枚舉搜索圖中的每條路徑，但當(dāng)圖的規(guī)模較大時，搜枚舉搜索圖中的每條路徑，但當(dāng)圖的規(guī)模較大時，搜索的效率顯然不盡人意。索的效率顯然不盡人意。 試用動態(tài)規(guī)劃的思路分析這道題試用動態(tài)規(guī)劃的思路分析這道題: :從圖

38、中可以看到從圖中可以看到,A,A點要到達(dá)點要到達(dá)S S點必然要經(jīng)過點必然要經(jīng)過B B和和C C中的一個中的一個, ,所以所以A A到到S S的最的最短距離必然等于短距離必然等于B B到到S S的最短距離加上的最短距離加上5,5,或是或是C C到到S S的最的最短距離加上短距離加上2.2.同樣同樣,B,B到到S S的最短距離等于的最短距離等于E E到到S S的最短的最短距離加上距離加上3 3或是或是F F到到S S的最短距離加上的最短距離加上2,2,. .第第4 4講講 單源最短路徑單源最短路徑 設(shè)設(shè)Gi為點為點i到點到點S的距離的距離,顯顯GE=4,GF=3,GG=5,根據(jù)上面的分析根據(jù)上面的

39、分析,有：有： GB=minGE+3，GF+2=5， GC=minGF+7，GG+4=9， GA=minGB+5，GC+2=10， 所以所以A到到S的最短距離是的最短距離是10，最短路徑，最短路徑ABFSA32745542BCEFGS3第第4 4講講 單源最短路徑單源最短路徑 階段階段: :我們按虛線所示來劃分階段我們按虛線所示來劃分階段, ,按按1,2,3,41,2,3,4的順序的順序來逐階段求解子問題來逐階段求解子問題. .因為只有前一階段的所有子問因為只有前一階段的所有子問題計算了題計算了, ,才能正確計算當(dāng)前階段的子問題才能正確計算當(dāng)前階段的子問題, ,所以這樣所以這樣的劃分是正確合理

40、的。的劃分是正確合理的。劃分階段劃分階段A32745542BCEFGS3階段階段1階段階段4 階段階段3階段階段2第第4 4講講 單源最短路徑單源最短路徑狀態(tài)：狀態(tài)可看成一個階段中的多個子問題。第狀態(tài)：狀態(tài)可看成一個階段中的多個子問題。第1個階個階段有一個狀態(tài)即段有一個狀態(tài)即S，第，第2個階段是三個狀態(tài)個階段是三個狀態(tài)E，F(xiàn)和和G，而第而第3個階段有兩個狀態(tài)個階段有兩個狀態(tài)B和和C，第，第4個階段只有一個狀個階段只有一個狀態(tài)態(tài)A。A32745542BCEFGS3狀態(tài)狀態(tài)4狀態(tài)狀態(tài)3狀態(tài)狀態(tài)2狀態(tài)狀態(tài)1第第4 4講講 單源最短路徑單源最短路徑A32745542BCEFGS3決策：決策就是狀態(tài)轉(zhuǎn)移

41、。狀態(tài)轉(zhuǎn)移方程：決策：決策就是狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移方程： G(i)=minG(j) + Aij ，j=1,n, n是從節(jié)點是從節(jié)點i一步可達(dá)的節(jié)點個數(shù)，即節(jié)點一步可達(dá)的節(jié)點個數(shù)，即節(jié)點i的直接鄰居節(jié)的直接鄰居節(jié)點個數(shù)。點個數(shù)。Aij表示從表示從i到到j(luò)的一步可達(dá)線段長度。的一步可達(dá)線段長度。GC=minGF+7，GG+4=9，第第4 4講講 單源最短路徑單源最短路徑Step1 :real COST(n), integer D(n-1),P(k), r, j, k, n COST(n)0Step2: for jn-1 to 1 by -1 do 設(shè)設(shè)r是一個這樣的結(jié)點，是一個這樣的結(jié)點，E且使且使

42、c(j, r) +COST(r)取最小值。取最小值。Step3: COST（j）c(j, r)+COST(r)Step4: D(j) rStep5: repeatStep6: P(1) 1;P(k) nStep7: for j2 to k-1 doStep8: P(j) D(P(j-1)Step9: repeatStep10: end FGRAPH第第4 4講講 分支限界法分支限界法p 回溯法以深度優(yōu)先的方式搜索解空間樹回溯法以深度優(yōu)先的方式搜索解空間樹T，而分支而分支 限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先（優(yōu)先隊列）限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先（優(yōu)先隊列） 的方式搜索解空間樹的方式搜索解

43、空間樹T。p 由于它們在問題的解空間樹由于它們在問題的解空間樹T上搜索的方法不同上搜索的方法不同, ,適適 合解決的問題也就不同。合解決的問題也就不同。p 一般情況下一般情況下, ,回溯法的求解目標(biāo)是找出回溯法的求解目標(biāo)是找出T中滿足約束中滿足約束 條件的條件的所有解的方案所有解的方案，而分支限界法的求解目標(biāo)則，而分支限界法的求解目標(biāo)則 是找出是找出滿足約束條件的一個最優(yōu)解滿足約束條件的一個最優(yōu)解，或是在滿足約，或是在滿足約 束條件的解中找出使用某一目標(biāo)函數(shù)值達(dá)到極大或束條件的解中找出使用某一目標(biāo)函數(shù)值達(dá)到極大或 極小的解，即在某種意義下的最優(yōu)解。極小的解，即在某種意義下的最優(yōu)解。圖的搜索算法

44、小結(jié)圖的搜索算法小結(jié)回溯與分支限界法回溯與分支限界法第第4 4講講 分支限界法分支限界法p 相對而言相對而言,分支限界算法的解空間比回溯法大得多分支限界算法的解空間比回溯法大得多, 因此當(dāng)內(nèi)存容量有限時因此當(dāng)內(nèi)存容量有限時,回溯法成功的可能性更大?；厮莘ǔ晒Φ目赡苄愿蟆?回溯法和分支限界法區(qū)別：回溯法和分支限界法區(qū)別：方方法法搜索方法搜索方法數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)節(jié)點存儲特性節(jié)點存儲特性應(yīng)用應(yīng)用回回溯溯深度優(yōu)先搜索深度優(yōu)先搜索堆棧堆?；罟?jié)點的所有可活節(jié)點的所有可行子節(jié)點被遍歷行子節(jié)點被遍歷后才被棧中彈出后才被棧中彈出滿足約束滿足約束 條件的所條件的所有解的方案有解的方案分分支支限限界界廣度優(yōu)先搜索

45、廣度優(yōu)先搜索或者最小消耗或者最小消耗優(yōu)先搜索優(yōu)先搜索隊列隊列、優(yōu)、優(yōu)先隊先隊列列每個節(jié)點只有一每個節(jié)點只有一次成為活節(jié)點的次成為活節(jié)點的機(jī)會機(jī)會滿足約束條件的一滿足約束條件的一個解個解,或者在某種意或者在某種意義下的最優(yōu)解義下的最優(yōu)解第第4 4講講 分支限界法分支限界法p 采用窮舉法、回溯法或分支限界法都可以通過利用當(dāng)采用窮舉法、回溯法或分支限界法都可以通過利用當(dāng) 前最優(yōu)解和上界函數(shù)加速。前最優(yōu)解和上界函數(shù)加速。p 僅對限界剪枝的效率而言，優(yōu)先隊列分支限界法顯僅對限界剪枝的效率而言，優(yōu)先隊列分支限界法顯 然要更充分一些。然要更充分一些。p 在窮舉法中通過上界函數(shù)與當(dāng)前情況下函數(shù)值的比在窮舉法中

46、通過上界函數(shù)與當(dāng)前情況下函數(shù)值的比 較，可以直接略過不合要求的情況而省去了更進(jìn)一步較，可以直接略過不合要求的情況而省去了更進(jìn)一步 的枚舉和判斷；的枚舉和判斷；p 回溯法則因為層次的劃分，可以在上界函數(shù)值小于當(dāng)回溯法則因為層次的劃分，可以在上界函數(shù)值小于當(dāng) 前最優(yōu)解時，剪去以該結(jié)點為根的子樹，也就節(jié)省了前最優(yōu)解時，剪去以該結(jié)點為根的子樹，也就節(jié)省了 搜索范圍；搜索范圍；第第4 4講講 分支限界法分支限界法p 分支限界法在這方面除了可以做到回溯法能做到的之分支限界法在這方面除了可以做到回溯法能做到的之外，同時若采用優(yōu)先隊列的分支限界法，用上界函數(shù)作外，同時若采用優(yōu)先隊列的分支限界法，用上界函數(shù)作為

47、活結(jié)點的優(yōu)先級，一旦有葉結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，為活結(jié)點的優(yōu)先級，一旦有葉結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，就意味著該葉結(jié)點所對應(yīng)的解即為最優(yōu)解，可以立即終就意味著該葉結(jié)點所對應(yīng)的解即為最優(yōu)解，可以立即終止其余的過程。止其余的過程。p在前面的例題中曾說明，優(yōu)先隊列的分支限界法更象是在前面的例題中曾說明，優(yōu)先隊列的分支限界法更象是有選擇、有目的地進(jìn)行有選擇、有目的地進(jìn)行深度優(yōu)先搜索深度優(yōu)先搜索，時間效率、空間效，時間效率、空間效率都是比較高的。率都是比較高的。第第4 4講講 分支限界法分支限界法p 撇開時空效率的因素不談，在解決最優(yōu)化問題的算撇開時空效率的因素不談，在解決最優(yōu)化問題的算 法中，搜索可以說是法中，搜索可以說是“萬能萬能”的。所以動態(tài)規(guī)劃可的。所以動態(tài)規(guī)劃可以以 解決的問題，搜索也一定可以解決。解決的問題，搜索也一定可以解決。p 動態(tài)規(guī)劃要求階段決策具有無后向性，而搜索算法沒動態(tài)規(guī)劃要求階段決策具有無后向性，而搜索算法沒 有此限制。有此限制。p 動態(tài)規(guī)劃是動態(tài)規(guī)劃是自底向上自底向上或或自頂向下自頂向下的遞推求解，而無論的遞推求解，而無論 深度優(yōu)先搜索或廣度優(yōu)先搜索都是自頂向下求解。深度優(yōu)先搜索或廣度優(yōu)先搜索都是自頂向下求解。 動態(tài)規(guī)劃與搜索算法動態(tài)規(guī)劃與搜索算法第第4 4講講 分支限界法分支限界法利用動態(tài)規(guī)劃法進(jìn)行算