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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

39、l，長(zhǎng)度分別為10、11，均到達(dá)城市結(jié)點(diǎn)8，因此可以舍棄長(zhǎng)度=11的路徑s-c:h:l所對(duì)應(yīng)的子樹(shù),e.g. 假設(shè)當(dāng)前得到的最優(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);} // 取下一擴(kuò)展結(jié)點(diǎn) catch (OutOfBounds) {break;} // 優(yōu)先隊(duì)列空 }},頂點(diǎn)I和j間有邊，且此路徑長(zhǎng)小于原先從原點(diǎn)到j(luò)的路徑長(zhǎng),旅行商TSP問(wèn)題,本問(wèn)題關(guān)鍵： 如何估計(jì)TSP最優(yōu)解的上下界,（a）5個(gè)頂點(diǎn)的無(wú)向圖,（b）代價(jià)矩陣C表示各城市間的距離,代價(jià)矩陣特點(diǎn)：每

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

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

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

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

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

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

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

48、 + 進(jìn)入/離開(kāi)城市3帶來(lái)的最小成本 + 進(jìn)入/離開(kāi)城市4帶來(lái)的最小成本 + 進(jìn)入/離開(kāi)城市5帶來(lái)的最小成本} /2 = { 2*0 + 0 + (1+3) + (3+6) + (1+2) +

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

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

51、 + 進(jìn)入/離開(kāi)城市3帶來(lái)的最小成本 + 進(jìn)入/離開(kāi)城市4帶來(lái)的最小成本 } /2 = { 2*8 + 1 + 2 + (3+6) + (1+2) + (3+4) } /2 = 19 lb(5)>問(wèn)題上界1

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

53、上述方法，依次擴(kuò)展搜索樹(shù)，得到最優(yōu)解 1→3 → 5 → 4 → 2 → 1，最短路徑長(zhǎng)度=1+2+3+7+3=16 TSP問(wèn)題分支限界法算法描述： 數(shù)組x[1:n]存儲(chǔ)搜索路徑上的樹(shù)頂點(diǎn),1. 采用貪心法，計(jì)算上界up； 根據(jù)目標(biāo)函數(shù)公式，計(jì)算下界down2. 將活結(jié)點(diǎn)表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 如果路徑上城市頂點(diǎn)不重復(fù)，則 5.3.1.1 計(jì)算x[i]的下界lb 5.3.1.2 if (lb < up), 將路徑上的頂點(diǎn)和lb值存入活結(jié) 點(diǎn)表ANT

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

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

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

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

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

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

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

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

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

64、全解界限[14, 18],1. 樹(shù)結(jié)點(diǎn)編號(hào)對(duì)應(yīng)了結(jié)點(diǎn)搜索/生成順序2. ×表示被丟棄的死結(jié)點(diǎn),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. 采用貪心法，計(jì)算上界up； 根據(jù)目標(biāo)函數(shù)公式，計(jì)算下界down2. 將活

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

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

67、 //* 選取lb最小的活結(jié)點(diǎn)v，作為擴(kuò)展結(jié)點(diǎn) 5.5 i =表ANT中l(wèi)b最小的結(jié)點(diǎn)的i值； //*擴(kuò)展結(jié)點(diǎn)對(duì)應(yīng)的段號(hào) 5.6 i++,批處理作業(yè)調(diào)度,給定n個(gè)作業(yè)的集合J={J1,J2,…,Jn},每個(gè)作業(yè)有3項(xiàng)任務(wù)需要在3臺(tái)機(jī)器上完成，作業(yè)Ji需要機(jī)器j的處理時(shí)間為tij（1≤i ≤ n, 1≤j≤3 ）。每個(gè)作業(yè)需要依次在機(jī)器1、2、3上處理。要求：確定作業(yè)最優(yōu)處理順序

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