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

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

本節(jié)我們將詳細(xì)分析如何用優(yōu)先隊列分支限界法來解決類似問題。

優(yōu)先隊列式分支限界法：3654789搜索算法：分支搜索（例：深度優(yōu)先，廣度優(yōu)先，均為按深度或?qū)挾软樞?，在全部解空間搜索）分支限界搜索（例：與分枝搜索類似，并加入結(jié)點限制，對不滿足條件的結(jié)點為根的分枝子樹不再進行搜索）優(yōu)先隊列分支限界搜索例：在分支限界搜索基礎(chǔ)上，對搜索結(jié)點的順序按優(yōu)先隊列組織，使每一步搜索向最優(yōu)解目標(biāo)靠近，不滿足條件的結(jié)點為根的分支子樹不再進行搜索，遇到葉結(jié)點，即可得到一個解）第4講分支限界法優(yōu)先隊列組織：結(jié)點優(yōu)先級確定后,簡單地按結(jié)點優(yōu)先級進行排序,就生成了優(yōu)先隊列.但是,排序算法的時間復(fù)雜度較高?？紤]到搜索算法每次只擴展一個結(jié)點,數(shù)據(jù)結(jié)構(gòu)中堆排序方法適合這一特點,并且元素比較和交換的次數(shù)最少.堆通常有兩類：最大堆(根部的數(shù)最大,由大到小構(gòu)造堆)，最小堆(根部的數(shù)最小,由小到大構(gòu)造堆)，第4講分支限界法定義：堆(heap)是一個滿足下列條件的完全二叉數(shù)：（1）父結(jié)點比其左、右兒子結(jié)點都大（或?。?。（2）左、右兒子分別是一個堆。即：n個元素的序列{k1,k2,…kn},當(dāng)且僅當(dāng)滿足：

ki≤k2i

ki≥k2i

ki≤k2i+1

ki≥k2i+1

堆定義或(i=1,2,……n/2)第4講分支限界法例：6，4，7，9構(gòu)造的大堆（從根到葉子數(shù)值減?。?47969749674無序序列4篩選后的狀態(tài)建堆6篩選后建成堆第4講分支限界法例:3,8,7,4,5,9,1,6構(gòu)造的小堆(從根到葉子數(shù)值增大)初始堆根節(jié)點1出隊，最后節(jié)點6做根節(jié)點位后的狀態(tài)出堆6和3交換后的狀態(tài)135478696354781913654789第4講分支限界法例:3,8,7,4,5,9,1,6構(gòu)造的小堆(從根到葉子數(shù)值增大)6和4交換后的狀態(tài)出堆34567891第4講分支限界法例:3,8,7,4,5,9,6構(gòu)造的小堆(從根到葉子數(shù)值增大)初始堆進堆1進堆后建成新堆演示過程3468597134685971新堆建成第4講分支限界法

優(yōu)先隊列式搜索通過結(jié)點的優(yōu)先級,可以使搜索盡快朝著解空間樹上能到達(dá)最優(yōu)解的分支推進,這樣當(dāng)前最優(yōu)解一定較接近真正的最優(yōu)解.其后，我們將當(dāng)前最優(yōu)解作為一個“界”,對上界(或下界)不可能達(dá)到(大于)這個界的分支則不去進行搜索(結(jié)點不入隊),這樣就能縮小搜索范圍，從而提高搜索效率.這種搜索策略稱為優(yōu)先隊列分支限界法，簡稱LC-檢索(LeastCostSearch)。優(yōu)先隊列式分支限界法：第4講分支限界法結(jié)點擴展方式：無論那種分支限界法，都需要有一張活結(jié)點表。優(yōu)先隊列分支限界法將活結(jié)點組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級

