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

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

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

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

4、素比較和交換的次數(shù)最少并且元素比較和交換的次數(shù)最少. . 堆堆通常有兩類(lèi)：最大堆通常有兩類(lèi)：最大堆( (根部的數(shù)最大根部的數(shù)最大, ,由大到小構(gòu)造由大到小構(gòu)造堆堆 ) )，最小堆最小堆(根部的數(shù)最小根部的數(shù)最小,由小到大構(gòu)造堆由小到大構(gòu)造堆 )，第第4 4講講 分支限界法分支限界法定義：堆定義：堆(heap)(heap)是一個(gè)滿足下列條件的完全二叉數(shù)：是一個(gè)滿足下列條件的完全二叉數(shù)： （1 1）父結(jié)點(diǎn)比其左、右兒子結(jié)點(diǎn)都大（或?。＃└附Y(jié)點(diǎn)比其左、右兒子結(jié)點(diǎn)都大（或?。?。 （2 2）左、右兒子分別是一個(gè)堆。）左、右兒子分別是一個(gè)堆。即：即：n n個(gè)元素的序列個(gè)元素的序列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無(wú)序序列無(wú)序序列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é)點(diǎn)根節(jié)點(diǎn)1出隊(duì)，最

6、后節(jié)點(diǎn)出隊(duì)，最后節(jié)點(diǎn)6做根節(jié)點(diǎn)位后的狀態(tài)做根節(jié)點(diǎn)位后的狀態(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)堆后建成新堆演示過(guò)程進(jìn)堆

7、后建成新堆演示過(guò)程3468597134685971新新堆堆建建成成第第4 4講講 分支限界法分支限界法 優(yōu)先隊(duì)列式搜索優(yōu)先隊(duì)列式搜索通過(guò)結(jié)點(diǎn)的優(yōu)先級(jí)通過(guò)結(jié)點(diǎn)的優(yōu)先級(jí),可以使搜索盡快可以使搜索盡快朝著解空間樹(shù)上能朝著解空間樹(shù)上能到達(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)解作為一個(gè)其后，我們將當(dāng)前最優(yōu)解作為一個(gè)“界界”,對(duì)上界對(duì)上界(或下界或下界)不可能達(dá)到不可能達(dá)到(大于大于)這個(gè)界的分支則不去進(jìn)行搜這個(gè)界的分支則不去進(jìn)行搜索索(結(jié)點(diǎn)不入隊(duì)結(jié)點(diǎn)不入隊(duì)),這樣就能縮小搜索范圍，從而提高搜這樣就能縮小搜索

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

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

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

11、1X3=1X2=0X2=0X3=0X3=0X3=0X3=090909090606040108080805050300第第4 4講講 分支限界法分支限界法例例4.4.裝載問(wèn)題裝載問(wèn)題: :有三個(gè)貨物，其重量為有三個(gè)貨物，其重量為 W=10W=10，3030，5050，有，有2 2輛貨輛貨車(chē)，其載重量為車(chē)，其載重量為c1=60c1=60，c2=50,c2=50,問(wèn)：是否有方案把所有貨物運(yùn)走？問(wèn)：是否有方案把所有貨物運(yùn)走？關(guān)鍵概念：關(guān)鍵概念：(1)每個(gè)字母表示車(chē)當(dāng)前裝貨狀態(tài)。每個(gè)字母表示車(chē)當(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)下裝載量上界：已裝入貨物：已裝入貨物 和未和未 來(lái)可能來(lá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） 初始隊(duì)列中只有結(jié)點(diǎn)初始隊(duì)列中只有結(jié)點(diǎn)A

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

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

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

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

17、隊(duì)列之首。6） 結(jié)點(diǎn)結(jié)點(diǎn)E變?yōu)樽優(yōu)镋-結(jié)點(diǎn)結(jié)點(diǎn),葉結(jié)點(diǎn)葉結(jié)點(diǎn)J裝載量為裝載量為60，入堆，入堆, bestw變?yōu)樽優(yōu)?0; 葉結(jié)點(diǎn)葉結(jié)點(diǎn)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; / 搜索子集空間樹(shù)搜索子集空間樹(shù)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) )。但通過(guò)限界策略。但通過(guò)限界策略, ,并沒(méi)

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

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

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

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

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

