1、第九章 分支限界法1234概述圖問題中的分支限界法組合問題中的分支限界法小結9.1 概述 9.1.1 分枝限界法的設計思想 9.1.2 分枝限界法的時間性能9.1.3 一個簡單例子 -圓排列問題 分支限界法按廣度優先策略搜索問題的解空間樹，在搜索過程中，對待處理的結點根據限界函數估算目標函數的可能取值，從中選取使目標函數取得極值（極大或極小）的結點優先進行廣度優先搜索，從而不斷調整搜索方向，盡快找到問題的解。 分支限界法適用于求解最優化問題。 確定一個合理的限界函數，并根據限界函數確定目標函數的界down, up。 按照廣度優先策略搜索問題的解空間樹，在分支結點上，依次擴展該結點的所有孩子結點

2、，分別估算這些孩子結點的目標函數的可能取值，某孩子結點的目標函數的可能取值超出目標函數的界，則將其丟棄；否則，將其加入待處理結點表（以下簡稱表PT）中。 依次從表PT中選取使目標函數取得極值的結點成為當前擴展結點，重復上述過程，直至找到最優解。9.1.1 分支限界法的設計思想分支限界法需要解決的關鍵問題 如何確定合適的限界函數。（提示：計算簡單，減少搜索空間，不丟解） 如何組織待處理結點表。（提示：表PT可以采用堆的形式，也可以采用優先隊列的形式存儲。各有什么特點？） 如何確定最優解的各個分量。（提示：跳躍式處理解空樹結點，必須保存搜索過程中經過的路徑信息。） 回溯法從根結點出發，按照深度優先

3、策略遍歷問題的解空間樹。分支限界法按廣度優先策略搜索問題的解空間樹。二者與蠻力法區別？回溯法與分支限界法區別？ 一般情況下，在問題的解向量X=(x1, x2, , xn)中，分量xi (1in)的取值范圍為某個有限集合Si=ai1, ai2, , airi，因此，問題的解空間由笛卡兒積A=S1S2Sn構成，并且第1層的根結點有|S1|棵子樹，則第2層共有|S1|個結點，第2層的每個結點有|S2|棵子樹，則第3層共有|S1|S2|個結點，依此類推，第n+1層共有|S1|S2|Sn|個結點，他們都是葉子結點，代表問題的所有可能解。9.1.2 分支限界法的時間性能 類比回溯法分析分支限界法的時間性能

4、11111100000001圖8.2 0/1背包問題的解空間樹對物品1的選擇對物品3的選擇對物品2的選擇12345781112141531069例如：對于n=3的0/1背包問題解空間樹 分支限界法和回溯法實際上都屬于蠻力窮舉法，當然不能指望它有很好的最壞時間復雜性，遍歷具有指數階個結點的解空間樹，在最壞情況下，時間復雜性肯定為指數階。 與回溯法不同的是，分支限界法首先擴展解空間樹中的上層結點，并采用限界函數，有利于實行大范圍剪枝，同時，根據限界函數不斷調整搜索方向，選擇最有可能取得最優解的子樹優先進行搜索。所以，如果選擇了結點的合理擴展順序以及設計了一個好的限界函數，分支界限法可以快速得到問題

5、的解。 分支限界法的較高效率是以付出一定代價為基礎的，其工作方式也造成了算法設計的復雜性。首先，一個更好的限界函數通常需要花費更多的時間計算相應的目標函數值，而且對于具體的問題實例，通常需要進行大量實驗，才能確定一個好的限界函數；其次，由于分支限界法對解空間樹中結點的處理是跳躍式的，因此，在搜索到某個葉子結點得到最優值時，為了從該葉子結點求出對應的最優解中的各個分量，需要對每個擴展結點保存該結點到根結點的路徑，或者在搜索過程中構建搜索經過的樹結構，這使得算法的設計較為復雜；再次，算法要維護一個待處理結點表PT，并且需要在表PT中快速查找取得極值的結點，等等。這都需要較大的存儲空間，在最壞情況下

6、，分支限界法需要的空間復雜性是指數階。 9.1.3 一個簡單的例子圓排列問題問題描述：給定n個圓的半徑序列，將這些圓放到一個矩形框中，各圓與矩形框的底邊相切，則圓的不同排列會得到不同的排列長度，要求找出具有最小長度的圓排列。想法：采用分支限界法求解圓排列問題，首先設計限界函數，然后在搜索過程中選擇使目標函數取得極值的結點優先進行擴充。 9.2 圖問題中的分支限界法 9.2.1 TSP問題 9.2.2 多段圖的最短路徑問題問題描述：TSP問題是指旅行家要旅行n個城市，要求各個城市經歷且僅經歷一次然后回到出發城市，并要求所走的路程最短。9.2.1 TSP問題 想法： 確定目標函數的界down, u

7、p 。（提示：如何確定上、下界？） 確定目標函數值的計算方法（限界函數）。 基于上、下界，按分支限界法設計思想，搜索解空間樹，得到最優解。圖9.5(a)所示是一個帶權無向圖，(b)是該圖的代價矩陣。271563134253984C= 3 1 5 83 6 7 91 6 4 25 7 4 38 9 2 3 (a) 一個無向圖 (b) 無向圖的代價矩陣圖 9.5 無向圖及其代價矩陣1.確定問題的上界16，下界14。如何設計求上、下界策略？2.確定限界函數計算方法一般情況下，假設當前已確定的路徑為U=(r1, r2, , rk)，即路徑上已確定了k個頂點，此時，該部分解的目標函數值的計算方法如下：3