選取優(yōu)先級最高的活結(jié)點成為當(dāng)前擴展結(jié)點.結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級通常是一個與該結(jié)點相關(guān)的數(shù)值p,它一般表示其接近最優(yōu)解的程度，裝載問題就可以當(dāng)前結(jié)點的裝載上界為該結(jié)點的優(yōu)先級。結(jié)點是否入隊判定標(biāo)準(zhǔn)：結(jié)點裝載上界>當(dāng)前最優(yōu)方案bestw,并且從該結(jié)點到根的裝載方案下，裝載量不超過船裝載量c1優(yōu)先隊列式分支限界法算法設(shè)計要點：第4講分支限界法例如：裝載問題W={10，30，50}，c1=60，所構(gòu)成的子集樹如下圖所表示：方框中紅色數(shù)表示該結(jié)點的裝載上界，作為結(jié)點的優(yōu)先級。裝載上界=已裝入物品重量+未來可能裝入物品的重量注意：已經(jīng)“處理”過的物品(已判斷是否裝入)不再計算為未來可能裝入物品的重量。AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=1X3=1X2=0X2=0X3=0X3=0X3=0X3=090909090606040108080805050300第4講分支限界法例4.裝載問題:有三個貨物，其重量為W={10，30，50}，有2輛貨車，其載重量為c1=60，c2=50,問：是否有方案把所有貨物運走？關(guān)鍵概念：(1)每個字母表示車當(dāng)前裝貨狀態(tài)。(2)當(dāng)前狀態(tài)下剩余裝載量(ew)：當(dāng)前狀態(tài)下剩余裝載量。(3)當(dāng)前狀態(tài)下裝載量上界：已裝入貨物和未來可能裝入的貨物總重量(排除已打算不裝入的貨物重量)。(4)當(dāng)前狀態(tài)最優(yōu)已裝載上界：截至目前狀態(tài)(包括目前狀態(tài))，所有已搜索的局部裝載方案中的最大裝載量(已裝入的最大重量)。裝50裝10裝30裝50裝50裝30裝50不裝10不裝30第4講分支限界法1）

初始隊列中只有結(jié)點A；2）

結(jié)點A變?yōu)镋-結(jié)點擴充B入隊,bestw=10;結(jié)點C的裝載上界為30+50=80>bestw，也入隊；3）

結(jié)點B變?yōu)镋-結(jié)點擴充D入隊,bestw=40;結(jié)點E的裝載上界為60>bestw，也入隊；4）

結(jié)點C變?yōu)镋-結(jié)點擴充F入隊,bestw仍為40;結(jié)點G的裝載上界為50>bestw,也入隊；5）

結(jié)點D變?yōu)镋-結(jié)點,葉結(jié)點H超過容量,不入隊；葉結(jié)點I的裝載上界為40=bestw=40,不入隊；6）

結(jié)點E變?yōu)镋-結(jié)點,葉結(jié)點J裝載上界為60>bestw=40,入隊，并將bestw更新為60;葉結(jié)點K的裝載上界為10<bestw=40,不入隊,即被剪掉；7）

結(jié)點F變?yōu)镋-結(jié)點，葉結(jié)點L超過容量，不入隊，bestw仍為60；葉結(jié)點M的裝載上界為30<bestw=60,被剪掉；8）

結(jié)點G變?yōu)镋-結(jié)點,葉結(jié)點N、O都被剪掉;9)結(jié)點J變?yōu)镋-結(jié)點,由于J是葉子結(jié)點，算法結(jié)束。FIFO+限界搜索過程：物品的重量W={10,30,50}，c1=60FIFO+限界搜索(超剩余容量)AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=1X3=1X2=0X2=0X3=0X3=0X3=0X3=090909090606040108080805050300H)J所有出隊結(jié)點中的葉子結(jié)點到根結(jié)點的路徑就是最優(yōu)裝載方案，即最優(yōu)解（可能有多個最優(yōu)解）。1)A2)3)4)5)6)EFGJ7)8)ABCCBCDEDEFGDEFGFGJGJ9)J葉子，隊列空，算法結(jié)束第4講分支限界法1）

初始隊列中只有結(jié)點A;2）

結(jié)點A變?yōu)镋-結(jié)點擴充B入堆,bestw=10;結(jié)點C的裝載上界為30+50=80>bestw,也入堆;堆中B上界為90，在優(yōu)先隊列之首;3）

結(jié)點B變?yōu)镋-結(jié)點擴充D入堆,bestw=40;結(jié)點E的裝載上界為60>bestw,也入堆;此時堆中D上界為90，在優(yōu)先隊列之首;4）

結(jié)點D變?yōu)镋-結(jié)點,葉結(jié)點H超過容量,葉結(jié)點I的裝載上界為40>=bestw=40,入堆;此時堆中C上界為80，在優(yōu)先隊列之首。分支限界(LC)-搜索的過程如下：優(yōu)先隊列分枝限界搜索第4講分支限界法5）

