目錄

• 1.分支限界法簡介
  1.1 分支限界法的本質(zhì)——通過限界阻塞子樹
  1.2 分支限界法與回溯法的區(qū)別
  1.3 下界或者上界估算——貪心
• 2.單源最短路徑問題
  2.1 問題描述
  2.2 分支限界法解決單元最短路徑問題
• 3.裝載問題
• 4.布線問題
• 5.0-1背包問題
  5.1 問題描述
  5.2 分支限界法解決0-1背包問題
  5.3 一個示例
• 6.最大團問題
• 7 作業(yè)分配問題
  7.1 問題描述
  7.2 分支限界法步驟描述
• 8.旅行商問題
  8.1 問題描述
  8.2 分支限界法解決旅行商問題
  8.3 一個示例
• 9.電路板排列問題
• 10.批處理作業(yè)調(diào)度

1.分支限界法簡介

1.1 分支限界法的本質(zhì)——通過限界阻塞子樹

• 分支限界法通常僅關(guān)心使給定函數(shù)最大化或最小化。
• （分支限界法的本質(zhì)）因此狭握，如果算法找到了一個耗費為c的解，并且有一個部分解，它的耗費至少是c，那么就不會有該部分解的擴展生成。
• 在分支限界法中蟀悦，每一個活結(jié)點只有一次機會成為擴展結(jié)點⊙醺遥活結(jié)點一旦成為擴展結(jié)點日戈，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中孙乖，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄浙炼，其余兒子結(jié)點被加入活結(jié)點表中。
  然后唯袄，從活結(jié)點表中取下一節(jié)點（優(yōu)先隊列中最大或最小值）成為當前擴展結(jié)點弯屈，并重復(fù)上述擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止恋拷。
• （分支限界法實現(xiàn)的本質(zhì)）對某個節(jié)點進行搜索時季俩，先估算出目標的解，再確定是否向下搜索（選擇最小損耗的結(jié)點進行搜索）
  在分支結(jié)點上梅掠，預(yù)先分別估算沿著它的各個兒子結(jié)點向下搜索的路徑中酌住，目標函數(shù)可能取得的界，然后把它的這些兒子結(jié)點和它們可能取得的界保存在一張結(jié)點表中阎抒，再從表中選擇界最小或最大的結(jié)點向下搜索酪我。一般采用優(yōu)先隊列維護這張表。

1.2 分支限界法與回溯法的區(qū)別

• 回溯法
  1）（求解目標）回溯法的求解目標是找出解空間中滿足約束條件的一個解或所有解且叁。
  2）（搜索方式深度優(yōu)先）回溯法會搜索整個解空間都哭，當不滿條件時，丟棄，繼續(xù)搜索下一個兒子結(jié)點欺矫，如果所有兒子結(jié)點都不滿足纱新，向上回溯到它的父節(jié)點。
• 分支限界法
  1）（求解目標）分支限界法的目標一般是在滿足約束條件的解中找出在某種意義下的最優(yōu)解穆趴，也有找出滿足約束條件的一個解脸爱。
  2）（搜索方式）分支限界法以廣度優(yōu)先或以最小損耗優(yōu)先的方式搜索解空間。
  3）常見的兩種分支界限法
  a.隊列式（FIFO）分支界限法（廣度優(yōu)先）：按照隊列先進先出原則選取下一個結(jié)點為擴展結(jié)點
  b.優(yōu)先隊列式分支限界法（最小損耗優(yōu)先）：按照優(yōu)先隊列規(guī)定的優(yōu)先級選取優(yōu)先級最高的結(jié)點成為當前擴展結(jié)點

1.3 下界或者上界估算——貪心

• 分支限界法對下界和上界的估算未妹，總是采用貪心算法簿废，選擇當前最優(yōu)作為界加入到優(yōu)先隊列

2.單源最短路徑問題

2.1 問題描述

• 給定帶權(quán)重的有向圖G=(V, E)，圖中的每一條邊都具有非負的長度络它，求從源頂點s到目標頂點t的最短路徑問題族檬。

