第9章分支限界法

第九章分支限界法1234概述圖問題中的分支限界法組合問題中的分支限界法小結(jié)分支限界法—概述分支限界法按廣度優(yōu)先策略搜索問題的解空間樹，在搜索過程中，對(duì)待處理的結(jié)點(diǎn)根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的可能取值，從中選取使目標(biāo)函數(shù)取得極值（極大或極?。┑慕Y(jié)點(diǎn)優(yōu)先進(jìn)行廣度優(yōu)先搜索，從而不斷調(diào)整搜索方向，盡快找到問題的解。分支限界法適用于求解最優(yōu)化問題。確定一個(gè)合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]。按照廣度優(yōu)先策略搜索問題的解空間樹，在分支結(jié)點(diǎn)上，依次擴(kuò)展該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值，某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值超出目標(biāo)函數(shù)的界，則將其丟棄；否則，將其加入待處理結(jié)點(diǎn)表（以下簡(jiǎn)稱表PT）中。依次從表PT中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，重復(fù)上述過程，直至找到最優(yōu)解。9.1.1分支限界法的設(shè)計(jì)思想分支限界法需要解決的關(guān)鍵問題如何確定合適的限界函數(shù)。（提示：計(jì)算簡(jiǎn)單，減少搜索空間，不丟解）如何組織待處理結(jié)點(diǎn)表。（提示：表PT可以采用堆的形式，也可以采用優(yōu)先隊(duì)列的形式存儲(chǔ)。各有什么特點(diǎn)？）如何確定最優(yōu)解的各個(gè)分量。（提示：跳躍式處理解空樹結(jié)點(diǎn)，必須保存搜索過程中經(jīng)過的路徑信息。）回溯法從根結(jié)點(diǎn)出發(fā)，按照深度優(yōu)先策略遍歷問題的解空間樹。分支限界法按廣度優(yōu)先策略搜索問題的解空間樹。二者與蠻力法區(qū)別？回溯法與分支限界法區(qū)別？9.1.2分支限界法的時(shí)間性能

在最壞情況下，時(shí)間復(fù)雜性為指數(shù)階。與回溯法不同的是，分支限界法首先擴(kuò)展解空間樹中的上層結(jié)點(diǎn)，并采用限界函數(shù)，有利于實(shí)行大范圍剪枝，同時(shí)，根據(jù)限界函數(shù)不斷調(diào)整搜索方向，選擇最有可能取得最優(yōu)解的子樹優(yōu)先進(jìn)行搜索。類比回溯法分析分支限界法的時(shí)間性能分支限界法的較高效率是以付出一定代價(jià)為基礎(chǔ)的，其工作方式也造成了算法設(shè)計(jì)的復(fù)雜性。一個(gè)簡(jiǎn)單的例子—圓排列問題問題描述：給定n個(gè)圓的半徑序列，將這些圓放到一個(gè)矩形框中，各圓與矩形框的底邊相切，則圓的不同排列會(huì)得到不同的排列長度，要求找出具有最小長度的圓排列。想法：采用分支限界法求解圓排列問題，首先設(shè)計(jì)限界函數(shù)，然后在搜索過程中選擇使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)優(yōu)先進(jìn)行擴(kuò)充。問題描述：TSP問題是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。圖問題中的分支限界法—TSP問題想法：確定目標(biāo)函數(shù)的界[down,up]。（提示：如何確定上、下界？）確定目標(biāo)函數(shù)值的計(jì)算方法（限界函數(shù)）。基于上、下界，按分支限界法設(shè)計(jì)思想，搜索解空間樹，得到最優(yōu)解。圖9.5(a)所示是一個(gè)帶權(quán)無向圖，(b)是該圖的代價(jià)矩陣。271563134253984C=∞31583∞67916∞42574∞38923∞(a)一個(gè)無向圖(b)無向圖的代價(jià)矩陣圖9.4無向圖及其代價(jià)矩陣1.確定問題的上界16，下界14。如何設(shè)計(jì)求上、下界策略？圖問題中的分支限界法—TSP問題2.確定限界函數(shù)計(jì)算方法一般情況下，假設(shè)當(dāng)前已確定的路徑為U=(r1,r2,…,rk)，即路徑上已確定了k個(gè)頂點(diǎn)，此時(shí)，該部分解的目標(biāo)函數(shù)值的計(jì)算方法如下：3.基于分支限界法的思想，從根結(jié)點(diǎn)開始依次計(jì)算目標(biāo)函數(shù)值加入待處理結(jié)點(diǎn)表中直至葉子結(jié)點(diǎn)。圖問題中的分支限界法—TSP問題圖問題中的分支限界法—TSP問題1.根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up；2.計(jì)算根結(jié)點(diǎn)的目標(biāo)函數(shù)值并加入待處理結(jié)點(diǎn)表PT；3.循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中取得極小值

3.1i=表PT中具有最小值的結(jié)點(diǎn)；

3.2對(duì)結(jié)點(diǎn)i的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作：3.2.1估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值lb;3.2.2若(lb<=up)，則將結(jié)點(diǎn)x加入表PT中；否則丟棄該結(jié)點(diǎn)；4.將葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)值輸出，回溯求得最優(yōu)解的各個(gè)分量；分支限界法求解TSP問題的算法多段圖的最短路徑問題