結(jié)點C變?yōu)镋-結(jié)點擴充F入堆,bestw仍為40;結(jié)點G的裝載上界為50>bestw,也入堆;此時堆中E上界為60，在優(yōu)先隊列之首。6）

結(jié)點E變?yōu)镋-結(jié)點,葉結(jié)點J裝載量為60，入堆,bestw變?yōu)?0;葉結(jié)點K上界為10<bestw，被剪掉；此時堆中J上界為60，在優(yōu)先隊列之首。7）

結(jié)點J變?yōu)镋-結(jié)點（葉子結(jié)點），擴展的層次為4（或隊首結(jié)點為葉子），算法結(jié)束。雖然此時堆并不空，但可以確定已找到了最優(yōu)解。物品的重量W={10,30,50}方框數(shù)字為裝載上界，Bestw為當(dāng)前最優(yōu)裝載量優(yōu)先隊列+限界搜索A90909090606040108080805050300Bestw=0Bestw=10Bestw=40Bestw=40Bestw=40Bestw=40Bestw=10Bestw=40如果裝入x3,則超重Bestw=60如果裝入則超重不是最優(yōu)方案裁剪AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=1X3=1X2=0X2=0X3=0X3=0X3=0X3=0BC9080ADC9080E60BCI8040E60DFE8040I50CG60E60IFG4050J60IEG4050J60擴展層數(shù)4(葉子)，算法結(jié)束第4講分支限界法1)輸出解方案,在搜索過程中仍需要生成解結(jié)構(gòu)樹,其結(jié)點信息包括指向父結(jié)點的指針和標(biāo)識物品取舍(或是父結(jié)點的左、右孩子)。2)堆結(jié)點首先應(yīng)該包括結(jié)點優(yōu)先級信息：結(jié)點所在分支的裝載上界uweight；堆中無法體現(xiàn)結(jié)點的層次信息(level),層次信息只能存儲在結(jié)點中。數(shù)據(jù)結(jié)構(gòu)設(shè)計：第4講分支限界法3)不同于分枝限界算法,由于擴展結(jié)點不是按層進行的，計算結(jié)點所在分支的裝載上界時,要用數(shù)組變量r記錄當(dāng)前層以下的最大重量，這樣可以隨時方便使用各層結(jié)點的裝載上界。數(shù)據(jù)結(jié)構(gòu)設(shè)計：第4講分支限界法同樣為了突出算法本身的思想，對堆操作也只進行抽象的描述用HeapNode代表隊列類型,則HeapNodeH;定義了一個堆H,相關(guān)操作有：

Insert(Q,…)表示入堆

DeleteMax(Q,…)表示出堆數(shù)據(jù)結(jié)構(gòu)設(shè)計：第4講分支限界法算法3

HeapNodeH[1000];structbbnode{bbnode*parent;//父節(jié)點指針intLChild;};//當(dāng)且僅當(dāng)是父節(jié)點的左孩子時，取值為1structHeapNode{bbnode*ptr;//活節(jié)點指針

floatuweight;//活節(jié)點的重量上限

intlevel;};//活節(jié)點所在層第4講分支限界法AddLiveNode(floatwt,intlev,bbnode*E,intch){bbnode*b=newbbnode;b->parent=E;b->LChil=ch;HeapNodeN;N.uweight=wt;N.level=lev;N.ptr=b;Insert(H，N);}第4講分支限界法MaxLoading(floatc,intn,intbestx[]){froatr[100],Ew,bestw=0;r[n]=0;For(intj=n-1;j>0;j--)r[j]=r[j+1]+w[j+1];Inti=1;bbnode*E=0;Ew=0;//搜索子集空間樹while(i!=n+1)//不在葉子上

{if(Ew+w[i]<=c)//可行的左孩子

{AddLiveNode(E,Ew+w[i]+r[i],1,i+1);}if(bestw<Ew+w[i])bestw=Ew+w[i];if(bestw<Ew+r[i])AddLiveNode(E,Ew+r[i],0,i+1);DeleteMax(H,E);i=N.level;E=N.ptr;Ew=N.uweight-r[i-1];}for(intj=n;j>0;j--){bestx[j]=E->LChild;E=E->parent;}returnEw;}第4講分支限界法算法的復(fù)雜度仍為O(2n)。但通過限界策略,并沒有搜索子集樹中的所有結(jié)點,由于每次都是選取的最接近最優(yōu)解的結(jié)點擴展，所以一旦搜索到葉結(jié)點作E結(jié)點時算法就可以結(jié)束了,所以算法實際執(zhí)行時復(fù)雜度遠(yuǎn)遠(yuǎn)低于O(2n).需要說明的是,算法結(jié)束時堆并不一定為空。算法分析：第4講分支限界法