2.2 分支限界法解決單元最短路徑問題

• 把源頂點s作為根節(jié)點開始進行搜索。對源頂點s的所有鄰接頂點化戳，都產(chǎn)生一個分支結(jié)點单料，估計從源點s經(jīng)該鄰接頂點到達目標頂點t的距離作為該分支結(jié)點的下界
• 選擇下界最小的分支結(jié)點，對該分支結(jié)點所對應(yīng)的頂點的所有鄰接頂點繼續(xù)進行上述的搜索

2.2.1 下界估算方法（貪心）

• 假定d(node)是搜索樹中從根節(jié)點到結(jié)點node所對應(yīng)的頂點u的路徑長度点楼，頂點u的鄰接頂點為v₁, v₂, ..., v_l扫尖，而c_u,vi為頂點u到其鄰接頂點v_i(i = 1, ..., l)的距離。
  令h = min(c_u,v1, c_u,v2, ..., c_u,vl)
  則結(jié)點node的下界b(node) = d(node) + h

• 一個例子

  
  
  
  

  源頂點為a盟步，目標定的為t藏斩，把a作為根節(jié)點進行搜索：
  a->b->t距離的下界為：1+min{2, 9} = 3
  a->c->t距離的下界為：4+min{3,6,3,4} = 7
  a->d->t距離的下界為：4+min{7} = 11

  
  

2.2.2 分支限界法的步驟

將頂點編號為0, 1, ..., n-1.
每個結(jié)點包含如下信息：
??u——該節(jié)點所對應(yīng)的頂點
??path[n]——從源點開始的路徑上的頂點編號
??k——當前搜索深度下，路徑上的頂點個數(shù)
??d——從源點到本節(jié)點所對應(yīng)頂點的路徑長度
??b——經(jīng)本節(jié)點到目標頂點最短路徑的長度下界
bound——一個可行解的取值却盘，當做剪枝的標準

假定源頂點為s狰域，目標頂點為t。

• step1.初始化黄橘。建立根節(jié)點X
  X.u = s
  X.k = 1
  X.path[0] = s
  X.d = 0
  X.b = 0
  當前可行解的最短路徑下界bound置位∞兆览。
• step2.令頂點X.u所對應(yīng)的頂點為u，對u的所有鄰接頂點v_i塞关，建立兒子結(jié)點Y_i抬探，把結(jié)點X的數(shù)據(jù)復(fù)制到結(jié)點Y_i
• step3.計算Y_i的相關(guān)值
  Y_i.u = v_i
  Y_i.path[Y_i.k] = v_i
  Y_i.k = Y_i.k + 1
  Y_i.d = Y_i.d + c_u,vi
  計算h和Y_i.b
• step4.若Y_i.b < bound，轉(zhuǎn)向step5帆赢；
  否則剪去結(jié)點Y_i小压，轉(zhuǎn)向step6
• step5.把結(jié)點Y_i插入優(yōu)先隊列。如果結(jié)點Y_i.u = t椰于，表明它是問題的一個可行解怠益，用Y_i.b更新當前可行解的最短路徑長度下界bound。
• step6.取下優(yōu)先隊列首元素作為子樹的根節(jié)點X瘾婿，若X.u = t蜻牢，表明它是問題的最優(yōu)解烤咧，算法結(jié)束，數(shù)組X.path存放從源點s到目標頂點t的最短路徑上的頂點編號抢呆，X.d存放該路徑長度煮嫌，否則，轉(zhuǎn)向step2.

2.2.3 一個示例

• k=1抱虐。
  根節(jié)點0對應(yīng)于源點a昌阿，有3個鄰接頂點b、c梯码、d宝泵，其下界為3,7,11好啰，壓入優(yōu)先隊列轩娶。
• k=2。優(yōu)先隊列中下界3最小框往，對于的頂點b鳄抒，也即結(jié)點1。從頂點b繼續(xù)進行搜索椰弊。
  頂點b的鄰接頂點為c和e许溅，其下界為6和11，壓入優(yōu)先隊列秉版。
