分枝定界-簡(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ò)充過程才結(jié)束。分枝定界-方法有兩種常用的方法可用來選擇下一個(gè)E-節(jié)點(diǎn)（雖然也可能存在其他的方法）：1）先進(jìn)先出（FIF0）即從活節(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)表可用最小堆來建立，下一個(gè)E-節(jié)點(diǎn)就是具有最小耗費(fèi)的活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，則可用最大堆來構(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)表）。為避免再次回到這兩個(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)（見圖16-1的解空間），只有（1，3）是可行的移動(dòng)（剩余的兩個(gè)節(jié)點(diǎn)是障礙節(jié)點(diǎn)），將其加入隊(duì)列，并把相應(yīng)的迷宮位置置為1，所得到的迷宮狀態(tài)如圖17-1b所示。節(jié)點(diǎn)（1，2）被刪除，而下一個(gè)E-節(jié)點(diǎn)（2,1）將會(huì)被取出，當(dāng)此節(jié)點(diǎn)被展開時(shí)，節(jié)點(diǎn)（3，1）被加入隊(duì)列中，節(jié)點(diǎn)（3，1）被置為1，節(jié)點(diǎn)（2,1）被刪除，所得到的迷宮如圖17-1c所示。此時(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）展開，（3,2）被加入隊(duì)列中，而（3,1）被刪除。（3,2）變?yōu)樾碌腅-節(jié)點(diǎn)，展開此節(jié)點(diǎn)后，到達(dá)節(jié)點(diǎn)（3，3），即迷宮的出口。使用FIFO搜索，總能找出從迷宮入口到出口的最短路徑。需要注意的是：利用回溯法找到的路徑卻不一定是最短路徑。有趣的是，程序6-11已經(jīng)給出了利用FIFO分枝定界搜索從迷宮的（1，1）位置到（n，n）位置的最短路徑的代碼。例5-2【0/1背包問題】下面比較分別利用FIFO分枝定界和最大收益分枝定界方法來解決如下背包問題：n=3,w=【20,15,15】，p=【40,25,25】，c=30。FIFO分枝定界利用一個(gè)隊(duì)列來記錄活節(jié)點(diǎn)，節(jié)點(diǎn)將按照FIFO順序從隊(duì)列中取出；而最大收益分枝定界使用一個(gè)最大堆，其中的E-節(jié)點(diǎn)按照每個(gè)活節(jié)點(diǎn)收益值的降序，或是按照活節(jié)點(diǎn)任意子樹的葉節(jié)點(diǎn)所能獲得的收益估計(jì)值的降序從隊(duì)列中取出。本例所使用的背包問題與例16.2相同，并且有相同的解空間樹。使用FIFO分枝定界法搜索，初始時(shí)以根節(jié)點(diǎn)A作為E-節(jié)點(diǎn)，此時(shí)活節(jié)點(diǎn)隊(duì)列為空。當(dāng)節(jié)點(diǎn)八、、A展開時(shí)，生成了節(jié)點(diǎn)B和C，由于這兩個(gè)節(jié)點(diǎn)都是可行的，因此都被加入活節(jié)點(diǎn)隊(duì)列中，節(jié)點(diǎn)A被刪除。下一個(gè)E-節(jié)點(diǎn)是B，展開它并產(chǎn)生了節(jié)點(diǎn)D和E，D是不可行的，被刪除，而E被加入隊(duì)列中。下一步節(jié)點(diǎn)C成為E-節(jié)點(diǎn)，它展開后生成節(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è)到目前為止可行的解，它的收益值為40。下一個(gè)E-節(jié)點(diǎn)是F，它產(chǎn)生兩個(gè)孩子L、M，L代表一個(gè)可行的解且其收益值為50，M代表另一個(gè)收益值為15的可行解。G是最后一個(gè)E-節(jié)點(diǎn)，它的孩子N和O都是可行的。由于活節(jié)點(diǎn)隊(duì)列變?yōu)榭?，因此搜索過程終止，最佳解的收益值為50?？梢钥吹?，工作在解空間樹上的FIFO分枝定界方法非常象從根節(jié)點(diǎn)出發(fā)的寬度優(yōu)先搜索。它們的主要區(qū)別是在FIFO分枝定界中不可行的節(jié)點(diǎn)不會(huì)被搜索。最大收益分枝定界算法以解空間樹中的節(jié)點(diǎn)A作為初始節(jié)點(diǎn)。展開初始節(jié)點(diǎn)得到節(jié)點(diǎn)B和C，兩者都是可行的并被插入堆中，節(jié)點(diǎn)B獲得的收益值是40（設(shè)x1=1），而節(jié)點(diǎn)C得到的收益值為0。A被刪除，B成為下一個(gè)E-節(jié)點(diǎn)，因?yàn)樗氖找嬷当菴的大。當(dāng)展開B時(shí)得到了節(jié)點(diǎn)D和E，D是不可行的而被刪除，E加入堆中。由于E具有收益值40，而C為0，因?yàn)镋成為下一個(gè)E-節(jié)點(diǎn)。展開E時(shí)生成節(jié)點(diǎn)J和K，J不可行而被刪除，K是一個(gè)可行的解，因此K為作為目前能找到的最優(yōu)解而記錄下來，然后K被刪除。由于只剩下一個(gè)活節(jié)點(diǎn)C在堆中，因此C作為E-節(jié)點(diǎn)被展開，生成F、G兩個(gè)節(jié)點(diǎn)插入堆中。F的收益值為25，因此成為下一個(gè)E-節(jié)點(diǎn)，展開后得到節(jié)點(diǎn)L和M，但L、M都被刪除，因?yàn)樗鼈兪侨~節(jié)點(diǎn)，同時(shí)L所對(duì)應(yīng)的解被作為當(dāng)前最優(yōu)解記錄下來。最終，G成為E-節(jié)點(diǎn)，生成的節(jié)點(diǎn)為N和O,兩者都是葉節(jié)點(diǎn)而被刪除，兩者所對(duì)應(yīng)的解都不比當(dāng)前的最優(yōu)解更好，因此最優(yōu)解保持不變。此時(shí)堆變?yōu)榭?，沒有下一個(gè)E-節(jié)點(diǎn)產(chǎn)生，搜索過程終止。終止于J的搜索即為最優(yōu)解。猶如在回溯方法中一樣，可利用一個(gè)定界函數(shù)來加速最優(yōu)解的搜索過程。定界函數(shù)為最大收益設(shè)置了一個(gè)上限，通過展開一個(gè)特殊的節(jié)點(diǎn)可能獲得這個(gè)最大收益。如果一個(gè)節(jié)點(diǎn)的定界函數(shù)值不大于目前最優(yōu)解的收益值，則此節(jié)點(diǎn)會(huì)被刪除而不作展開，更進(jìn)一步，在最大收益分枝定界方法中，可以使節(jié)點(diǎn)按照它們收益的定界函數(shù)值的非升序從堆中取出，而不是按照節(jié)點(diǎn)的實(shí)際收益值來取出。這種策略從可能到達(dá)一個(gè)好的葉節(jié)點(diǎn)的活節(jié)點(diǎn)出發(fā)，而不是從目前具有較大收益值的節(jié)點(diǎn)出發(fā)。例5-3【旅行商問題】對(duì)于圖16-4的四城市旅行商問題，其對(duì)應(yīng)的解空間為圖16-5所示的排列樹。FIFO分枝定界使用節(jié)點(diǎn)B作為初始的E-節(jié)點(diǎn)，活節(jié)點(diǎn)隊(duì)列初始為空。當(dāng)B展開時(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)C。因?yàn)樵趫D16-4中存在從頂點(diǎn)2到頂點(diǎn)3和4的邊，因此展開C，生成節(jié)點(diǎn)F和G，兩者都被加入隊(duì)列。下一步，D成為E-節(jié)點(diǎn)，接著又是￡，到目前為止活節(jié)點(diǎn)隊(duì)列中包含節(jié)點(diǎn)F到K。下一個(gè)E-節(jié)點(diǎn)是F，展開它得到了葉節(jié)點(diǎn)L。至此找到了一個(gè)旅行路徑，它的開銷是59。展開下一個(gè)E-節(jié)點(diǎn)G，得到葉節(jié)點(diǎn)M，它對(duì)應(yīng)于一個(gè)開銷為66的旅行路徑。接著H成為E-節(jié)點(diǎn)，從而找到葉節(jié)點(diǎn)N，對(duì)應(yīng)開銷為25的旅行路徑。下一個(gè)E-節(jié)點(diǎn)是I，它對(duì)應(yīng)的部分旅行1-3-4的開銷已經(jīng)為26,超過了目前最優(yōu)的旅行路徑，因此，I不會(huì)被展開。最后，節(jié)點(diǎn)J，K成為E-節(jié)點(diǎn)并被展開。經(jīng)過這些展開過程，隊(duì)列變?yōu)榭眨惴ńY(jié)束。找到的最優(yōu)方案是節(jié)點(diǎn)N所對(duì)應(yīng)的旅行路徑。如果不使用FIFO方法，還可以使用最小耗費(fèi)方法來搜索解空間樹，即用一個(gè)最小堆來存儲(chǔ)活節(jié)點(diǎn)。這種方法同樣從節(jié)點(diǎn)B開始搜索，并使用一個(gè)空的活節(jié)點(diǎn)列表。當(dāng)節(jié)點(diǎn)B展開時(shí)，生成節(jié)點(diǎn)C、D和E并將它們加入最小堆中。在最小堆的節(jié)點(diǎn)中，E具有最小耗費(fèi)（因?yàn)?-4的局部旅行的耗費(fèi)是4），因此成為E-節(jié)點(diǎn)。展開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和I。至此，最小堆中包含節(jié)點(diǎn)C、H、I、J和K，H具有最小耗費(fèi)，因此H成為下一個(gè)E-節(jié)點(diǎn)。展開節(jié)點(diǎn)E，得到一個(gè)完整的旅行路徑1-3-2-4-1，它的開銷是25。節(jié)點(diǎn)J是下一個(gè)E-節(jié)點(diǎn)，展開它得到節(jié)點(diǎn)P，它對(duì)應(yīng)于一個(gè)耗費(fèi)為25的旅行路徑。節(jié)點(diǎn)K和I是下兩個(gè)E-節(jié)點(diǎn)。由于I的開銷超過了當(dāng)前最優(yōu)的旅行路徑，因此搜索結(jié)束，而剩下的所有活節(jié)點(diǎn)都不能使我們找到更優(yōu)的解。對(duì)于例5-2的背包問題，可以使用一個(gè)定界函數(shù)來減少生成和展開的節(jié)點(diǎn)數(shù)量。這種函數(shù)將確定旅行的最小耗費(fèi)的下限，這個(gè)下限可通過展開某個(gè)特定的節(jié)點(diǎn)而得到。如果一個(gè)節(jié)點(diǎn)的定界函數(shù)值不能比當(dāng)前的最優(yōu)旅行更小，則它將被刪除而不被展開。另外，對(duì)于最小耗費(fèi)分枝定界，節(jié)點(diǎn)按照它在最小堆中的非降序取出。在以上幾個(gè)例子中，可以利用定界函數(shù)來降低所產(chǎn)生的樹型解空間的節(jié)點(diǎn)數(shù)目。當(dāng)設(shè)計(jì)定界函數(shù)時(shí)，必須記住主要目的是利用最少的時(shí)間，在內(nèi)存允許的范圍內(nèi)去解決問題。而通過產(chǎn)生具有最少節(jié)點(diǎn)的樹來解決問題并不是根本的目標(biāo)。因此，我們需要的是一個(gè)能夠有效地減少計(jì)算時(shí)間并因此而使產(chǎn)生的節(jié)點(diǎn)數(shù)目也減少的定界函數(shù)?；厮莘ū确种Χń缭谡加脙?nèi)存方面具有優(yōu)勢(shì)?；厮莘ㄕ加玫膬?nèi)存是O（解空間的最