分支定界法概述

分枝定界-簡(jiǎn)介分枝定界（branchandbound）是另一種系統(tǒng)地搜尋解空間的方法，它與回溯法的主要區(qū)分在于對(duì)E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成E-節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)镋-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的全部新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不行能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過(guò)程才結(jié)束。分枝定界-方法有兩種常用的方法可用來(lái)選擇下一個(gè)E-節(jié)點(diǎn)（雖然也可能存在其他的方法）：1）先進(jìn)先出（FIFO）即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的挨次與加入節(jié)點(diǎn)的挨次相同，因此活節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。2）最小耗費(fèi)或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。假如查找一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來(lái)建立，下一個(gè)E-節(jié)點(diǎn)就是具有最小耗費(fèi)的活節(jié)點(diǎn)；假如盼望搜尋一個(gè)具有最大收益的解，則可用最大堆來(lái)構(gòu)造活節(jié)點(diǎn)表，下一個(gè)E-節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn)。分枝定界-例子例5-1【迷宮老鼠】考察圖16-3a給出的迷宮老鼠例子和圖16-1的解空間結(jié)構(gòu)。使用FIF0分枝定界，初始時(shí)?。?,1）作為E-節(jié)點(diǎn)且活動(dòng)隊(duì)列為空。迷宮的位置（1,1）被置為1,以免再次返回到這個(gè)位置。（1,1）被擴(kuò)充，它的相鄰節(jié)點(diǎn)（1,2）和（2,1）加入到隊(duì)列中（即活節(jié)點(diǎn)表X為避開(kāi)再次回到這兩個(gè)位置，將位置（1,2）和（2,1）置為1。此時(shí)迷宮如圖17-1a所示，E-節(jié)點(diǎn)（1,1）被刪除。節(jié)點(diǎn)（1,2）從隊(duì)列中移出并被擴(kuò)充。檢查它的三個(gè)相鄰節(jié)點(diǎn)（見(jiàn)圖16-1的解空間），只有（1,3）是可行的移動(dòng)（剩余的兩個(gè)節(jié)點(diǎn)是障礙節(jié)點(diǎn)），將其加入隊(duì)列，并把相應(yīng)的迷宮位置置為1,所得到的迷宮狀態(tài)如圖17-lb所示。節(jié)點(diǎn)（1,2）被刪除，而下一個(gè)E-節(jié)點(diǎn)（2,1）將會(huì)被取出，當(dāng)此節(jié)點(diǎn)被綻開(kāi)時(shí)，節(jié)點(diǎn)（3,1）被加入隊(duì)列中，節(jié)點(diǎn)（3,1）被置為1,節(jié)點(diǎn)（2,1）被刪除，所得到的迷宮如圖17-lc所示。此時(shí)隊(duì)列中包含（1,3）和（3,1）兩個(gè)節(jié)點(diǎn)。隨后節(jié)點(diǎn)（1,3）變成下一個(gè)E-節(jié)點(diǎn)，由于此節(jié)點(diǎn)不能到達(dá)任何新的節(jié)點(diǎn)，所以此節(jié)點(diǎn)即被刪除，節(jié)點(diǎn)（3,1）成為新的E-節(jié)點(diǎn)，將隊(duì)列清空。節(jié)點(diǎn)（3,1）綻開(kāi)，（3,2）被加入隊(duì)列中,010（3,1）被刪除。（3,2）變?yōu)樾碌腅-節(jié)點(diǎn),綻開(kāi)此節(jié)點(diǎn)后，到達(dá)節(jié)點(diǎn)（3,3）,即迷宮的出口。使用FIFO搜尋，總能找出從迷宮入口到出口的最短路徑。需要留意的是：采用回溯法找到的路徑卻不肯定是最短路徑。好玩的是，程序6-11已經(jīng)給出了采用FIFO分枝定界搜尋從迷宮的（1,1）位置到（n,n）位置的最短路徑的代碼。例5-2【0/1背包問(wèn)題】下面比較分別采用FIFO分枝定界和最大收益分枝定界方法來(lái)解決如下背包問(wèn)題：n=3,w=[20,15,15],p=[40,25,25],c=30o法FO分枝定界采用一個(gè)隊(duì)列來(lái)紀(jì)錄活節(jié)點(diǎn)，節(jié)點(diǎn)將根據(jù)FIFO挨次從隊(duì)列中取出；而最大收益分枝定界使用一個(gè)最大堆，其中的E-節(jié)點(diǎn)根據(jù)每個(gè)活節(jié)點(diǎn)收益值的降序，或是根據(jù)活節(jié)點(diǎn)任意子樹(shù)的葉節(jié)點(diǎn)所能獲得的收益估量值的降序從隊(duì)列中取出。本例所使用的背包問(wèn)題與例16.2相同，并且有相同的解空間樹(shù)。使用FIF0分枝定界法搜尋，初始時(shí)以根節(jié)點(diǎn)A作為E-節(jié)點(diǎn)，此時(shí)活節(jié)點(diǎn)隊(duì)列為空。當(dāng)節(jié)點(diǎn)A綻開(kāi)時(shí)，生成了節(jié)點(diǎn)B和C,由于這兩個(gè)節(jié)點(diǎn)都是可行的，因此都被加入活節(jié)點(diǎn)隊(duì)列中，節(jié)點(diǎn)A被刪除。下一個(gè)E-節(jié)點(diǎn)是B,綻開(kāi)它并產(chǎn)生了節(jié)點(diǎn)D和E,D是不行行的，被刪除，而E被加入隊(duì)列中。下一步節(jié)點(diǎn)C成為E-節(jié)點(diǎn)，它綻開(kāi)后生成節(jié)點(diǎn)F和G,兩者都是可行節(jié)點(diǎn)，加入隊(duì)列中。下一個(gè)E-節(jié)點(diǎn)E生成節(jié)點(diǎn)J和K,J不行行而被刪除，K是一個(gè)可行的葉節(jié)點(diǎn)，并產(chǎn)生一個(gè)到目前為止可行的解，它的收益值為40o下一個(gè)E-節(jié)點(diǎn)是F,它產(chǎn)生兩個(gè)孩子L、M,L代表一個(gè)可行的解且其收益值為50,M代表另一個(gè)收益值為15的可行解。G是最終一個(gè)E-節(jié)點(diǎn)，它的孩子N和0都是可行的。由于活節(jié)點(diǎn)隊(duì)列變?yōu)榭?，因此搜尋過(guò)程終止,最佳解的收益值為50?？梢钥吹?，工作在解空間樹(shù)上的FIFO分枝定界方法特別象從根節(jié)點(diǎn)動(dòng)身的寬度優(yōu)先搜尋。它們的主要區(qū)分是在FIFO分枝定界中不行行的節(jié)點(diǎn)不會(huì)被搜尋。最大收益分枝定界算法以解空間樹(shù)中的節(jié)點(diǎn)A作為初始節(jié)點(diǎn)。綻開(kāi)初始節(jié)點(diǎn)得到節(jié)點(diǎn)B和C,兩者都是可行的并被插入堆中，節(jié)點(diǎn)B獲得的收益值是40（設(shè)xl=1），而節(jié)點(diǎn)C得到的收益值為0oA被刪除，B成為下一個(gè)E-節(jié)點(diǎn)，由于它的收益值比C的大。當(dāng)綻開(kāi)B時(shí)得到了節(jié)點(diǎn)D和E,D是不行行的而被刪除，E加入堆中。由于E具有收益值40,而C為0,由于E成為下一個(gè)E-節(jié)點(diǎn)。綻開(kāi)E時(shí)生成節(jié)點(diǎn)J和K,J不行行而被刪除，K是一個(gè)可行的解，因此K為作為目前能找到的最優(yōu)解而紀(jì)錄下來(lái)，然后K被刪除。由于只剩下一個(gè)活節(jié)點(diǎn)C在堆中，因此C作為E-節(jié)點(diǎn)被綻開(kāi)，生成F、G兩個(gè)節(jié)點(diǎn)插入堆中。F的收益值為25,因此成為下一個(gè)E-節(jié)點(diǎn)，綻開(kāi)后得到節(jié)點(diǎn)L和M,但L、M都被刪除，由于它們是葉節(jié)點(diǎn)，同時(shí)L所對(duì)應(yīng)的解被作為當(dāng)前最優(yōu)解紀(jì)錄下來(lái)。最終，G成為E-節(jié)點(diǎn)，生成的節(jié)點(diǎn)為N和0,兩者都是葉節(jié)點(diǎn)而被刪除，兩者所對(duì)應(yīng)的解都不比當(dāng)前的最優(yōu)解更好，因此最優(yōu)解保持不變。此時(shí)堆變?yōu)榭眨瑳](méi)有下一個(gè)E-節(jié)點(diǎn)產(chǎn)生，搜尋過(guò)程終止。終止于J的搜尋即為最優(yōu)解。如同在回溯方法中一樣，可采用一個(gè)定界函數(shù)來(lái)加速最優(yōu)解的搜尋過(guò)程。定界函數(shù)為最大收益設(shè)置了一個(gè)上限，通過(guò)綻開(kāi)一個(gè)特別的節(jié)點(diǎn)可能獲得這個(gè)最大收益。假如一個(gè)節(jié)點(diǎn)的定界函數(shù)值不大于目前最優(yōu)解的收益值，則此節(jié)點(diǎn)會(huì)被刪除而不作綻開(kāi)，更進(jìn)一步，在最大收益分枝定界方法中，可以使節(jié)點(diǎn)根據(jù)它們收益的定界函數(shù)值的非升序從堆中取出,而不是根據(jù)節(jié)點(diǎn)的實(shí)際收益值來(lái)取出。這種策略從可能到達(dá)一個(gè)好的葉節(jié)點(diǎn)的活節(jié)點(diǎn)動(dòng)身,而不是從目前具有較大收益值的節(jié)點(diǎn)動(dòng)身。例5-3【旅行商問(wèn)題】對(duì)于圖16-4的四城市旅行商問(wèn)題，其對(duì)應(yīng)的解空間為圖16-5所示的排列樹(shù)。FIFO分枝定界使用節(jié)點(diǎn)B作為初始的E-節(jié)點(diǎn)，活節(jié)點(diǎn)隊(duì)列初始為空。當(dāng)B綻開(kāi)時(shí)，生成節(jié)點(diǎn)C、D和E。由于從頂點(diǎn)1到頂點(diǎn)2,3,4都有邊相連，所以C、D、E三個(gè)節(jié)點(diǎn)都是可行的并加入隊(duì)列中。當(dāng)前的E-節(jié)點(diǎn)B被刪除，新的E-節(jié)點(diǎn)是隊(duì)列中的第一個(gè)節(jié)點(diǎn)，即節(jié)點(diǎn)Co由于在圖16-4中存在從頂點(diǎn)2到頂點(diǎn)3和4的邊，因此綻開(kāi)C,生成節(jié)點(diǎn)F和G,兩者都被加入隊(duì)列。下一步，D成為E-節(jié)點(diǎn)，接著又是E,到目前為止活節(jié)點(diǎn)隊(duì)列中包含節(jié)點(diǎn)F到Ko下一個(gè)E-節(jié)點(diǎn)是F,綻開(kāi)它得到了葉節(jié)點(diǎn)L。至此找到了一個(gè)旅行路徑，它的開(kāi)銷(xiāo)是59O綻開(kāi)下一個(gè)E-節(jié)點(diǎn)G，得到葉節(jié)點(diǎn)M,它對(duì)應(yīng)于一個(gè)開(kāi)銷(xiāo)為66的旅行路徑。接著H成為E-節(jié)點(diǎn)，從而找到葉節(jié)點(diǎn)N,對(duì)應(yīng)開(kāi)銷(xiāo)為25的旅行路徑。下一個(gè)E-節(jié)點(diǎn)是I,它對(duì)應(yīng)的部分旅行1-3-4的開(kāi)銷(xiāo)已經(jīng)為26,超過(guò)了目前最優(yōu)的旅行路徑，因此，I不會(huì)被綻開(kāi)。最終，節(jié)點(diǎn)J,K成為E-節(jié)點(diǎn)并被綻開(kāi)。經(jīng)過(guò)這些綻開(kāi)過(guò)程，隊(duì)列變?yōu)榭眨惴ńY(jié)束。找到的最優(yōu)方案是節(jié)點(diǎn)N所對(duì)應(yīng)的旅行路徑。假如不使用FIF0方法，還可以使用最小耗費(fèi)方法來(lái)搜尋解空間樹(shù)，即用一個(gè)最小堆來(lái)存儲(chǔ)活節(jié)點(diǎn)。這種方法同樣從節(jié)點(diǎn)B開(kāi)頭搜尋，并使用一個(gè)空的活節(jié)點(diǎn)列表。當(dāng)節(jié)點(diǎn)B綻開(kāi)時(shí)，生成節(jié)點(diǎn)C、D和E并將它們加入最小堆中。在最小堆的節(jié)點(diǎn)中，E具有最小耗費(fèi)（由于1-4的局部旅行的耗費(fèi)是4）,因此成為E-節(jié)點(diǎn)。綻開(kāi)E生成節(jié)點(diǎn)J和K并將它們加入最小堆，這兩個(gè)節(jié)點(diǎn)的耗費(fèi)分別為14和24。此時(shí)，在全部最小堆的節(jié)點(diǎn)中，D具有最小耗費(fèi)，因而成為E-節(jié)點(diǎn)，并生成節(jié)點(diǎn)H和10至此，最小堆中包含節(jié)點(diǎn)C、H、I、J和K,H具有最小耗費(fèi)，因此H成為下一個(gè)E-節(jié)點(diǎn)。綻開(kāi)節(jié)點(diǎn)E,得到一個(gè)完整的旅行路徑1-3-2-4-1,它的開(kāi)銷(xiāo)是25。節(jié)點(diǎn)J是下一個(gè)E-節(jié)點(diǎn)，綻開(kāi)它得到節(jié)點(diǎn)P,它對(duì)應(yīng)于一個(gè)耗費(fèi)為25的旅行路徑。節(jié)點(diǎn)K和I是下兩個(gè)E-節(jié)點(diǎn)。由于I的開(kāi)銷(xiāo)超過(guò)了當(dāng)前最優(yōu)的旅行路徑，因此搜尋結(jié)束，而剩下的全部活節(jié)點(diǎn)都不能使我們找到更優(yōu)的解。對(duì)于例5-2的背包問(wèn)題，可以使用一個(gè)定界函數(shù)來(lái)削減生成和綻開(kāi)的節(jié)點(diǎn)數(shù)量。這種函數(shù)》各確定旅行的最小耗費(fèi)的下限，這個(gè)下限可通過(guò)綻開(kāi)某個(gè)特定的節(jié)點(diǎn)而得到。假如一個(gè)節(jié)點(diǎn)的定界函數(shù)值不能比當(dāng)前的最優(yōu)旅行更小，則它將被刪除而不被綻開(kāi)。此外，對(duì)于最小耗費(fèi)分枝定界，節(jié)點(diǎn)根據(jù)它在最小堆中的非降序取出。在以上幾個(gè)例子中，可以采用定界函數(shù)來(lái)降低所產(chǎn)生的樹(shù)型解空間的節(jié)點(diǎn)數(shù)目。當(dāng)設(shè)計(jì)定界函數(shù)時(shí)，必需記住主要目的是采用最少的時(shí)間，在內(nèi)存允許的范圍內(nèi)去解決問(wèn)題。而通過(guò)產(chǎn)生具有最少節(jié)點(diǎn)的樹(shù)來(lái)解決問(wèn)題并不是根本的目標(biāo)。因此，我們需要的是一個(gè)能夠有效地削減計(jì)算時(shí)間并因此而使產(chǎn)生的節(jié)點(diǎn)數(shù)目也削減的定界函數(shù)?；厮莘ū确种Χń缭谡加脙?nèi)存方面具有優(yōu)勢(shì)?；厮莘ㄕ加玫膬?nèi)存是0（解