算法設(shè)計(jì)與分析分支限界法

主要內(nèi)容分支限界基本方法最短路徑問(wèn)題和0-1背包問(wèn)題旅行商問(wèn)題（無(wú)向圖）旅行商問(wèn)題（有向圖）Little算法基本概念分支限界法回溯在求最優(yōu)解的過(guò)程中，效率不是很高。改進(jìn)：先訪問(wèn)那些有可能得出最優(yōu)解的節(jié)點(diǎn)生成一個(gè)節(jié)點(diǎn)時(shí)，也會(huì)生成這個(gè)節(jié)點(diǎn)的界，界表示通過(guò)此節(jié)點(diǎn)生成的解所能夠到達(dá)的一個(gè)下限(最小化問(wèn)題)或者上限(最大化問(wèn)題)分支限界法在訪問(wèn)一個(gè)節(jié)點(diǎn)時(shí)，會(huì)生成這個(gè)節(jié)點(diǎn)所有的子節(jié)點(diǎn)，也被稱為生成所有的分支基本概念分支限界的基本流程如下基本概念：關(guān)鍵點(diǎn)樹(shù)的形成不追求規(guī)則的樹(shù)，也就是并不追求等長(zhǎng)的解，只要形成的樹(shù)有利于解的獲取和界的計(jì)算。界的計(jì)算界計(jì)算一方面應(yīng)該越簡(jiǎn)單越好，另一方面應(yīng)該和最優(yōu)解越接近越好?；靖拍睿宏P(guān)鍵點(diǎn)算法終止條件當(dāng)算法從堆中取得了第一個(gè)解節(jié)點(diǎn)(葉子節(jié)點(diǎn))，則算法必然得出了最優(yōu)解，則算法結(jié)束。優(yōu)化計(jì)算一個(gè)上界（最小化問(wèn)題）或者下界（最大化問(wèn)題）。基本概念和回溯比較樹(shù)的構(gòu)造不一樣搜索方式不一樣回溯法可用于尋找可行解的問(wèn)題，也可以用于最優(yōu)解的問(wèn)題，但分支限界只用于最優(yōu)解問(wèn)題主要內(nèi)容分支限界基本方法最短路徑問(wèn)題和0-1背包問(wèn)題旅行商問(wèn)題（無(wú)向圖）旅行商問(wèn)題（有向圖）Little算法單源最短路徑計(jì)算節(jié)點(diǎn)a到節(jié)點(diǎn)t的最短路徑單源最短路徑確定下界經(jīng)過(guò)某節(jié)點(diǎn)到t的最短路徑的下界為：到此節(jié)點(diǎn)的最短路徑+此節(jié)點(diǎn)的一條最短邊單源最短路徑搜索樹(shù)單源最短路徑k=1根節(jié)點(diǎn)0對(duì)應(yīng)于源點(diǎn)a，有3個(gè)鄰接頂點(diǎn)b、c、d，其下界為3,7,11，壓入堆。k=2堆中下界3最小，對(duì)于的頂點(diǎn)b，也即節(jié)點(diǎn)1。從頂點(diǎn)b繼續(xù)進(jìn)行搜索。頂點(diǎn)b的鄰接頂點(diǎn)為c和e，其下界為6和11，壓入堆。k=3堆中下界6最小，對(duì)應(yīng)頂點(diǎn)c，也即節(jié)點(diǎn)4，從頂點(diǎn)c繼續(xù)進(jìn)行搜索。頂點(diǎn)c鄰接頂點(diǎn)d、e、f、g，對(duì)應(yīng)的下界為13,10,8,8，壓入堆。k=2堆中7最小，對(duì)應(yīng)頂點(diǎn)c，也即節(jié)點(diǎn)2。從頂點(diǎn)c進(jìn)行搜索。頂點(diǎn)c鄰接頂點(diǎn)d、e、f、g，對(duì)應(yīng)的下界為14,11,9,9，壓入堆。單源最短路徑k=4堆中8最小，對(duì)應(yīng)頂點(diǎn)f，也即節(jié)點(diǎn)8。頂點(diǎn)f的鄰接頂點(diǎn)為e、t，下界分別為9、11，壓入棧中。其中11為一個(gè)可行解，路徑長(zhǎng)度為11.k=4堆中8最小，對(duì)應(yīng)頂點(diǎn)g，也即節(jié)點(diǎn)9。頂點(diǎn)g的鄰接頂點(diǎn)為f、t，下界都是10。其中10為一個(gè)可行解，路徑長(zhǎng)度為10.

k=5堆中9最小，對(duì)應(yīng)頂點(diǎn)e，也即節(jié)點(diǎn)14.頂點(diǎn)e只有一個(gè)鄰接頂點(diǎn)t，下界為9，從而得到一個(gè)可行解，路徑長(zhǎng)度為9，加入堆中。

堆中最小的為9，且為一個(gè)可行解，因此是最優(yōu)解單源最短路徑：總結(jié)初始化初始化參數(shù)，初始化源節(jié)點(diǎn)，壓入堆中。從堆中取堆頂節(jié)點(diǎn)如果堆頂節(jié)點(diǎn)是一個(gè)完整解，則算法結(jié)束。否則，生成該節(jié)點(diǎn)的所有子節(jié)點(diǎn)，并計(jì)算下界，之后依據(jù)節(jié)點(diǎn)的界，將節(jié)點(diǎn)插入到最小堆中。重復(fù)上述流程。0-1背包問(wèn)題考慮n=4的背包問(wèn)題（背包承重量為C=10）物品重量?jī)r(jià)值價(jià)值/重量144010274263525543124