• k=3贤重。優(yōu)先隊列中下界6最小，對應(yīng)頂點c清焕，也即結(jié)點4.從頂點c繼續(xù)進行搜索并蝗。
  頂點c鄰接頂點d、e秸妥、f滚停、g，對應(yīng)的下界為13,10,8,8粥惧，壓入優(yōu)先隊列键畴。
• （回溯到了k=2）k=2。優(yōu)先隊列中7最小突雪，對應(yīng)頂點c起惕，也即結(jié)點2。從頂點c進行搜索咏删。
  頂點c鄰接頂點d惹想、e、f饵婆、g勺馆，對應(yīng)的下界為14,11,9,9戏售，壓入優(yōu)先隊列。
• k=4草穆。優(yōu)先隊列中8最小灌灾，對應(yīng)頂點f，也即結(jié)點8悲柱。
  頂點f的鄰接頂點為e锋喜、t，下界分別為9豌鸡、11嘿般，壓入棧中。其中11為一個可行解涯冠，將bound置為11.
• （回溯到了k=4）k=4炉奴。優(yōu)先隊列中8最小，對應(yīng)頂點g蛇更，也即結(jié)點9瞻赶。
  頂點g的鄰接頂點為f、t派任，下界都是10砸逊。其中10為一個可行解，將bound置為10.
• k=5.優(yōu)先隊列中9最小掌逛，對應(yīng)頂點e师逸，也即結(jié)點14.
  頂點e只有一個鄰接頂點t，下界為9豆混，從而得到一個可行解篓像，路徑長度為9，加入優(yōu)先隊列中崖叫。
  優(yōu)先隊列中最小的為9遗淳，且最后一個結(jié)點為t，因此是最優(yōu)解心傀。

3.裝載問題

4.布線問題

5.0-1背包問題

5.1 問題描述

假定n個商品重量分別為w₀, w₁, ..., w_n-1屈暗，價值分別為p₀, p₁, ..., p_n-1，背包載重量為M脂男。怎樣選擇商品組合养叛，使得價值最高？

5.2 分支限界法解決0-1背包問題

• 按價值重量比 遞減 的順序宰翅，對n個商品進行排序
  排序后商品序號的結(jié)合為S = {0, 1, ..., n-1}
• 將這些商品分為3個集合：
  S₁——選擇裝入背包的商品集合
  S₂——不選擇裝入背包的商品集合
  S₃——尚待選擇的商品集合
• S₁(k)弃甥、S₂(k)、S₃(k)分別表示在搜索深度為k時的3個集合中的商品汁讼。開始時有：
  S₁(0) = ?
  S₂(0) = ?
  S₃(0) = {0, 1, ..., n-1}

5.2.1 分支方法（二叉分支）

• 假設(shè)比值p_i/w_i最大的商品序號為s（s ∈ S₃）淆攻，用s進行分支阔墩，一個分支結(jié)點表示把商品s裝入背包，另一個分支結(jié)點表示不把商品s裝入背包瓶珊。
  當商品按照價值重量比遞減排序后啸箫，s就是集合S₃(k)中的第一個元素。特別地伞芹，當搜索深度為k時忘苛，商品s的序號就是集合S中的元素k。
• 把商品s裝入背包的分支結(jié)點
  S₁(k+1) = S₁(k) ∪ {k}
  S₂(k+1) = S₂(k)
  S₃(k+1) = S₃(k) - {k}
• 不把商品s裝入背包的分支結(jié)點
  S₁(k+1) = S₁(k)
  S₂(k+1) = S₂(k) ∪ {k}
  S₃(k+1) = S₃(k) - {k}

5.2.2 上界估算方法（貪心）

• 假定b(k)表示在搜索深度為k時唱较，某個分支結(jié)點的背包中商品的價值上界扎唾。
  此時S₃(k) = {k, k+1, ..., n-1}。用如下方法計算兩種分支結(jié)點背包中商品價值的上界：
  
