算法設(shè)計與分析-6分支限界法

1、第6章 分支限界法,分支限界法原理與算法框架 — 分支限界法 vs 回溯法應(yīng)用范例（1）旅行商問題（2）單源最短路徑問題（3）0-1背包問題應(yīng)用范例（略）（4）多段圖最短路徑（5）裝載問題（6）批處理作業(yè)調(diào)度問題,6.1分支限界法原理,與回溯法類似，一種基于解空間搜索的問題求解策略回溯法原理：1）利用某種數(shù)據(jù)結(jié)構(gòu)——解向量，形式化地表示問題解 e.g. n個城市旅行商問題(TSP)

2、 解向量表示為長度為n的向量x[1:n]=2）問題的各種解組成了問題解空間——最優(yōu)解、次優(yōu)解/可行 解、錯誤/不可行解、部分解,3）問題解應(yīng)滿足各種約束約束，包括: 顯約束：對解空間中分量xi的取值限定 e.g. TSP xi ∈{1,2,3,…,n} 隱約束：為滿足問題的解而對不同分量之間施加的約束 e.g. TSP，各個城市只

3、能遍歷一次4）解空間中各個解根據(jù)相互間關(guān)系 和解的構(gòu)造順序，組成解空間樹,,e.g. 4個城市的旅行商問題,,1） 非葉結(jié)點對應(yīng)部分解2）葉節(jié)點對應(yīng)最優(yōu)解、可行解,5）對解空間中的解，引入定量指標，作為優(yōu)化依據(jù) e.g. 旅行商問題：旅游路徑總長最短6）問題求解過程——帶有回溯的深度優(yōu)先樹搜索 以深度優(yōu)先的方式，從樹根結(jié)點開始，依次擴展樹結(jié)點，直到達到葉結(jié)點——搜索過程中動態(tài)產(chǎn)生解空間

4、— 深度優(yōu)先目的：盡可能快地獲得可行解,,,,擴展過程中，碰到可行非葉結(jié)點（部分解），可進一步擴展 e.g. 結(jié)點C對應(yīng)部分解 可進一步擴展為: F= G= ,碰到不可行非葉/葉結(jié)點（不可行（部分）解），需要返回到上一層結(jié)點——回溯 e.g. 對C結(jié)點，下一步的擴展有4種可能選擇：3、4、1、2，每種選擇都可以繼續(xù)擴展子樹；但只有其中2種選擇是合理的，對后2種選擇不再繼續(xù)擴展，而是返回C結(jié)點,4

5、,7）為了提高搜索效率，用剪枝函數(shù)（面向具體問題）避免無效搜索，即避免不可行解對應(yīng)的子樹或結(jié)點e.g. 剪枝條件/約束1： 如果當前正在考慮的頂點j與當前路徑中的末端結(jié)點i沒有邊相連，即w[i, j]= ∞, 則不必搜索j所在分支 E.g. 當前已有的部分路徑為, ,路徑末端結(jié)點為2, 下一步可考慮將頂點3、4加入到部分路徑中。 但是，頂點2與4間無邊，w(2,4)= ∞, 因此在解空間樹中，可以不必考慮頂點4

6、所在分支,剪枝條件2：假設(shè)：已經(jīng)知道直到第i-1層的部分解 ,從第i-1層結(jié)點選擇頂點x[i]，并向該分支往下搜索的界限函數(shù)為： B(i) = cw(i-1) + w(x[i-1], x[i]) 由此得到剪枝/約束條件2： 如果B(i) ≥ bestw, 則停止搜索x[i]分支及其下面的層 ，其中，bestw代表到目前為止,在前面的搜索中，從其

7、它已經(jīng)搜索過的路徑中，找到的最佳回路的權(quán)和（總長度）,分支限界法（branch and bound）原理：1）按寬度優(yōu)先策略遍歷解空間樹。2）在遍歷過程中，對處理的每個結(jié)點vi，根據(jù)界限函數(shù)，估計沿該結(jié)點向下搜索所可能達到的完全解的目標函數(shù)的可能取值范圍—界限bound(vi)=[downi, upi]3）從中選擇使目標函數(shù)取的極值（最大、最?。┑慕Y(jié)點優(yōu)先進行寬度優(yōu)先搜索，從而不斷調(diào)整搜索方向，盡快找到問題解關(guān)鍵：各結(jié)點的界限

8、函數(shù)bound(vi)=[downi, upi], 依據(jù)具體問題而定e.g. 4個城市的TSP搜索樹中的界限函數(shù),bound(G),bound(D),bound(E),子樹,子樹,子樹,一、與回溯法類似，解向量、解空間、解空間樹二、解空間樹中的結(jié)點分為4種類型 活結(jié)點，死結(jié)點，擴展結(jié)點，待處理結(jié)點,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,擴展結(jié)點,,未處理結(jié)點,— 活結(jié)點

