第八章 分支與限界

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

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

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

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

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

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