其中物品已經(jīng)按照“價(jià)值-重量比”降序排列，這樣會(huì)帶來(lái)處理上的方便。

0-1背包問(wèn)題界的選取為每個(gè)搜索節(jié)點(diǎn)設(shè)置一個(gè)上界ub(upperbound)，一個(gè)簡(jiǎn)單方法是：把已經(jīng)選擇的物品總價(jià)值v，加上背包剩余承重量C-w與剩下可選擇的物品的最高“價(jià)值-重量比”的乘積，即ub=v+(C-w)×max(vi/wi)另外更準(zhǔn)確的方法是按照小數(shù)背包貪心算法比如，若已裝物品1，則價(jià)值的上界為40+(10-4)×6=760-1背包問(wèn)題物品重量?jī)r(jià)值價(jià)值/重量144010274263525543124主要內(nèi)容分支限界基本方法最短路徑問(wèn)題和0-1背包問(wèn)題旅行商問(wèn)題（無(wú)向圖）旅行商問(wèn)題（有向圖）Little算法旅行商問(wèn)題：無(wú)向圖樹(shù)的構(gòu)造旅行商問(wèn)題：無(wú)向圖界的選取可以取圖中開(kāi)銷最小的邊w(例子中的最小開(kāi)銷為2)，則n?w(n為哈密頓回路邊的條數(shù))必然是一個(gè)下界。旅行商問(wèn)題：無(wú)向圖旅行商問(wèn)題：無(wú)向圖旅行商問(wèn)題：無(wú)向圖優(yōu)化為了進(jìn)一步提高效率，可以直接剪去那些下界比較高的節(jié)點(diǎn)，此時(shí)，我們可以確定一個(gè)上界ub，也就是說(shuō)旅行商回路TPS?

一定不會(huì)大于這個(gè)上界ub≥TPS?，當(dāng)某個(gè)節(jié)點(diǎn)的下界lb>ub時(shí)，可以對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行剪枝貪心算法確定ub：例子的ub為16旅行商問(wèn)題：無(wú)向圖樹(shù)的訪問(wèn)旅行商問(wèn)題：無(wú)向圖算法主要內(nèi)容分支限界基本方法最短路徑問(wèn)題和0-1背包問(wèn)題旅行商問(wèn)題（無(wú)向圖）旅行商問(wèn)題（有向圖）Little算法旅行商問(wèn)題：有向圖構(gòu)造的樹(shù)是和無(wú)向圖一致的下界的確定可不可以直接沿用無(wú)向圖下界的確定？旅行商問(wèn)題：有向圖下界的確定旅行商問(wèn)題：有向圖下界的確定旅行商問(wèn)題：有向圖下界的確定旅行商問(wèn)題：有向圖旅行商問(wèn)題：有向圖旅行商問(wèn)題：有向圖將根節(jié)點(diǎn)約化矩陣的第一行和第二列元素，以及元素(2,1)全部置為無(wú)窮旅行商問(wèn)題：有向圖旅行商問(wèn)題：little算法基于邊的分支即算法每次都選擇一個(gè)合適的邊，之后，將父節(jié)點(diǎn)分支成兩個(gè)子節(jié)點(diǎn)，左子節(jié)點(diǎn)代表包含此邊的所有回路，而右邊的節(jié)點(diǎn)表示不包含此邊的回路little算法形成的是二叉樹(shù)little算法對(duì)下界的計(jì)算是和有向圖的分支限界類似。旅行商問(wèn)題：little算法旅行商問(wèn)題：little算法算法的關(guān)鍵是選擇一條合適的邊，怎么選邊呢？選擇一條后悔值最大的邊作為用于分支

旅行商問(wèn)題：little算法約化旅行商問(wèn)題：little算法根節(jié)點(diǎn)的計(jì)算是一樣的計(jì)算后悔值最大的邊，得出旅行商問(wèn)題：little算法注意：右子節(jié)點(diǎn)不包括的那條邊對(duì)應(yīng)矩陣中的值設(shè)置為∞避免產(chǎn)生子回路，需要將可能產(chǎn)生回路的邊設(shè)置為∞如果約化矩陣只剩下0和∞元素，表示已經(jīng)確定了一條哈密頓回路旅行商問(wèn)題：little算法約化旅行商問(wèn)題：little算法選擇邊已經(jīng)是約化矩陣旅行商問(wèn)題：little算法不包含邊旅行商問(wèn)題：little算法選擇邊已經(jīng)是約化矩陣旅行商問(wèn)題：little算法不選擇邊旅行商問(wèn)題：little算法選擇邊旅行商問(wèn)題：little算法不選擇邊旅行商問(wèn)題：little算法選擇邊旅行商問(wèn)題：little算法不選擇邊旅行商問(wèn)題：little算法任務(wù)指派問(wèn)題任務(wù)指派問(wèn)題要求把n項(xiàng)任務(wù)指派給n個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的費(fèi)用不同，要求指派的總費(fèi)用最小。通常用矩陣來(lái)描述一個(gè)任務(wù)分配給一個(gè)人的費(fèi)用，稱為費(fèi)用矩陣，如下所示，此矩陣中，行代表人，列代表任務(wù)。任務(wù)指派問(wèn)題：算法1

樹(shù)：任務(wù)指派先給先給第1個(gè)人分配任務(wù)，再給第2個(gè)人分配，直到給第n個(gè)人分配，所以建立樹(shù)的第1層是第1個(gè)人的分配，第2層是第2個(gè)人的分配，依次類推。下界：以每行最小元素之和作為下界

上界：用貪心算法即可任