• 上述公式的理解
  1）按照一個商品是否加入到S₁集合南缓，總共有2ⁿ個葉子節(jié)點胸遇，每個葉子節(jié)點對應(yīng)一種情況
  2）當一層一層向下搜索是，如果當前S₁集合中的總重量超過了載重量M西乖，則直接將b(k)置為0狐榔，該分支終止坛增。
  為什么這樣做获雕？因為在搜索上一層時，該商品不應(yīng)該加入到S₁集合收捣，這種不加入該商品情況對應(yīng)于另一個分支届案。加入該商品的此分支已經(jīng)不滿足要求了，所以剪枝罢艾。

5.2.3 分支限界法求解步驟

每個結(jié)點都包含如下信息：
??S₁——當前選擇裝入背包的商品集合
??S₂——當前不選擇裝入背包的商品集合
??S₃——當前尚待選擇的商品集合
??k——搜索深度
??b——上界
bound——一個可行解的取值楣颠，當做剪枝的標準

• step1.bound = 0，把商品按價值重量比遞減排序
• step2.建立根節(jié)點X
  X.b = 0
  X.k = 0
  X.S₁ = ?
  X.S₂ = ?
  X.S₃ = S
• step3. 若X.k == n咐蚯，算法結(jié)束童漩，X.S₁即為裝入背包中的物體，X.b即為裝入背包中物體的最大價值春锋；
  否則轉(zhuǎn)向step4
• （分支1）step4.建立結(jié)點Y
  Y.S₁ = X.S₁ ∪ {X.k}
  Y.S₂ = X.S₂
  Y.S₃ = X.S₃ - {X.k}
  Y.k = X.k + 1
  計算Y.b矫膨，將Y.b與bound進行比較，據(jù)此判定是否插入優(yōu)先隊列期奔；當S₃為空時侧馅，找到一個可行解，判定是否更新bound呐萌。
• （分支2）step5.建立結(jié)點Z
  Z.S₁ = X.S₁
  Z.S₂ = X.S₂ ∪ {X.k}
  Z.S₃ = X.S₃ - {X.k}
  Z.k = Z.k + 1
  計算Z.b馁痴，將Z.b與bound進行比較，據(jù)此判定是否插入優(yōu)先隊列肺孤；當S₃為空時罗晕，找到一個可行解济欢，判定是否更新bound。
• step6.取出優(yōu)先隊列首元素作為結(jié)點X小渊，轉(zhuǎn)向step3

5.3 一個示例

• 有5個商品船逮，重量分別為8,16,21,17,12，價值分別為8,14,16,11,7粤铭，背包的載重量為37挖胃，求裝入背包的商品及其價值。

  
  

6.最大團問題

7 作業(yè)分配問題

7.1 問題描述

• n個操作員（編號：0, 1, ..., n-1）以n種不同時間完成n項不同作業(yè)（編號：0, 1, ..., n-1）梆惯，要求分配每位操作完成一項作業(yè)酱鸭，使完成n項作業(yè)的時間總和最少。
• c_ij表示第i位操作員完成第j號作業(yè)所需的時間垛吗。
• 用向量x來描述分配給操作員的作業(yè)編號凹髓，如分量x_i表示分配給第i位操作員的作業(yè)編號。

7.2 分支限界法步驟描述

• （估算下界怯屉，放到優(yōu)先隊列）從根節(jié)點開始向下搜索蔚舀，在整個搜索過程中，每遇到一個結(jié)點锨络，對其所有兒子結(jié)點計算它們的下界赌躺，把它們記錄在結(jié)點表中。
• （從優(yōu)先隊列取最值羡儿，重復(fù)操作）從表中選取最小的結(jié)點礼患，并重復(fù)上述過程。
• （葉節(jié)點是否是最優(yōu)解的判定）當搜索到一個葉子節(jié)點掠归，如果該節(jié)點的下界是結(jié)點表中最小的缅叠，那么該節(jié)點就是問題的最優(yōu)解。
  否則虏冻，對下界最小的結(jié)點繼續(xù)進行擴展肤粱。

7.2.1 下界估算方法（類似于貪心，是一種最小估算方法）