FIFO限界算法搜索解空間的過程是按廣度優(yōu)先搜索子集樹過程中生成的一般隊列的元素順序，搜索最優(yōu)解，而優(yōu)先隊列限界搜索解空間的過程是按動搜索過程中態(tài)構(gòu)造的優(yōu)先隊列的首結(jié)點順序搜索最優(yōu)解。

看了上面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列法擴展結(jié)點的過程，一開始實際是在進行類似“深度優(yōu)先”的搜索。第4講分支限界法FIFO搜索或LIFO搜索也可以通過加入“限界”策略加速搜索嗎?與優(yōu)先隊列式分支限界法—LC—檢索的區(qū)別在哪兒呢？答案：由于FIFO搜索或LIFO搜索是盲目擴展結(jié)點,當(dāng)前最優(yōu)解距真正的最優(yōu)解距離較大,作為“界”所起到的剪枝作用很有限,不能有效提高搜索速度其實,優(yōu)先隊列式擴展結(jié)點的過程，一開始實際是在進行類似“深度優(yōu)先”的搜索。討論：第4講分支限界法上一小節(jié)的例子是求最大值的最優(yōu)化問題，下面我們以求解”最小成本“的最優(yōu)化問題為例，給出FIFO分支搜索算法框架。假定問題解空間樹為T,T至少包含一個解結(jié)點（即答案結(jié)點）.u為當(dāng)前的最優(yōu)解,初值為一個較大的數(shù);E表示當(dāng)前擴展的活結(jié)點,x為E的兒子,s(x)為結(jié)點x下界函數(shù),當(dāng)其值比u大時,不可能為最優(yōu)解,不繼續(xù)搜索此分支,該結(jié)點不入隊;當(dāng)其值比u小時,可能達(dá)到最優(yōu)解,繼續(xù)搜索此分支,該結(jié)點入隊;cost(X)為當(dāng)前葉結(jié)點所在分支的解。舉一反三：找最小成本的分枝限界法和優(yōu)先隊列分枝限界法第4講分支限界法search（T）//為找出最小成本答案結(jié)點檢索T。

{leaf=0;

初始化隊；ADDQ（T）；//根結(jié)點入隊parent（E）=0；//記錄擴展路徑，當(dāng)前結(jié)點的父結(jié)點

while（隊不空）{DELETEQ(E)//隊首結(jié)點出隊為新的E結(jié)點；for（E的每個兒子X）

if(s（X）<u)//當(dāng)是可能的最優(yōu)解時入隊

{ADDQ（X）；

parent（X）=E;

if(X是解結(jié)點)//x為葉結(jié)點

{U=min（cost（X），u）;

leaf=x;}//方案的葉結(jié)點存儲在leaf中

}}FIFO算法框架：第4講分支限界法

print（”leastcost=’，u）；

while（leaf<>0）//輸出最優(yōu)解方案

{print（leaf）；

leaf=parent（leaf）；}

}

