第八章 分支與限界

1、1第八章第八章分支與限界分支與限界8.1分支與限界法的基本思想一、基本思想：1、在結(jié)點(diǎn)估算沿著它的各兒子結(jié)點(diǎn)搜索時(shí)，目標(biāo)函數(shù)可能取得的“界”，_e2、把兒子結(jié)點(diǎn)和目標(biāo)函數(shù)可能取得的“界”，保存在優(yōu)先隊(duì)列或堆中，3、從隊(duì)列或堆中選取“界”最大或最小的結(jié)點(diǎn)向下搜索，直到葉子結(jié)點(diǎn)，_e4、若葉子結(jié)點(diǎn)的目標(biāo)函數(shù)的值，是結(jié)點(diǎn)表中的最大值或最小值，則沿葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑所確定的解，就是問(wèn)題的最優(yōu)解，由該葉子結(jié)點(diǎn)所確定的目標(biāo)函數(shù)的值，就是解這個(gè)問(wèn)

2、題所得到的最大值或最小值二、目標(biāo)函數(shù)“界”的特性：是部分解，是相應(yīng)的界)()(211kxxxx??)()(211kxxxboundxbound??1、對(duì)最小值問(wèn)題，稱(chēng)為下界，意思是向下搜索所可能取得的值最小不會(huì)小于這些下界。若是所得到的部分解，滿足：)(21kxxxX??（8.1.1）)()()(21211kxxxboundxxboundxbound?????2、對(duì)最大值問(wèn)題，稱(chēng)為上界，意思是向下搜索所可能取得的值最大不會(huì)大于這些上界。

3、若是所得到的部分解，滿足：)(21kxxxX??)()()(21211kxxxboundxxboundxbound?????三、兩種分支方法：設(shè)解向量，的取值范圍為有窮集，，。)(21nxxxX??ixiSiinS?||ni??11、每棵子樹(shù)都有個(gè)分支：in最壞情況下，結(jié)點(diǎn)表的空間為，)(21nnnnO????若狀態(tài)空間樹(shù)是完全叉樹(shù)，，結(jié)點(diǎn)表的空間為。nnnnnn?????21)(nnO2、每棵子樹(shù)只有兩個(gè)分支，取特定值的分支、及不取特

4、定值的分支：ix狀態(tài)空間樹(shù)是完全二叉樹(shù)，最壞情況下結(jié)點(diǎn)表的空間為)2(nO8.2貨郎擔(dān)問(wèn)題有向賦權(quán)圖，頂點(diǎn)集。)(EVG?)(110??nvvvV?為圖的鄰接矩陣，表示頂點(diǎn)到頂點(diǎn)的關(guān)聯(lián)邊的長(zhǎng)度，又把稱(chēng)為費(fèi)用矩陣。cijcivjvc3定義定義8.2對(duì)費(fèi)用矩陣的每一行和每一列都進(jìn)行行歸約和列歸約，得到一個(gè)新的費(fèi)用c矩陣，使得中每一行和每一列至少都有一個(gè)元素為0，稱(chēng)為費(fèi)用矩陣的歸約。矩陣稱(chēng)ccc為費(fèi)用矩陣的歸約矩陣。稱(chēng)常數(shù)hc（8.2.1）?

5、???????1010niiniichlhh為矩陣的歸約常數(shù)。c例：對(duì)圖8.1(a)中的費(fèi)用矩陣進(jìn)行歸約，得到圖8.1(c)所示歸約矩陣。歸約常數(shù)h為484761525???????h3、歸約矩陣與哈密爾頓回路的關(guān)系定理定理8.1有向賦權(quán)圖，的哈密爾頓回路，的費(fèi)用矩陣，是以)(EVG?GlGc)(lw計(jì)算的回路費(fèi)用。是的歸約矩陣，歸約常數(shù)為，是以計(jì)算的回路費(fèi)用，有：ccch)(lwc（8.2.2）hlwlw??)()(證明證明和分別是和

6、的第行第列元素，ijcijcccij，jiijijchlhcc???10???njiji是以計(jì)算的哈密爾頓回路的費(fèi)用，令)(lwc???ljiijclw)(是計(jì)算的同一條哈密爾頓回路的費(fèi)用，令)(lwc???ljiijclw)(由引理8.1，回路上的邊對(duì)應(yīng)于中每行每列各一個(gè)元素。有chlwchlhcclwnjjniiljiijljiij????????????????)()(1010定理證畢。定理定理8.2有向賦權(quán)圖，是的最短哈密爾頓回