9、 當前滿足約束條件、未來有可能產(chǎn)生最優(yōu)解的結(jié)點； 對應(yīng)部分解, e.g. 結(jié)點G、D、E 所有活結(jié)點組成活結(jié)點表ANT (Alive Node Table),— 擴展結(jié)點 從活結(jié)點表ANT中取出來，當前準備進行擴展的結(jié)點，即當前進行處理的結(jié)點 1）評估每個活結(jié)點價值，按照價值最大化/最小化原則，從 ANT中選取擴展結(jié)點 e_node 2）e_n

10、ode擴展方式： 寬度優(yōu)先，生成e_node的全部子節(jié)點； 評估這些子節(jié)點，滿足界限約束、有可能產(chǎn)生更優(yōu)解的 結(jié)點被作為活結(jié)點，加入ANT；不滿足約束、或無法產(chǎn)生 最優(yōu)解的子節(jié)點被舍棄——剪枝 3） e_node結(jié)點被擴展后，該結(jié)點轉(zhuǎn)換為死結(jié)點，以后將不會 被再搜索 活結(jié)點?擴展結(jié)點?死結(jié)點,e.g. 如下圖

11、i) 從上圖中的3個活結(jié)點G、D、E中，選擇價值最大的結(jié)點D，作為擴展結(jié)點,ii) 生成D的全部2個子結(jié)點H、I，經(jīng)評估后，作為活結(jié)點加入 ADT表中iii) D變?yōu)樗澜Y(jié)點,B,C,F,E,L,,,,,2,3,4,4,A,,1,,4,G,,3,,,,,第1步,第2步,第3步,第4步,H,I,,,D,,,,,,,2,4,— 死結(jié)點： 1）已經(jīng)處理過（搜索過）、不再處理的結(jié)點; e.g. A, B, C, F, L 2

12、）不滿足約束條件、無法產(chǎn)生最優(yōu)解的結(jié)點. e.g. 結(jié)點G, 對應(yīng)部分解, 而 w(4,3)=∞,— 未處理結(jié)點 解空間樹中位于活結(jié)點之下，還沒有被搜索/處理到、不屬于上述三類結(jié)點的其它結(jié)點 在后續(xù)的搜索過程中，通過結(jié)點擴展會逐步生成,三、解空間樹的擴展 選定擴展結(jié)點e_node，生成其全部子結(jié)點——采取寬度優(yōu)先進行擴展 e.g. 結(jié)點D對應(yīng)于，考察它的2個子結(jié)點和,四、對擴展結(jié)點e_n

13、ode，生成其全部兒子結(jié)點后，判斷評估每個兒子結(jié)點： i) 是否滿足約束條件。如不滿足，則作為死結(jié)點 ii）估算沿著兒子結(jié)點向下搜索時，目標函數(shù)可能取得的“界”，即沿著兒子結(jié)點向下構(gòu)造出的最終解可能取得的目標函數(shù)的范圍； -極大化目標，估計子節(jié)點目標函數(shù)上界 -極小化目標，估計子節(jié)點目標函數(shù)下界 iii）將全部活結(jié)點組織在活結(jié)點表ANT中 利用活結(jié)點的“界”值，對活結(jié)點進行價值評

14、估——是否有可能得到最優(yōu)解？ 關(guān)鍵：目標函數(shù)——界限函數(shù)！！,五、擴展結(jié)點e_node選取 擴展樹時，需要從活結(jié)點表ANT中選取合適的活結(jié)點，將其轉(zhuǎn)化為擴展結(jié)點e_node 1) 對最小化問題（如TSP），選取具有最小“界”的活結(jié)點 e.g. 前圖中，部分解D的最小界：經(jīng)過D的最短路徑長度至少（下界）是多少 2) 對最大化問題（如背包問題），選取具有最大“界”的活結(jié)點，物品裝入方案的最大價值

15、 e.g. 3) 當?shù)竭_1個葉結(jié)點時，得到1個可行解，該可行解對應(yīng)的最優(yōu)值bound(x1,x2,…,xn)可作為當前最優(yōu)解的1個“界”,六、結(jié)點界限函數(shù)及剪枝 進行結(jié)點/樹擴展時，利用界限函數(shù)估計每個結(jié)點可能達到的最優(yōu)解，進行剪枝 1) 估計e_node的每個兒子結(jié)點ci的“界”bound(ci) -極大化目標，估計子結(jié)點目標函數(shù)上界 -極小化目標，估計子結(jié)點目標函數(shù)下界 2)