• 假定k表示搜索深度厨相，當k = 0领曼，從根節(jié)點開始向下搜索。若將0號作業(yè)(j = 0)分配給第i位操作員(0 ≤ i ≤ n-1)领铐，其余作業(yè)分配給其余操作員悯森，則所需時間至少為：第i位操作員完成第0號作業(yè)的時間 + 其余n-1項作業(yè)分配給其余n-1位操作員單獨完成時所需最短時間之和。（下式中l(wèi)是任意的绪撵，只要不等于i即可）
  
  
  下圖中瓢姻，若將第0號作業(yè)分配給第0位操作員，c₀₀ = 3音诈，此時所需時間下界為： 3 + 7（1號作業(yè)給其余三位操作員完成最短時間） + 6（2號作業(yè)給其余三位操作員完成最短時間） + 3（3號作業(yè)給其余三位操作員完成最短時間） = 19
  
  一個示例
• 一般的幻碱，當搜索深度為k绎狭，前面第0, 1, ..., k-1號作業(yè)已經(jīng)分別分配給編號i₀, i₁, ..., i_k-1的操作員。令S = {0, 1, ..., n-1}表示所有操作員的編號集合褥傍；m_k-1 = {i₀, i₁, ..., i_k-1}表示作業(yè)已分配的操作員的編號集合儡嘶。當把k號作業(yè)分配給編號為i_k的操作員時，i_k ∈ S - m_k-1恍风。顯然蹦狂，其下界為：
  

7.2.2 分支限界法求解作業(yè)分配問題

每個結(jié)點包含如下信息：
??m——已分配作業(yè)的操作員編號集合
??S——未分配作業(yè)的操作員編號集合
??x——操作的分配方案向量x，分量x_i表示分配給第i位操作員的作業(yè)編號朋贬。
??k——搜索深度（表示分配的第k號作業(yè)）
??t——所需時間的下界
bound——一個可行解的取值凯楔，當做剪枝的標準

• step1.開始步驟。建立根節(jié)點X
  X.k = 0
  X.S = {0, 1, ..., n-1}
  X.m = ?
  把當前問題的可行解的最優(yōu)時間下界bound置位∞锦募。
• step2.對所有操作員i（i ∈ X.S）摆屯，建立兒子結(jié)點Y_i，把結(jié)點X的數(shù)據(jù)復(fù)制到Y(jié)_i
• step3. 修改Y_i的值
  Y_i.m = Y_i.m ∪ {i}
  Y_i.s = Y_i.S - {i}
  Y_i.x_i= Y_i.k （表示將第k號作業(yè)分給第i號操作員）
  Y_i.k= Y_i.k + 1
  并計算Y_i.t
• step4.若Y_i.t < bound糠亩，轉(zhuǎn)step5虐骑；
  否則剪去結(jié)點Y_i，轉(zhuǎn)step6
• step5.把結(jié)點Y_i插入優(yōu)先隊列赎线，如果結(jié)點Y_i是葉節(jié)點廷没，表明它是問題的一個可行解，用Y_i.t更新當前可行解的最優(yōu)時間下界bound氛驮。
• step6.取下隊列首元素作為子樹的根節(jié)點X腕柜，若X.k = n，則該節(jié)點是葉節(jié)點矫废，表明它是問題的最優(yōu)解，算法結(jié)束砰蠢，向量X.x便是作業(yè)最優(yōu)分配方案蓖扑；否則轉(zhuǎn)向step2.

7.2.3 一個實例

考慮如圖所示的4個操作員的作業(yè)最優(yōu)分配方案

• 當k = 0時律杠，有
  t₀₀ = 3 + 7 + 6 + 3 = 19
  t₁₀ = 9 + 7 + 4 + 3 = 23
  t₂₀ = 8 + 7 + 4 + 5 = 24
  t₃₀ = 12 + 7 + 4 + 3 = 26
  將這四個結(jié)點插入優(yōu)先隊列
