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

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

3.1i=表PT中具有最小值的結點；

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

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

3.1i=表PT中具有最大值的結點；

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

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

T＝

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

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