16、 比較bound(ci)與活結(jié)點表ANT中現(xiàn)有活結(jié)點*的最優(yōu)界限值bound(*) — 對最小化問題，e.g. 最短路徑，如果bound(ci) > bound(*)，沿ci搜索得到可行解不可能小于目前已經(jīng)得到的最優(yōu)解，則結(jié)點ci不應(yīng)加入活結(jié)點表——剪枝，不考慮該結(jié)點,e.g. 已知 的路徑總和=20；結(jié)點G對應(yīng)如果路徑1-2-4的總長=21，則結(jié)點G被舍棄— 對最大化問題， e.g. 背包問題

17、，如果bound(ci) < bound(*)，沿ci搜索得到可行解不可能大于目前已經(jīng)得到的最優(yōu)解，則結(jié)點ci不應(yīng)加入活結(jié)點表——剪枝，不考慮該結(jié)點,分支限界法算法框架— 以最大化問題為例，e.g. 背包問題1. 選擇根節(jié)點v0，根據(jù)限界函數(shù)bound，估計根節(jié)點的目標函數(shù)上下界bound(v0), 確定目標函數(shù)的界[down, up]2. 將活結(jié)點表ANT初始化為空3. 生成根結(jié)點v0的全部子結(jié)點-寬度優(yōu)先；對每個子