• 當k = 1時，結(jié)點2（把0號作業(yè)分給0號操作員）的下界做小竞惋，將其取出柜去，并由它向下繼續(xù)搜索
  t₁₁ = 3 + 12 + 6 + 3 = 24
  t₂₁ = 3 + 7 + 6 + 5 = 21
  t₃₁ = 3 + 7 + 9 + 3 = 22
  將這三個結(jié)點插入優(yōu)先隊列
• 當k =2時，結(jié)點7（把1號作業(yè)分給2號操作員）的下界最小拆宛，將其取出嗓奢，并由它向下繼續(xù)搜索
  t₁₂ = 3 + 7 + 13 + 8 = 31
  t₃₂ = 3 + 7 + 6 + 5 = 21
  將這兩個結(jié)點插入優(yōu)先隊列
• 當k = 3時，結(jié)點10（將2號作業(yè)分給3號操作員）的下界最小浑厚，將其取出股耽，并由它向下繼續(xù)搜索
  t₁₃ = 3 + 7 + 6 + 5 = 21
  將其插入隊列中根盒。
  因為它是隊列中最小的結(jié)點，所以將其取出物蝙，又因為是葉子節(jié)點炎滞，所以是最優(yōu)解。(分量x_i表示分配給第i位操作員的作業(yè)編號诬乞。)
  x₀ = 0, x₁ = 3, x₂ = 1, x₃ = 2

8.旅行商問題

8.1 問題描述

8.1.1 問題描述

• 一個售貨員必須訪問n個城市册赛，恰好訪問每個城市一次，并最終回到出發(fā)城市震嫉。
  售貨員從城市i到城市j的旅行費用是一個整數(shù)击奶，旅行所需的全部費用是他旅行經(jīng)過的的各邊費用之和，而售貨員希望使整個旅行費用最低责掏。
• （等價于求圖的最短哈密爾頓回路問題）令G=(V, E)是一個帶權(quán)重的有向圖柜砾，頂點集V=(v₀, v₁, ..., v_n-1)。從圖中任一頂點v_i出發(fā)换衬，經(jīng)圖中所有其他頂點一次且只有一次痰驱，最后回到同一頂點v_i的最短路徑。
• c——費用矩陣（鄰接矩陣）瞳浦，c_ij表示頂點v_i到頂點v_j的關(guān)聯(lián)邊的長度担映。

8.1.2 費用矩陣的特性及規(guī)約

• 令G=(V, E)是一個帶權(quán)重的有向圖，l是圖G的一條哈密爾頓回路叫潦，c是圖G的費用矩陣蝇完，則回路上的邊對應(yīng)于費用矩陣c中每行每列各一個元素。
  證明：因為l上面的每個頂點v_i有且僅有一條入邊和出邊矗蕊，入邊表示費用矩陣第i列僅有一個元素對應(yīng)短蜕，出邊表示費用矩陣第i行僅有一個元素對應(yīng)。
• 費用矩陣c的第i行（或第j列）中的每個元素減去一個整數(shù)lh_i（或ch_j）傻咖，得到一個新的費用矩陣c'朋魔。使得c'中第i行（或第j列）中的最小元素為0，稱為費用矩陣的行歸約（或列歸約）卿操。稱lh_i為行歸約常數(shù)警检，ch_j為列歸約常數(shù)。
  

• 對費用矩陣c的每一行和每一列都進行行歸約和列歸約害淤，得到一個新的費用矩陣c'扇雕，使得c'中每一行和每一列至少都有一個元素0，稱為費用矩陣的歸約窥摄。矩陣c'稱為費用矩陣c的歸約矩陣镶奉，稱常數(shù)h為矩陣c的歸約常數(shù)。

  
  
• 令G=(V, E)是一個帶權(quán)重的有向圖，l是圖G的一條哈密爾頓回路腮鞍，c是G的費用矩陣值骇，w(l)是以費用矩陣c計算的這條回來的費用。如果c'是費用矩陣c的歸約矩陣移国，歸約常數(shù)為h吱瘩，w'(l)是以費用矩陣c'計算的這條回路的費用。則有：
  w(l) = w'(l) + h