8、.基于分支限界法的思想，從根結點開始依次計算目標函數值加入待處理結點表中直至葉子結點。14,16 3 1 5 83 6 7 91 6 4 25 7 4 38 9 2 3 根據限界函數計算目標函數的下界down； 采用貪心法得到上界up；2. 計算根結點的目標函數值并加入待處理結點表PT；3. 循環直到某個葉子結點的目標函數值在表PT中取得極小值 3.1 i = 表PT中具有最小值的結點； 3.2 對結點i的每個孩子結點x執行下列操作： 3.2.1 估算結點x的目標函數值lb; 3.2.2 若(lb=up)，則將結點x加入表PT中； 否則丟棄該結點；4. 將葉子結點對應的最優值輸出，回溯求得最優

9、解的各個分量；算法描述：9.2.2 多段圖的最短路徑問題 問題描述：設圖G=(V, E)是一個帶權有向連通圖，如果把頂點集合V劃分成k個互不相交的子集Vi（2kn, 1ik），使得E中的任何一條邊(u, v)，必有uVi，vVi+m（1ik, 1i+mk），則稱圖G為多段圖，稱sV1為源點，tVk為終點。多段圖的最短路徑問題是求從源點到終點的最小代價路徑。1203456789492386884756866537求解過程：1. 應用貪心法求得近似解為02589，其路徑代價為2+7+6+3=18，這可以作為多段圖最短路徑問題的上界。把每一段最小的代價相加，可以得到一個非常簡單的下界，其路徑長度為2

10、+4+5+3=14。于是，得到了目標函數的界14, 18。2. 一般情況下，對于一個正在生成的路徑，假設已經確定了前i段（1ik），其路徑為(r1, r2, , ri, ri+1)，此時，該部分解的目標函數值的計算方法即限界函數如下： 如果部分解包含路徑01，則第1段的代價已經確定，并且在下一段只能從頂點1出發，最好的情況是選擇從頂點1出發的最短邊，則該部分解的下界是lb=4+8+5+3=20。搜索空間分支限界法求解多段圖的最短路徑問題，搜索過程？9.3 組合問題中的分支限界法 9.3.2 任務分配問題 9.3.3 批處理作業調度問題 9.3.1 0/1 背包問題 問題描述：給定n種物品和一個

11、容量為W的背包，物品i的重量是wi,其價值為vi,對每種物品i只有兩種選擇：裝入背包或不裝入背包，如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?9.3.1 0/1 背包問題 1 確定目標函數上、下界；2 確定目標函數計算方法；一般情況下,假設當前已對前i個物品進行了某種特定的選擇,且背包中已裝入物品的重量是w,獲得的價值是v,計算該結點的目標函數上界的一個簡單方法是，將背包中剩余容量全部裝入第i+1個物品,并可以將背包裝滿,于是,得到限界函數：想法：3 依上計算從根結點到葉子結點的目標函數值直到表PT中取得極大值。搜索過程？重量為4,7,5,3價值為40,42,25,12背包容量為1

12、0單位價值：10，6，5，4算法描述：1. 根據限界函數計算目標函數的上界up； 采用貪心法得到下界down；2. 計算根結點的目標函數值并加入待處理結點表PT；3. 循環直到某個葉子結點的目標函數值在表PT中取極大值 3.1 i = 表PT中具有最大值的結點； 3.2 對結點i的每個孩子結點x執行下列操作： 3.2.1 如果結點x不滿足約束條件，則丟棄該結點； 3.2.2 否則，估算結點x的目標函數值lb， 將結點x加入表PT中；4. 將葉子結點對應的最優值輸出，回溯求得最優解的各個分量；問題描述：任務分配問題要求把n項任務分配給n個人，每個人完成每項任務的成本不同，要求分配總成本最小的最優

13、分配方案。9.3.2 任務分配問題實例C9 2 7 86 4 3 75 8 1 87 6 9 4任務1 任務2 任務3 任務4人員a人員b人員c人員d任務分配成本矩陣如下： 1、 應用貪心法求得一個合理的上界2+3+5+4=14，將每一行的最小元素加起來就得到解的下界2+3+1+4=10。最優值一定是10, 14之間的某個值。2、設當前已對人員1i分配了任務，并且花費了成本v，則限界函數可以定義為：想法：假設已經將任務2分配給人員a，任務3分配給人員b，花費的成本是5，則該部分解可能獲得的最小成本是5+(1+4)=10。搜索過程？C9 2 7 86 4 3 75 8 1 87 6 9 4任務1

14、 任務2 任務3 任務4abcd 9.3.3 批處理作業調度問題問題描述：給定n個作業的集合J=J1, J2, , Jn，每個作業都有3項任務分別在3臺機器上完成，作業Ji需要機器j的處理時間為tij（1in, 1j3），每個作業必須先由機器1處理，再由機器2處理，最后由機器3處理。批處理作業調度問題要求確定這n個作業的最優處理順序，使得從第1個作業在機器1上處理開始，到最后一個作業在機器3上處理結束所需的時間最少。批處理作業的一個最優調度應使機器1沒有空閑時間，且機器2和機器3的空閑時間最小。可以證明，存在一個最優作業調度使得在機器1、機器2和機器3上作業以相同次序完成。 想法： T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4機器1 機器2 機器3實例上界確定的方法：可以隨機產生幾個調度方案，從中選取具有最短完成時間的調度方案作為近似最優解。 J4:7 J1:5 J3:9 J2:10機器1機器2機器3空閑:7 J4:8 J1:7 J3:9 J2:5空閑:15 J4:10 J1:9 J3:5 J2:2 分支限界法求解批處理作業調度問題的關鍵在于限界函