問題描述：設(shè)圖G=(V,E)是一個(gè)帶權(quán)有向連通圖，如果把頂點(diǎn)集合V劃分成k個(gè)互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一條邊(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,

1＜i+m≤k），則稱圖G為多段圖，稱s∈V1為源點(diǎn)，t∈Vk為終點(diǎn)。多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。1203456789492386884756866537求解過程：1.應(yīng)用貪心法求得近似解為0→2→5→8→9，其路徑代價(jià)為2+7+6+3=18，這可以作為多段圖最短路徑問題的上界。把每一段最小的代價(jià)相加，可以得到一個(gè)非常簡(jiǎn)單的下界，其路徑長度為2+4+5+3=14。于是，得到了目標(biāo)函數(shù)的界[14,18]。2.一般情況下，對(duì)于一個(gè)正在生成的路徑，假設(shè)已經(jīng)確定了前i段（1≤i≤k），其路徑為(r1,r2,…,ri,ri+1)，此時(shí)，該部分解的目標(biāo)函數(shù)值的計(jì)算方法即限界函數(shù)如下：如果部分解包含路徑01，則第1段的代價(jià)已經(jīng)確定，并且在下一段只能從頂點(diǎn)1出發(fā)，最好的情況是選擇從頂點(diǎn)1出發(fā)的最短邊，則該部分解的下界是lb=4+8+5+3=20。求解過程：分支限界法求解多段圖的最短路徑問題，搜索空間：分支限界法求解多段圖的最短路徑問題，搜索過程？組合問題中的分支限界法—0/1背包問題問題描述：給定n種物品和一個(gè)容量為W的背包，物品i的重量是wi,其價(jià)值為vi,對(duì)每種物品i只有兩種選擇：裝入背包或不裝入背包，如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?1確定目標(biāo)函數(shù)上、下界；2確定目標(biāo)函數(shù)計(jì)算方法；一般情況下,假設(shè)當(dāng)前已對(duì)前i個(gè)物品進(jìn)行了某種特定的選擇,且背包中已裝入物品的重量是w,獲得的價(jià)值是v,計(jì)算該結(jié)點(diǎn)的目標(biāo)函數(shù)上界的一個(gè)簡(jiǎn)單方法是，將背包中剩余容量全部裝入第i+1個(gè)物品,并可以將背包裝滿,于是,得到限界函數(shù)：想法：3依上計(jì)算從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值直到表PT中取得極大值。分支限界法求解0/1背包問題，搜索空間：搜索過程？分支限界法求解0/1背包問題算法1.根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的上界up；采用貪心法得到下界down；2.計(jì)算根結(jié)點(diǎn)的目標(biāo)函數(shù)值并加入待處理結(jié)點(diǎn)表PT；3.循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中取極大值

3.1i=表PT中具有最大值的結(jié)點(diǎn)；

3.2對(duì)結(jié)點(diǎn)i的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作：3.2.1如果結(jié)點(diǎn)x不滿足約束條件，則丟棄該結(jié)點(diǎn)；3.2.2否則，估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值lb，將結(jié)點(diǎn)x加入表PT中；4.將葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)值輸出，回溯求得最優(yōu)解的各個(gè)分量；問題描述：任務(wù)分配問題要求把n項(xiàng)任務(wù)分配給n個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。組合問題中的分支限界法—任務(wù)分配問題任務(wù)分配問題的實(shí)例C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d任務(wù)分配成本矩陣如下：

應(yīng)用貪心法求得一個(gè)合理的上界2+3+5+4=14，將每一行的最小元素加起來就得到解的下界2+3+1+4=10。最優(yōu)值一定是[10,14]之間的某個(gè)值。設(shè)當(dāng)前已對(duì)人員1～i分配了任務(wù)，并且花費(fèi)了成本v，則限界函數(shù)可以定義為：想法：假設(shè)已經(jīng)將任務(wù)2分配給人員a，任務(wù)3分配給人員b，花費(fèi)的成本是5，則該部分解可能獲得的最小成本是5+(1+4)=10。分支限界法求解任務(wù)分配問題，搜索空間：搜索過程？組合問題中的分支限界法—批處理作業(yè)調(diào)度問題問題描述：給定n個(gè)作業(yè)的集合J={J1,J2,…,Jn}，每個(gè)作業(yè)都有3項(xiàng)任務(wù)分別在3臺(tái)機(jī)器上完成，作業(yè)Ji需要機(jī)器j的處理時(shí)間為tij（1≤i≤n,1≤j≤3），每個(gè)作業(yè)必須先由機(jī)器1處理，再由機(jī)器2處理，最后由機(jī)器3處理。批處理作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)處理順序，使得從第1個(gè)作業(yè)在機(jī)器1上處理開始，到最后一個(gè)作業(yè)在機(jī)器3上處理結(jié)束所需的時(shí)間最少。批處理作業(yè)的一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器1沒有空閑時(shí)間，且機(jī)器2和機(jī)器3的空閑時(shí)間最小。可以證明，存在一個(gè)最優(yōu)作業(yè)調(diào)度使得在機(jī)器1、機(jī)器2和機(jī)器3上作業(yè)以相同次序完成。想法：

T＝

57910529957810J1J2J3J4機(jī)器1機(jī)器2機(jī)器3批處理作業(yè)調(diào)度問題的實(shí)例。上界確定的方法：可以隨機(jī)產(chǎn)生幾個(gè)調(diào)度方案，從中選取具有最短完成時(shí)間的調(diào)度方案作為近似最優(yōu)解。J4:7J1:5J3:9J2:10機(jī)器1機(jī)器2機(jī)器3空閑:7J4:8J1:7J3:9J2:5空閑:15J4:10

J1:9J3:5J2:2分支限界法求解批處理作業(yè)調(diào)度問題的關(guān)鍵在于限界函數(shù)，即如何估算部分解的下界?？紤]理想情況，機(jī)器1和機(jī)器2無空閑，最后處理的恰好是在