第9章分支限界法

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

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

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

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

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

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

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

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

T＝

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

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