第4講分支限界法找最小成本的LC分支-限界算法框架與FIFO分支-限界算法框架結(jié)構(gòu)大致相同，只是擴展結(jié)點的順序不同，因而存儲活結(jié)點的數(shù)據(jù)結(jié)構(gòu)不同。FIFO分支-限界算法用隊列存儲活結(jié)點，LC分枝-限界算法用堆存儲活結(jié)點，以保證比較優(yōu)良的結(jié)點先被擴展。且對于LC分支-限界算法，一旦擴展到葉結(jié)點就已經(jīng)找到最優(yōu)解，可以停止搜索。而用FIFO算法需要隊列為空時才可以停止搜索。找最小成本的LC分支-限界算法第4講分支限界法例5：單源最短路徑問題（LC算法） 給定帶權(quán)有向圖G=(V,E),其中每條邊的權(quán)是非負(fù)實數(shù).另外,還給定V中的一個頂點,稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。ISabcdefghijlmnopqrtu第2講分支限界法ISabcdefghilmnopqrtuj下面以一個例子來說明單源最短路徑問題:在有向圖G中,每一邊都有一個非負(fù)邊權(quán)。求從源頂點I到目標(biāo)頂點S之間的最短路徑。單源最短路徑問題具體問題實例：IS2342239279l35122871ABCDEFGHJ用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長IS2342239279l35122871ABCDEFGHJI活節(jié)點入堆（解空間樹生成過程）根節(jié)點出堆IIABC對出堆節(jié)點擴展234構(gòu)造堆A2B3C4A2B3C4判斷B,E,F是否入堆(只有E,F可入)注：判斷A的子節(jié)點E是否入堆的方法：從源點經(jīng)過A到E的路徑長度如果小于經(jīng)過目前解空間樹上從源點到E的其他最短路徑長度，則E入堆，否則E不入堆。判定其他節(jié)點入堆的方法與此相同。用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長IS2342239279l35122871ABCDEFGHJ活節(jié)點入堆（解空間樹生成過程）根節(jié)點出堆IABC對出堆節(jié)點擴展234B3C4整理堆判斷B,E,F是否入堆B3C4E4F9B3EFD判斷E,D是否入堆(只有D可入)注：判斷B的子節(jié)點E是否入堆的方法：從源點經(jīng)過B到E的路徑長度(12)如果小于經(jīng)過目前解空間樹上從源點到E的其他最短路徑長度(4)，則E入堆，否則E不入堆。判定其他節(jié)點入堆的方法與此相同。C4F9E4構(gòu)造堆272用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長IS2342239279l35122871ABCDEFGHJ活節(jié)點入堆（解空間樹生成過程）根節(jié)點出堆IABC對出堆節(jié)點擴展234整理為堆判斷D是否入堆（不）C4E4F9C4EFDD5C4E4D5F9整理為堆E4D5F9整理為堆注：判斷C的子節(jié)點D是否入堆的方法：從源點經(jīng)過C到D的路徑長度(6)如果小于經(jīng)過目前解空間樹上其他源點到D的最短路徑長度(5)，則E入堆，否則D不入堆。D不入堆272用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長IS2342239279l35122871ABCDEFGHJ活節(jié)點入堆（解空間樹生成過程）根節(jié)點出堆IABC對出堆節(jié)點擴展234判斷H,D是否入堆（H入）EFDE4D5F9整理為堆E4HD5F9H7D5判斷H,J是否入堆（J入）J整理為堆J6F9H7整理為堆D5F9D5F9H7H入2721用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點內(nèi)數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長IS2342239279l35122871ABCDEFGHJ活節(jié)點入堆（解空間樹生成過程）根節(jié)點出堆IABC對出堆節(jié)點擴展234判斷H,S是否入堆（S入）EFD整理為堆HJJ6F9H7J6SH7F9S8H7判斷S是否入堆（S不入）整理為堆S8F9S8因S是葉子，結(jié)束；最優(yōu)解從S到I272312第4講分支限界法

while(true)//搜索問題的解空間

{for(intj=1;j<=n;j++)

((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])){//頂點i到頂點j可達(dá)，且滿足控制約束

dist[j]=enode.length+a[enode.i][j];p[j]=enode.i;HeapNodenode=newHeapNode(j,dist[j]);heap.put(node);//加入活結(jié)點優(yōu)先隊列}

if(heap.isEmpty())break;elseenode=(HeapNode)heap.removeMin();}算法設(shè)計頂點I和j間有邊，且此路徑長小于原先從原點到j(luò)的路徑長(偽代碼)第4講分支限界法動態(tài)規(guī)劃解單源最短路徑由于圖的關(guān)系復(fù)雜而無序,一般難以呈現(xiàn)階段特征(除了特殊的圖，如多段圖--參見例5),因此動態(tài)規(guī)劃在圖論中的應(yīng)用不多.但有一類圖,它的頂點卻是有序的,這就是無環(huán)有向圖。在無環(huán)有向圖中,我們可以對點進行拓?fù)渑判?使其體現(xiàn)出有序的特征,據(jù)此劃分階段.在有向無環(huán)圖中求最短路徑的算法,體現(xiàn)出簡單的動態(tài)規(guī)劃思想.請看下面的例子。例5:單源最短路徑問題