• 令G=(V, E)是一個帶權(quán)重的有向圖迹缀，l是圖G的一條最短哈密爾頓回路使碾，c是G的費用矩陣，c'是c的歸約矩陣祝懂，G'是與c'對應(yīng)的圖票摇，c'是G'的費用矩陣，則l是G'的一條最短的哈密爾頓回路砚蓬。

8.2 分支限界法解決旅行商問題

8.2.1 分支方法（二叉分支）

• （分支1）選取沿著某一條邊出發(fā)的路徑矢门，作為進行搜索的一個分支結(jié)點
• （分支2）不沿這條邊的其他所有路徑集合，作為進行搜索的另一個分支結(jié)點

8.2.2 下界確定

• 假定父親結(jié)點為X灰蛙， w(X)是父親結(jié)點的下界祟剔。
  現(xiàn)在，選擇沿v_iv_j邊向下搜索作為其一個分支結(jié)點Y摩梧；
  不沿v_iv_j邊向下搜索作為另一個分支結(jié)點Y'物延。
• 分支Y：
  費用矩陣被降階和歸約，歸約常數(shù)為h仅父，則w(Y) = w(X) + h
• 分支Y'：
  將c_ij置位∞叛薯。
  同時它必然包含費用矩陣中第i行的某個元素和第j列的某個元素，令d_ij為第第i行和第j列中除c_ij之外的最小元素之和笙纤。
  如果這兩個最小元素不為零耗溜，那么也即按照這兩個元素進行歸約。本質(zhì)上d_ij也是矩陣進一步的歸約常數(shù)粪糙。
  
  
  因此有w(Y') = w(X) + d_ij强霎。

8.2.3 分支的選擇（貪心）

• 1）沿c_ij 為0的方向選擇，使所選擇的路線盡可能短蓉冈。
• 2）在多個c_ij 為0的方向中，沿d_ij最大的方向選擇轩触，使w(Y')盡可能大
  令S是費用矩陣中c_ij 為0的元素集合寞酿，D_kl是S中使d_ij達到最大的元素，即：
  
  
  即v_kl就是所要選擇的分支方向脱柱。

8.2.4 分支限界法的求解步驟

每個結(jié)點包含如下信息：
??c——歸約過后的費用矩陣
??k——費用矩陣的階數(shù)
??w——下界
??ad——頂點鄰接表
bound——一個可行解的取值伐弹，當做剪枝的標準

• step1.bound = ∞
• step2.建立父親結(jié)點X
  X.c 為費用矩陣，并進行歸約榨为，歸約常數(shù)為h
  X.k = n
  X.w = h（下界）
  X.ad頂點鄰接表
• step3.由X.c中所有為0的c_ij惨好，計算d_ij
• step4.選擇使d_ij最大的元素d_kl煌茴，選擇邊v_kl作為分支方向。
  step5是分支Y'的處理
• step5.（分支1）建立兒子結(jié)點Y'
  Y'.c = X.c日川，將Y'.c中元素c_kl置為∞蔓腐，歸約Y'.c
  Y'.ad = X.ad
  Y'.k = X.k
  計算下界Y'.w，并與bound進行比較龄句，根據(jù)比較決定是否插入優(yōu)先隊列回论。
  step6-step9是分支Y的處理
• step6.（分支2）建立兒子結(jié)點Y
  Y.c = X.c，將c_lk置為∞
  Y.ad = X.ad
  Y.k = X.k
• step7.刪除Y.c的第k行與第l列元素
  Y.k = Y.k -1
  歸約Y.c
  計算Y.w
• step8.Y.k為2分歇，直接判斷最短回路的兩條邊傀蓉，并登記Y.ad，使Y.k = 0
• step9. Y.w與bound進行比較职抡，處理是否插入優(yōu)先隊列和更新bound
• step10.取下優(yōu)先隊列元素作為結(jié)點X葬燎，若X.k為0，算法結(jié)束缚甩；否則轉(zhuǎn)向step3.

8.3 一個示例

9.電路板排列問題

10.批處理作業(yè)調(diào)度