18、結(jié)點x，執(zhí)行以下操作 3.1 估算x的目標函數(shù)值（上界） bound(x) 3.2 若 （bound(x)>= down），將x加入ANT表 /* 對最大化問題，要求沿x分支搜索到的完全解的目標值（上界）估計必須大于現(xiàn)有已知的目標函數(shù)的下界down,循環(huán)，直到某個葉結(jié)點的目標函數(shù)值在表ANT中最大 /* 找到1個具有最大值的完全

19、解 4.1 從表ANT中選擇bound(vi)值最大的結(jié)點vi ，擴展其子結(jié)點 /* 從活結(jié)點表中，選擇1個具有最大可能目標值的擴展結(jié)點vi 4.2 對結(jié)點vi的每個子結(jié)點c，執(zhí)行下列操作 4.2.1 估算c的目標函數(shù)值bound(c)-上界 4.2.2 如果（bound(c)>= down），將c加入ANT表

20、 /*子結(jié)點c有可能產(chǎn)生更優(yōu)的解，將其加入活結(jié)點 表，以后考慮對其進行擴展 4.2.3 如果（c是葉結(jié)點 and bound(c)在表ANT中最大）， 則將結(jié)點c對應(yīng)的完全解輸出，算法結(jié)束 /* 結(jié)點c對應(yīng)了1個新找到的、具有最大目標

21、 函數(shù)值的完全解——最優(yōu)解,4.2.4 如果（c是葉結(jié)點 and bound(c)在表ANT中不是最 大），則： /*結(jié)點c對應(yīng)了1個新找到的完全解，但該完全解的目標 函數(shù)值與已經(jīng)找到的、或未來可能找到完全解相比，并非更優(yōu)

22、 i) 令down = value(c) /*利用新找到的完全解的實際目標函數(shù)，更新問題的下界 ii) 對表ANT中所有滿足bound(vj)< bound(c)的結(jié)點vj， 從表ANT中刪除該結(jié)點?。?！ /* 利用新找到的完全解的目標函數(shù)bou

23、nd(c) ，進行剪枝，從ANT 表中去掉那些目標函數(shù)值不可能大于結(jié)點c的bound(c)的結(jié)點vj， 即去掉那些目標函數(shù)值小于由于當前新找到的完全解c的目標值 bound(c)的結(jié)點,分支限界法是一種高效、通用的問題求解方法。此方法發(fā)明者曾獲計算機界最高獎項圖靈獎。分支限界法

24、三個關(guān)鍵技術(shù)1. 如何確定合適的限界函數(shù) 面向具體問題而定2. 如何合理組織活結(jié)點表——決定了結(jié)點擴展順序 1）FIFO隊列：按照先進先出（FIFO）原則，選取下一個節(jié)點為擴展節(jié)點 2）優(yōu)先隊列：按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點，成為當前擴展節(jié)點。 3）堆,3. 如何確定最優(yōu)解中的各個分量 對解空間樹中的結(jié)點處理是根據(jù)結(jié)點的bound值進行的，

25、有可能是跳躍式的，回溯也不是單純沿著雙親結(jié)點一層層向上回溯。因此，當在某個葉結(jié)點上搜索到全局最優(yōu)值時，有可能無法得到組成該最優(yōu)解的各個分量。 為此，可采用下述處理方法： 1）對每個擴展結(jié)點，保存從根結(jié)點到該結(jié)點的路徑 2）在搜索過程中，構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)。當求得最優(yōu)解后，從葉結(jié)點回溯到根結(jié)點，得到最優(yōu)解各個分量 問題：用于存儲搜索樹的存儲空間可能會很大，增大了算法的空間復雜性,B,C,F,D,L

26、,,,,,2,3,4,4,A,,1,,4,G,,3,E,,,,,,,H,I,,,2,4,,,根據(jù)活結(jié)點表中各節(jié)點具體bound值，先處理D，后處理E，基本符合寬度優(yōu)先序序,根據(jù)活結(jié)點表中各節(jié)點具體bound值，先處理E，后處理D，不符合寬度優(yōu)先序序,分支限界法 vs 回溯法,求解目標： 回溯法的求解目標是找出解空間樹中滿足約束條件的所有（？？或多個）解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足

27、約束條件的解中找出在某種意義下的最優(yōu)解。,2. 搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。,3. 解空間樹的擴展 對擴展結(jié)點e_node，生成其全部子結(jié)點——采取寬度優(yōu)先或以最小耗費（最大效益）優(yōu)先進行擴展，需要維護活結(jié)點表，因此占用的空間比回溯法大，但計算速度一般比回溯法快——以空間換時間！！,此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴

28、展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。,在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。,6.2最短路徑問題,問題描述： 在下圖所給的有向圖G中，每一邊都有一個非負邊權(quán)。 要求：求出從源點s到目標點t之間的最短路徑。,用優(yōu)先隊列式分支限界

29、法，解空間樹：1） 樹中邊上的字母代表每一步經(jīng)過的結(jié)點間路徑2）樹節(jié)點上的數(shù)字表示從源點s到該結(jié)點所對應(yīng)的當前路長3）以經(jīng)歷過的邊表示路徑e.g. 以圖中頂點表示的路徑s-1-2-5, 邊表示的路徑s —a:u:f,,,算法思想,1. 解空間樹中的結(jié)點v 對應(yīng)1條從源點s到圖中某個頂點的路徑；葉節(jié)點對應(yīng)1條s到目標點t的路徑； 每個結(jié)點v需要記錄本路徑從s開始、經(jīng)過的全部邊或頂點 e.g. 樹結(jié)點，當前路長14，

30、對應(yīng)的路徑s —a:u:f,,各樹結(jié)點v的限界函數(shù) 1）上界up：可利用貪心法，求出1個上界 方法：每步選擇離當前結(jié)點最近的下一結(jié)點 書上沒有給出每條邊的長度？！ 2） dist(v)—下界 樹結(jié)點所對應(yīng)路徑的長度：從源點s至路徑中最后一個頂點的總長 e.g. 對以頂點表示的路徑s-1-2-5, 或以 邊表示的路徑s —a:u:f，對應(yīng)的樹中結(jié)點？（紅色），dist(?

31、)=143. 活結(jié)點表的組織 組織為極小堆，其優(yōu)先級/目標函數(shù)是結(jié)點所對應(yīng)的當前路徑長度dist,說明：教科書上的下界函數(shù)只考慮了當前部分路徑的現(xiàn)有長度，沒有考慮未來結(jié)點可能帶來的路徑長度，下界函數(shù)不準確e.g. 對部分路徑s→1 → 2 → 5, 書上給出的下界值/優(yōu)先級/目標函數(shù)只是取為當前路徑長度14； 但顯然對該部分解，不管從結(jié)點5向后如何走，下界值肯定比14大,,4. 搜索過程1）從源頂點s、空優(yōu)先隊

32、列開始，首先選擇s作為擴展結(jié)點2）結(jié)點s被擴展后，它的兒子結(jié)點被依次插入活結(jié)點表——堆中3）從堆中取出優(yōu)先級最高(即：dist(v)/目標函數(shù)/下界最小）的樹結(jié)點v，作為當前擴展結(jié)點 —v對應(yīng)的路徑為s-i1-i2-…-ik — 與堆中其它結(jié)點相比，該路徑的長度dist(v)最小 e.g. 見下頁，堆中有3個活結(jié)點，對應(yīng)了三條路徑s-1-2-5、s-1-5-6-9、s-2，路徑長度dist分別為14、6、3

33、 應(yīng)選擇dist最小的路徑s-2，即原圖中的城市頂點2應(yīng)作為擴展結(jié)點,,,,,,,,,,,,,,4) 生成擴展結(jié)點的子結(jié)點 在G (V,E)中，依次檢查與當前擴展結(jié)點相鄰的所有頂點。 e.g. 如果城市頂點2被選為擴展結(jié)點，則需要考察經(jīng)過邊f(xié)、g可到達的城市頂點5、65) 考察各子結(jié)點是否可作為活結(jié)點——是否有必要進一步擴展? 如果 i) 從當前選擇的擴展城市頂點i到它的鄰接城市頂點j有邊

34、可達，并且 ii) 從源s出發(fā)，途經(jīng)城市頂點i再到頂點j的所相應(yīng)的路徑的長度小于當前已經(jīng)得到的最優(yōu)路徑長度(或問題上界up), 即： dist(i) + distance(i, j) < mindist （或問題上界up），則將s到城市頂點j的路徑在解空間樹中所對應(yīng)樹結(jié)點作為活結(jié)點，插入到活結(jié)點優(yōu)先隊列中,e.g. 考察下圖 假設(shè)當前得到的最優(yōu)路徑為s-2-6-9-t, mind

35、ist=8； 樹結(jié)點6（對應(yīng)路徑 s-3-6,城市頂點6 ）被選為擴展結(jié)點，經(jīng)過邊l、m可分別到達的城市頂點8、9，對應(yīng)了樹結(jié)點11、76，在樹中分別對應(yīng)左、右2個子結(jié)點：— 左子節(jié)點表示路徑s-3-6-8，對應(yīng)了樹結(jié)點11 ，dist=11 > mindist=8, 被剪枝舍棄— 右子結(jié)點表示路徑s-3-6-9，dist=7 < mindist=8 因此，右子樹結(jié)點7（路徑s-3-6-9）可以作為活結(jié)點

36、加入表中，后續(xù)繼續(xù)擴展搜索；而左子樹結(jié)點11（路徑s-3-6-8 ）可以舍棄，在搜索樹中變?yōu)樗澜Y(jié)點,e.g. 假設(shè)當前得到的最優(yōu)路徑為s-1-5-6-9, mindist=6,,1,2,3,4,5,6,7,8,9,,,,,,,,,,,,,,,,,,,,,,×,,6) 上述擴展過程一直繼續(xù)到活結(jié)點優(yōu)先隊列為空時為止4. 剪枝策略1 結(jié)點擴展的過程中，一旦發(fā)現(xiàn)一個結(jié)點的下界不小于當前找到的最短路長mindist，則算法剪去

37、以該結(jié)點為根的子樹e.g. 見下圖：1）當前得到的最優(yōu)路徑為s-b:g:m:p，即s-2-6-9-t, mindist=8, 在樹中對應(yīng)1個葉節(jié)點. 對該葉結(jié)點左邊（先生成）的結(jié)點j，只要dist(j)>=8, 結(jié)點j就成為死結(jié)點； 只有dist(j)<8的結(jié)點才作為活結(jié)點保留下來。2）對樹中的3條路徑s-b:g:l、s-b:f、s-c:h:l，長度分別為10、12、11，均大于當前mindist=8, 因

38、此3個結(jié)點下的子樹被剪枝,e.g. 假設(shè)當前得到的最優(yōu)路徑為s-1-5-6-9, mindist=6,,1,2,3,4,5,6,7,8,9,,,,,,,,,,,,,,,,,,,,,,,,,,策略2：利用結(jié)點間的控制關(guān)系進行剪枝。 從源頂點s出發(fā)，2條不同路徑到達圖G的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應(yīng)的樹中的結(jié)點為根的子樹剪去e.g. 下圖中， 2條路徑s-b:g:l、s-c:h:

39、l，長度分別為10、11，均到達城市結(jié)點8，因此可以舍棄長度=11的路徑s-c:h:l所對應(yīng)的子樹,e.g. 假設(shè)當前得到的最優(yōu)路徑為s-1-5-6-9, mindist=6,,1,2,3,4,5,6,7,8,9,,,,,,,,,,,,,,,,,,,,算法代碼框架,while (true) { for (int j = 1; j N; N.i=j; N.length=dist[j];

40、 H.Insert(N);} try {H.DeleteMin(E);} // 取下一擴展結(jié)點 catch (OutOfBounds) {break;} // 優(yōu)先隊列空 }},頂點I和j間有邊，且此路徑長小于原先從原點到j(luò)的路徑長,旅行商TSP問題,本問題關(guān)鍵： 如何估計TSP最優(yōu)解的上下界,（a）5個頂點的無向圖,（b）代價矩陣C表示各城市間的距離,代價矩陣特點：每

41、條滿足要求的回路在代價矩陣中的每一行每一列有且只有1個元素與之對應(yīng)（n后問題）。e.g. 回路1→3 → 5 → 4 → 2 → 1，對應(yīng)于C中的 c13, c35, c54, c42, c21,,,,,,,TSP問題的上下界,1.利用貪心法計算上界 以起始城市1作為出發(fā)城市，每次從當前出發(fā)城市發(fā)出的多條邊中，選擇沒有遍歷過的最短邊連接的城市，作為下一步達到城市。

42、 即：選擇離當前出發(fā)城市最近的城市作為下一步出發(fā)城市 e.g. 從城市1出發(fā)， 途徑1→3 → 5 → 4 → 2 → 1路徑長度=1+2+3+7+3=16作為上界，即最短路徑長度≤16,2. !! TSP 下界lb下界1：矩陣中每一行的最小元素相加，其路徑長度為 1 + 3 + 1 +3 + 2 = 10, 說明：最小元素代表每一步可能走的最短距離下界2（信息量更大）： 1） 在一條路

43、徑上，每個城市有2條鄰接邊：進入該城市、離開該城市； 2） 將矩陣中每一行最小的2個元素相加除以2，并向上取整，就得到一個合理下界 解釋：對每一步經(jīng)過的城市j，從最近的上一個城市i來，再到下一個最近城市k去，即i→j→k,e.g. 對上圖所示TSP，其最短路徑下界 lb={(1+3) + (3+6) + (1+2) + (3+4) + (2+3)}/2 =14

44、 因此，以最短路徑長度dist作為TSP問題目標函數(shù)，則dist的界為 [14, 16]. 在問題求解過程中，如果1個部分解的目標函數(shù)dist下界（e.g.18）超出此界限（上界16），則該部分解對應(yīng)了死結(jié)點，可剪枝。,,部分解目標函數(shù)下界計算,對于1條正在生成的路徑/部分解，已經(jīng)確定的頂點（已經(jīng)經(jīng)過/遍歷的城市）集合為 U=(r1, r2, …, rk) , 該部分解的目標函數(shù)的下界為：,//*已經(jīng)經(jīng)過的路徑的總長

45、的2倍,//*從當前已經(jīng)走過的城市出發(fā)，走向最近的1個未遍歷城市的距離和,//* 進入/離開未遍歷城市時，各未遍歷城市帶來的最小路徑成本,E.g. 假設(shè) 正在生成的路徑/部分解為1→4, U={1,4}，未遍歷城市={2,3,5}，該部分解下界為lb ={ 2*已經(jīng)歷過的路徑總長 + 從城市1到最近未遍歷城市的距離 + 從城市4到最近未遍歷城市的距離 + 進入/離開城市2帶來的最小成本

46、 + 進入/離開城市3帶來的最小成本 + 進入/離開城市5帶來的最小成本 } /2 = { 2*5 + 1 + 3 + (3+6) + (1+2) + (2+3) } / 2= 16 (向上取整),用分支限界求解，搜索空間樹如下圖所示：1. TSP問題完全解界限[14, 16]2. 最優(yōu)解為1→3 → 5 → 4 → 2 → 1，最短路徑長度=1+2+3+7+3=163.

47、樹結(jié)點編號對應(yīng)了結(jié)點擴展順序，即搜索順序4. ×表示被丟棄的死結(jié)點，其余為活結(jié)點搜索過程：Step1. 在根結(jié)點1處，U=空, 計算本問題的可能下界 lb = { 2*已經(jīng)歷過的路徑總長 + 進入/離開城市1帶來的最小成本 + 進入/離開城市2帶來的最小成本

48、 + 進入/離開城市3帶來的最小成本 + 進入/離開城市4帶來的最小成本 + 進入/離開城市5帶來的最小成本} /2 = { 2*0 + 0 + (1+3) + (3+6) + (1+2) +

49、(3+4) + (2+3) } /2 = 14,TSP問題完全解界限[14, 16],1. 樹結(jié)點編號對應(yīng)了結(jié)點搜索/生成順序2. ×表示被丟棄的死結(jié)點,Step2. 以結(jié)點1為擴展結(jié)點，依次生成樹結(jié)點2,3,4,5；Step3. 計算這4個結(jié)點的lb： lb(2)= lb(3)=14, lb(4)=16，均小于 等于問題上界16，因此結(jié)點2、3、4

50、 加入活結(jié)點表； 對結(jié)點5，已遍歷城市U={1,5} lb(5) = { 2*已經(jīng)歷過的路徑1 → 5總長 + 從城市1到最近未遍歷城市3的距離 + 從城市5到最近未遍歷城市3的距離 + 進入/離開城市2帶來的最小成本

51、 + 進入/離開城市3帶來的最小成本 + 進入/離開城市4帶來的最小成本 } /2 = { 2*8 + 1 + 2 + (3+6) + (1+2) + (3+4) } /2 = 19 lb(5)>問題上界1

52、6，樹結(jié)點5被作為死結(jié)點舍棄,Step4.從當前活結(jié)點表ANT={2,3,4}中，以lb為依據(jù)，并兼顧結(jié)點生成順序，選取lb最小的結(jié)點2作為擴展結(jié)點，生成結(jié)點6、7、8； 計算這3個結(jié)點的lb， lb(6)= lb(7)=16, lb(8)=19; 舍棄結(jié)點8，將結(jié)點6、7加入活結(jié)點表, 變?yōu)锳NT={3,4, 6,7}Step5. 從ANT中，選擇 lb最小的結(jié)點3擴展，生成結(jié)點9、10、11,Step6. 按照

53、上述方法，依次擴展搜索樹，得到最優(yōu)解 1→3 → 5 → 4 → 2 → 1，最短路徑長度=1+2+3+7+3=16 TSP問題分支限界法算法描述： 數(shù)組x[1:n]存儲搜索路徑上的樹頂點,1. 采用貪心法，計算上界up； 根據(jù)目標函數(shù)公式，計算下界down2. 將活結(jié)點表ANT初始化為空3. for ( i=1; i =1) 5.1 i=k+1; 5.2

54、 x[i]=1; 5.3 while (x[i] <= n) 5.3.1 如果路徑上城市頂點不重復，則 5.3.1.1 計算x[i]的下界lb 5.3.1.2 if (lb < up), 將路徑上的頂點和lb值存入活結(jié) 點表ANT

55、 5.3.2 x[i] = x[i] + 1,5.4 如果i==n, 并且葉子結(jié)點的目標函數(shù)值在表ANT中最小， 則將該葉結(jié)點對應(yīng)的最優(yōu)解輸出 5.5 否則，若i==n，則從ANT中取葉子結(jié)點的目標函數(shù)值最 小結(jié)點的lb，令up=lb，刪除ANT表中目標函數(shù)值lb超出 up的結(jié)點 5.6 k=表ANT中l(wèi)b最小的路徑上

56、的頂點個數(shù),65,0-1背包問題,問題： 4個物品，重量分別為(4,7,5,3 )，容量C=10 價值(40,42,25,12) 按照單位價值最大化排序：,66,搜索樹 二分搜索樹，依次考慮物品1、2、3、4是否放入 k=0層：對應(yīng)根節(jié)點，不放入任何物品 k>1層：考慮第i個物品，左分支—放入，右分支—不放入,,,1,2,67,限界函數(shù)（最大化問題） 下界down：貪心法，

57、 第1個可裝入的、具有最大價值/重量比的物品所具 有的價值，(1,0,0,0) , down=40 上界up：背包中全部裝入第1個物品，且裝滿， up=10*10=100 問題限界[40,100]對第k層結(jié)點，代表了對物品1—i作出的選擇，假設(shè)已經(jīng)裝入的物品重量為w，獲得的價值為v該結(jié)點的限界函數(shù)ub： 已裝入背包中物品取得的價值v + 背包剩余容

58、量（C-w）*剩余物品中的最大單位重量價值,68,問題完全解界限[40, 100],,,1,1,1,2,3,,,4,5,無效死結(jié)點(w>C),,,6,7,無效死結(jié)點(w>C),9,,,8,剪枝條件: ub <40,,物品2單位價值,,物品3單位價值,物品4單位價值,,物品4單位價值,,69,說明：死結(jié)點：裝入的物品超出背包容量C=10，如結(jié)點4、82. 當結(jié)點9生成后，得到1個完全解，其價值v=65。 此時

59、，活結(jié)點表中還有結(jié)點3、7，但由于結(jié)點3、7的ub分別為60、64，均已經(jīng)小于結(jié)點9的價值v=65， 因此，結(jié)點3、7沒有必要再進一步擴展，被剪枝；活結(jié)點表為空，算法結(jié)束。,6.3多段圖最短路徑問題,問題描述： 在帶權(quán)有向連通圖G=(V,E)中，將頂點集V劃分為k個互不相交子集Vi（2≤k ≤ n, 1≤ i ≤ k），使得對E中任何一條邊(u, v)，必有u∈Vi，v ∈ Vi+m （ 1≤ i ≤ k， 1≤

60、 i + m ≤ k ）。 稱G為多段圖，s ∈ V1為起點，t ∈ Vk為終點。要求：求出從源點s到目標點t之間的最短路徑。,問題的上下界,1.利用貪心法計算上界 以起始城市1作為出發(fā)城市，每次從當前出發(fā)城市發(fā)出的多條邊中，選擇最短邊連接的城市，作為下一步達到城市。 即：選擇離當前出發(fā)城市最近的城市作為下一步出發(fā)城市 e.g. 從城市1出發(fā)， 途徑0→2→ 5 → 8→ 9路徑長

61、度=2+7+6+3=18作為上界，即多段圖的最短路徑長度≤18,2. 問題下界 每一段最小代價相加，得到下界 2 + 4 + 5 +3 = 14,部分解目標函數(shù)下界計算,多段圖將頂點劃分為k個不相交子集，路徑也相應(yīng)分為k段； 對于1條正在生成的路徑/部分解，已經(jīng)確定了i段（ 1≤ i ≤ k ），即已經(jīng)經(jīng)過/遍歷i個城市，其路徑經(jīng)過的頂點/城市集合為 U=(r1, r2, …, ri , ri+1

62、) , 該部分解的目標函數(shù)的下界為：,//*已經(jīng)經(jīng)過的i段路徑的總長,//*從當前已經(jīng)走過的城市出發(fā)，走向最近1個未遍歷城市,//* 進入/離開后續(xù)各未遍歷城市時，各未遍歷城市帶來的最小路徑成本,E.g. 假設(shè) 正在生成的路徑/部分解為0→1, U={0,1}，后續(xù)未遍歷分為3段，對應(yīng)城市分別為{4,5,6}，{7,8}，{9}，該部分解下界為lb =已經(jīng)歷過的路徑0→1總長 + 從城市1到最近未遍歷城市5的距離

63、 + 第3段最短邊 + 第4段最短邊 = 4 + 8 + 5 + 3 = 20,多段圖的搜索樹及搜索過程,,1. 問題完全解界限[14, 18]2. 搜索過程中，利用各部分解結(jié)點的下界lb，判斷該結(jié)點lb是否>上界18 3. 如果是，則該結(jié)點被剪枝舍棄 e.g. 結(jié)點2， 對應(yīng)路徑0→1 結(jié)點10， 對應(yīng)路徑0→3 → 5 → 7,問題完

64、全解界限[14, 18],1. 樹結(jié)點編號對應(yīng)了結(jié)點搜索/生成順序2. ×表示被丟棄的死結(jié)點,2+7+5+3=17,3+4+5+3=15,2+8+5+7=22,×,2+7+6+3=18,2+8+5+3=18,4+8+5+3=20,3+4+6+3=16,3+7+5+3=18,3+4+8+7=22,3+4+6+3=16,1. 采用貪心法，計算上界up； 根據(jù)目標函數(shù)公式，計算下界down2. 將活

65、結(jié)點表ANT初始化為空3. for ( i=1; i =1) 5.1 對頂點u的所有鄰接點v 5.1.1 計算v的目標函數(shù)lb(v) 5.1.2 if (lb , lb(v)值} 存入活結(jié)點表ANT 5.2 如果i==k-1, 即搜索到達葉節(jié)點，并且葉子結(jié)點的目標函 數(shù)值lb在表ANT中

66、最小 ，則輸出該葉結(jié)點對應(yīng)的最優(yōu)解,5.3 否則，若i==k-1，并且葉子結(jié)點的目標函數(shù)值lb在 表ANT中不是最小，則 5.3.1 令up=表ANT中葉子結(jié)點所具有的最小的lb值 5.3.2 刪除ANT表中目標函數(shù)值lb超出up的結(jié)點 5.4 u =表ANT中l(wèi)b最小的結(jié)點的v值（頂點編號）

67、 //* 選取lb最小的活結(jié)點v，作為擴展結(jié)點 5.5 i =表ANT中l(wèi)b最小的結(jié)點的i值； //*擴展結(jié)點對應(yīng)的段號 5.6 i++,批處理作業(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è)最優(yōu)處理順序

68、，使得從第1個投入執(zhí)行的作業(yè)在機器1上開始，到最后1個作業(yè)在機器3上結(jié)束為止，所需時間最短。最優(yōu)調(diào)度：機器1上無空余時間，機器2、3上的空閑/等待時間最短可以證明：對最優(yōu)調(diào)度，作業(yè)在機器1上的執(zhí)行順序與機器2、3上的執(zhí)行順序是一致的。,分支限界法的復雜性,與回溯法一樣，分支限界法屬于蠻力窮舉法。最壞情況下，需要遍歷指數(shù)階個結(jié)點的解空間樹，復雜性為指數(shù)階。與回溯法不同：優(yōu)先擴展上層結(jié)點，采用界限函數(shù)，利于大范圍剪枝，縮小搜索空間；