已知從A到S的路線及費用如下圖，求從A到S的最小費用路線。A32745542BCEFGS3第4講單源最短路徑第4講單源最短路徑問題的分析A32745542BCEFGS3枚舉搜索圖中的每條路徑，但當(dāng)圖的規(guī)模較大時，搜索的效率顯然不盡人意。試用動態(tài)規(guī)劃的思路分析這道題:從圖中可以看到,A點要到達(dá)S點必然要經(jīng)過B和C中的一個,所以A到S的最短距離必然等于B到S的最短距離加上5,或是C到S的最短距離加上2.同樣,B到S的最短距離等于E到S的最短距離加上3或是F到S的最短距離加上2,…….第4講單源最短路徑設(shè)G[i]為點i到點S的距離,顯G[E]=4,G[F]=3,G[G]=5,根據(jù)上面的分析,有：G[B]=min{G[E]+3，G[F]+2}=5，G[C]=min{G[F]+7，G[G]+4}=9，G[A]=min{G[B]+5，G[C]+2}=10，所以A到S的最短距離是10，最短路徑ABFSA32745542BCEFGS3第4講單源最短路徑階段:我們按虛線所示來劃分階段,按1,2,3,4的順序來逐階段求解子問題.因為只有前一階段的所有子問題計算了,才能正確計算當(dāng)前階段的子問題,所以這樣的劃分是正確合理的。劃分階段A32745542BCEFGS3階段1階段4階段3階段2第4講單源最短路徑狀態(tài)：狀態(tài)可看成一個階段中的多個子問題。第1個階段有一個狀態(tài)即S，第2個階段是三個狀態(tài)E，F(xiàn)和G，而第3個階段有兩個狀態(tài)B和C，第4個階段只有一個狀態(tài)A。A32745542BCEFGS3狀態(tài)4狀態(tài)3狀態(tài)2狀態(tài)1第4講單源最短路徑A32745542BCEFGS3決策：決策就是狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移方程：

G(i)=min{G(j)+A[i][j]}，j=1,…,n,

n是從節(jié)點i一步可達(dá)的節(jié)點個數(shù)，即節(jié)點i的直接鄰居節(jié)點個數(shù)。A[i][j]表示從i到j(luò)的一步可達(dá)線段長度。G[C]=min{G[F]+7，G[G]+4}=9，第4講單源最短路徑Step1:realCOST(n),integerD(n-1),P(k),r,j,k,nCOST(n)←0Step2:forj←n-1to1by-1do設(shè)r是一個這樣的結(jié)點，<j,r>∈E且使c(j,r)+COST(r)取最小值。Step3:

COST（j）←c(j,r)+COST(r)Step4:

D(j)←rStep5:repeatStep6:

P(1)←1;P(k)←nStep7:

forj←2tok-1doStep8:P(j)←D(P(j-1))Step9:

repeatStep10:

endFGRAPH第4講分支限界法回溯法以深度優(yōu)先的方式搜索解空間樹T，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先（優(yōu)先隊列）的方式搜索解空間樹T。由于它們在問題的解空間樹T上搜索的方法不同,適合解決的問題也就不同。一般情況下,回溯法的求解目標(biāo)是找出T中滿足約束條件的所有解的方案，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個最優(yōu)解，或是在滿足約束條件的解中找出使用某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。圖的搜索算法小結(jié)回溯與分支限界法第4講分支限界法相對而言,分支限界算法的解空間比回溯法大得多,因此當(dāng)內(nèi)存容量有限時,回溯法成功的可能性更大。

回溯法和分支限界法區(qū)別：方法搜索方法數(shù)據(jù)結(jié)構(gòu)節(jié)點存儲特性應(yīng)用回溯深度優(yōu)先搜索堆?；罟?jié)點的所有可行子節(jié)點被遍歷后才被棧中彈出滿足約束條件的所有解的方案分支限界廣度優(yōu)先搜索或者最小消耗優(yōu)先搜索隊列、優(yōu)先隊列每個節(jié)點只有一次成為活節(jié)點的機會滿足約束條件的一個解,或者在某種意義下的最優(yōu)解第4講分支限界法采用窮舉法、回溯法或分支限界法都可以通過利用當(dāng)前最