24、ile （隊(duì)不空）隊(duì)不空）DELETEQ(E) /隊(duì)首結(jié)點(diǎn)出隊(duì)為新的隊(duì)首結(jié)點(diǎn)出隊(duì)為新的E E結(jié)點(diǎn)；結(jié)點(diǎn)；for （E E的每個(gè)兒子的每個(gè)兒子 X X） if (s（X）u) /當(dāng)是可能的最優(yōu)解時(shí)入隊(duì)當(dāng)是可能的最優(yōu)解時(shí)入隊(duì) ADD Q（X）；）； parent（X）=E; if (X是解結(jié)點(diǎn)是解結(jié)點(diǎn) ) /x/x為葉結(jié)點(diǎn)為葉結(jié)點(diǎn) U=min（cost（X），），u）; leaf=x; /方案的葉結(jié)點(diǎn)存儲(chǔ)在方案的葉結(jié)點(diǎn)存儲(chǔ)在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é)點(diǎn)的順序不同，框架結(jié)構(gòu)大致相同，只是擴(kuò)展結(jié)點(diǎn)的順序不同，因而存儲(chǔ)活結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不同。因而存儲(chǔ)活結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不同。FIFO分支分支- -限界算限界算法用法用隊(duì)列隊(duì)列存儲(chǔ)活結(jié)點(diǎn)，存儲(chǔ)活結(jié)點(diǎn)，LC分枝分枝- -限界算法用限界算法用堆堆存儲(chǔ)活存儲(chǔ)活結(jié)點(diǎn)，以保證比較優(yōu)良的結(jié)點(diǎn)先被擴(kuò)展。且對(duì)于結(jié)點(diǎn)，以保證比較優(yōu)良的結(jié)點(diǎn)先被擴(kuò)展。且對(duì)于LCL

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

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

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

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

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

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

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

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

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

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

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

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

38、中可以看到從圖中可以看到,A,A點(diǎn)要到達(dá)點(diǎn)要到達(dá)S S點(diǎn)必然要經(jīng)過(guò)點(diǎn)必然要經(jīng)過(guò)B B和和C C中的一個(gè)中的一個(gè), ,所以所以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為點(diǎn)為點(diǎn)i到點(diǎn)到點(diǎn)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講講 單源最短路徑單源最短路徑 階段階段: :我們按虛線所示來(lái)劃分階段我們按虛線所示來(lái)劃分階段, ,按按1,2,3,41,2,3,4的順序的順序來(lái)逐階段求解子問(wèn)題來(lái)逐階段求解子問(wèn)題. .因?yàn)橹挥星耙浑A段的所有子問(wèn)因?yàn)橹挥星耙浑A段的所有子問(wèn)題計(jì)算了題計(jì)算了, ,才能正確計(jì)算當(dāng)前階段的子問(wèn)題才能正確計(jì)算當(dāng)前階段的子問(wèn)題, ,所以這樣所以這樣的劃分是正確合理

40、的。的劃分是正確合理的。劃分階段劃分階段A32745542BCEFGS3階段階段1階段階段4 階段階段3階段階段2第第4 4講講 單源最短路徑單源最短路徑狀態(tài)：狀態(tài)可看成一個(gè)階段中的多個(gè)子問(wèn)題。第狀態(tài)：狀態(tài)可看成一個(gè)階段中的多個(gè)子問(wèn)題。第1個(gè)階個(gè)階段有一個(gè)狀態(tài)即段有一個(gè)狀態(tài)即S，第，第2個(gè)階段是三個(gè)狀態(tài)個(gè)階段是三個(gè)狀態(tài)E，F(xiàn)和和G，而第而第3個(gè)階段有兩個(gè)狀態(tài)個(gè)階段有兩個(gè)狀態(tài)B和和C，第，第4個(gè)階段只有一個(gè)狀個(gè)階段只有一個(gè)狀態(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é)點(diǎn)是從節(jié)點(diǎn)i一步可達(dá)的節(jié)點(diǎn)個(gè)數(shù)，即節(jié)點(diǎn)一步可達(dá)的節(jié)點(diǎn)個(gè)數(shù)，即節(jié)點(diǎn)i的直接鄰居節(jié)的直接鄰居節(jié)點(diǎn)個(gè)數(shù)。點(diǎn)個(gè)數(shù)。Aij表示從表示從i到到j(luò)的一步可達(dá)線段長(zhǎng)度。的一步可達(dá)線段長(zhǎng)度。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是一個(gè)這樣的結(jié)點(diǎn)，是一個(gè)這樣的結(jié)點(diǎn)，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)先的方式搜索解空間樹(shù)回溯法以深度優(yōu)先的方式搜索解空間樹(shù)T，而分支而分支 限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先（優(yōu)先隊(duì)列）限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先（優(yōu)先隊(duì)列） 的方式搜索解空間樹(shù)的方式搜索解

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

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

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

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

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