第9章分支限界法

1、第第9 9章章 分支限界法分支限界法n學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn): : 理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架掌握分支限界法的算法框架n隊(duì)列式隊(duì)列式(FIFO)分支限界法分支限界法n優(yōu)先隊(duì)列式優(yōu)先隊(duì)列式分支限界法分支限界法通過應(yīng)用范例學(xué)習(xí)分支限界算法設(shè)計(jì)策略通過應(yīng)用范例學(xué)習(xí)分支限界算法設(shè)計(jì)策略9.1.1 分支限界法分支限界法n分支限界法類似于回溯法，也是一種在問題的解分支限界法類似于回溯法，也是一種在問題的解空間樹空間樹T中中搜索搜索問題解的算法。問題解的算法。n分支限界法常以分支限界法常以廣度優(yōu)先廣度優(yōu)先或以或以最小耗費(fèi)最小耗費(fèi)( (LC) )優(yōu)先優(yōu)先的方式搜

2、索問題的解空間樹。的方式搜索問題的解空間樹。在遍歷過程中，對(duì)已經(jīng)擴(kuò)展出的每一個(gè)結(jié)點(diǎn)根據(jù)在遍歷過程中，對(duì)已經(jīng)擴(kuò)展出的每一個(gè)結(jié)點(diǎn)根據(jù)限界函數(shù)限界函數(shù)估算估算目標(biāo)函數(shù)目標(biāo)函數(shù)的可能取值，從中選取使的可能取值，從中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)優(yōu)先進(jìn)行優(yōu)先進(jìn)行廣度優(yōu)先搜索，廣度優(yōu)先搜索，從而不斷調(diào)整搜索方向，盡快找到問題的解。從而不斷調(diào)整搜索方向，盡快找到問題的解。n適用于求解適用于求解最優(yōu)化最優(yōu)化問題。問題。9.1 概述概述9.1.2 分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想n首先，確定一個(gè)合理的首先，確定一個(gè)合理的限界函數(shù)限界函數(shù)，并根據(jù)限界函數(shù)確，并根據(jù)限界函數(shù)確定問題的目標(biāo)

3、函數(shù)的界定問題的目標(biāo)函數(shù)的界down, up(具體問題可以只有具體問題可以只有下界下界down，或上界，或上界up)；n然后，按照廣度優(yōu)先策略遍歷問題的解空間樹：然后，按照廣度優(yōu)先策略遍歷問題的解空間樹：當(dāng)搜索到達(dá)一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，一次性擴(kuò)展它的所有孩子，當(dāng)搜索到達(dá)一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，一次性擴(kuò)展它的所有孩子，估算估算每一個(gè)每一個(gè)孩子結(jié)點(diǎn)的孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值目標(biāo)函數(shù)的可能取值(又稱為又稱為耗耗費(fèi)函數(shù)值費(fèi)函數(shù)值)；將那些滿足約束條件且將那些滿足約束條件且耗費(fèi)函數(shù)值耗費(fèi)函數(shù)值不超過不超過目標(biāo)函數(shù)的界目標(biāo)函數(shù)的界的孩子，插入的孩子，插入活動(dòng)結(jié)點(diǎn)表活動(dòng)結(jié)點(diǎn)表PT中，再?gòu)闹校購(gòu)腜T表中取耗費(fèi)函表中取

4、耗費(fèi)函數(shù)值極大數(shù)值極大(小小)的下一結(jié)點(diǎn)同樣擴(kuò)展；的下一結(jié)點(diǎn)同樣擴(kuò)展；直到找到所需的解或直到找到所需的解或PT表為空為止。表為空為止。怎樣確定怎樣確定“限界函數(shù)限界函數(shù)”？又如何求得目標(biāo)函數(shù)的界呢？又如何求得目標(biāo)函數(shù)的界呢？n對(duì)于對(duì)于PT中的中的葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)：其其耗費(fèi)函數(shù)值是極值耗費(fèi)函數(shù)值是極值(極大或極小極大或極小)，則該葉子結(jié)點(diǎn)，則該葉子結(jié)點(diǎn)對(duì)應(yīng)的解就是問題的最優(yōu)解；對(duì)應(yīng)的解就是問題的最優(yōu)解；否則否則，將問題，將問題目標(biāo)函數(shù)的界目標(biāo)函數(shù)的界(down, up)調(diào)整為調(diào)整為該該葉子結(jié)點(diǎn)的葉子結(jié)點(diǎn)的耗費(fèi)函數(shù)值耗費(fèi)函數(shù)值，然后丟棄，然后丟棄PT表中超出目表中超出目標(biāo)函數(shù)界的結(jié)點(diǎn)，再次選取結(jié)點(diǎn)

5、繼續(xù)擴(kuò)展。標(biāo)函數(shù)界的結(jié)點(diǎn)，再次選取結(jié)點(diǎn)繼續(xù)擴(kuò)展。n例例9-1：0/1背包問題。背包問題。實(shí)例：假設(shè)有實(shí)例：假設(shè)有4個(gè)物品，其重量分別為個(gè)物品，其重量分別為(4, 7, 5, 3)，價(jià)值分別，價(jià)值分別為為(40, 42, 25, 12)，背包容量，背包容量W=10。將給定物品。將給定物品按單位重按單位重量?jī)r(jià)值從大到小排序量?jī)r(jià)值從大到小排序，結(jié)果如下：，結(jié)果如下：物品物品重量重量(w)價(jià)值價(jià)值(v)價(jià)值價(jià)值/重量重量(v/w)144010274263525543124n分析：?jiǎn)栴}的解可表示為分析：?jiǎn)栴}的解可表示為n元向量元向量x1, x2, . xn , xi 0,1，則可用子集樹表示解空間則可用

6、子集樹表示解空間, 在樹中做廣在樹中做廣度優(yōu)先搜索。度優(yōu)先搜索。約束條件約束條件: 目標(biāo)函數(shù)目標(biāo)函數(shù): n下界下界Vdb =40 (1, 0, 0, 0)貪心思想貪心思想；n上界上界Vub =0+(W-0)(v1/w1) =0+(10-0)10=100；上限界函數(shù)：上限界函數(shù)： (式式9.1)()(11iiwvwWvubWxwniii1niiixvV1max目標(biāo)函數(shù)的界：目標(biāo)函數(shù)的界：40, 10011111100000001124891011121314157653前前i個(gè)物品獲得的價(jià)值個(gè)物品獲得的價(jià)值剩余容量全部裝入物品剩余容量全部裝入物品i+1，最多能夠獲得的價(jià)值最多能夠獲得的價(jià)值n分支

7、限界法求解分支限界法求解0/1背包問題：背包問題：w=0, v=0ub=100w=4, v=40ub=76w=0, v=0ub=60w=11w=4, v=40ub=70w=9, v=65ub=69w=4, v=40ub=64w=12w=9, v=65ub=65234567891PT=2, 3無效解無效解PT=5, 3PT=6, 7, 3無效解無效解x1=1x1=0 x2=1x2=0 x3=1x3=0 x4=1x4=0PT=9, 7, 3V=65X=(1, 0, 1, 0)目標(biāo)函數(shù)范圍：目標(biāo)函數(shù)范圍：40, 100wi=(4, 7, 5, 3)vi= (40, 42, 25, 12)vi/wi=

8、(10, 6, 5, 4)()(11iiwvwWvubn分支限界法的一般過程：分支限界法的一般過程：1根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界down, up；2將待處理結(jié)點(diǎn)表將待處理結(jié)點(diǎn)表PT初始化為空；初始化為空；3對(duì)根結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)對(duì)根結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作執(zhí)行下列操作 3.1 估算結(jié)點(diǎn)估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值value; 3.2 若若(value=down)，則將結(jié)點(diǎn)，則將結(jié)點(diǎn)x加入表加入表PT中；中；4循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大中最大 4.1 i=表表PT中值最大的結(jié)點(diǎn)；中值最大的結(jié)點(diǎn)；

9、4.2 對(duì)結(jié)點(diǎn)對(duì)結(jié)點(diǎn)i的每個(gè)孩子結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作執(zhí)行下列操作 4.2.1 估算結(jié)點(diǎn)估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值value; 4.2.2 若若(value=down)，則將結(jié)點(diǎn)，則將結(jié)點(diǎn)x加入表加入表PT中；中； 4.2.3 若若(結(jié)點(diǎn)結(jié)點(diǎn)x是葉子結(jié)點(diǎn)且結(jié)點(diǎn)是葉子結(jié)點(diǎn)且結(jié)點(diǎn)x的的value值在表值在表PT中最大中最大)， 則將結(jié)點(diǎn)則將結(jié)點(diǎn)x對(duì)應(yīng)的解輸出，算法結(jié)束；對(duì)應(yīng)的解輸出，算法結(jié)束； 4.2.4 若若(結(jié)點(diǎn)結(jié)點(diǎn)x是葉子結(jié)點(diǎn)但結(jié)點(diǎn)是葉子結(jié)點(diǎn)但結(jié)點(diǎn)x的的value值在表值在表PT中不是最大中不是最大)，則令，則令down=value，并且將表，并且將表PT中所有小于中所有小

10、于value的結(jié)點(diǎn)刪除；的結(jié)點(diǎn)刪除；n常見的兩種分支限界法：常見的兩種分支限界法： 從表從表PT中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不同的分支限界法：同的分支限界法：隊(duì)列式隊(duì)列式(FIFO)分支限界法：分支限界法：從左往右從左往右依次插入結(jié)依次插入結(jié)點(diǎn)到隊(duì)尾，按照隊(duì)列先進(jìn)先出（點(diǎn)到隊(duì)尾，按照隊(duì)列先進(jìn)先出（FIFO）原則選?。┰瓌t選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。優(yōu)先隊(duì)列式優(yōu)先隊(duì)列式分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。n最大最大優(yōu)先隊(duì)列：

11、使用最大堆，體現(xiàn)最大效益優(yōu)先。優(yōu)先隊(duì)列：使用最大堆，體現(xiàn)最大效益優(yōu)先。n最小最小優(yōu)先隊(duì)列：使用最小堆，體現(xiàn)最小費(fèi)用優(yōu)先。優(yōu)先隊(duì)列：使用最小堆，體現(xiàn)最小費(fèi)用優(yōu)先。例如，上例例如，上例0/1背包問題，采用最大優(yōu)先隊(duì)列式分支限背包問題，采用最大優(yōu)先隊(duì)列式分支限界法。界法。n應(yīng)用分支限界法的其他關(guān)鍵問題：應(yīng)用分支限界法的其他關(guān)鍵問題：如何確定最優(yōu)解中的各個(gè)分量？如何確定最優(yōu)解中的各個(gè)分量？n對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑保存根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑；例如，例如，0/1背包問題。將背包問題。將部分解部分解(x1, , xi)和該部分解和該部分解的的目標(biāo)函數(shù)的上界值目標(biāo)函數(shù)的上界值都存儲(chǔ)

12、在待處理結(jié)點(diǎn)表都存儲(chǔ)在待處理結(jié)點(diǎn)表PT中，中，在搜索過程中表在搜索過程中表PT的狀態(tài)如下：的狀態(tài)如下：(0)60 (1,0,0)64 (1,0,1,0)65(a) 擴(kuò)展根結(jié)點(diǎn)后表擴(kuò)展根結(jié)點(diǎn)后表PT狀態(tài)狀態(tài) (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)2后表后表PT狀態(tài)狀態(tài)(c) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)5后表后表PT狀態(tài)狀態(tài) (d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)6后表后表PT狀態(tài)，最優(yōu)解為狀態(tài)，最優(yōu)解為(1,0,1,0)65(0)60 (1,0,1)69 (1,0,0)64(1)76 (0)60(0)60 (1,0)70 結(jié)點(diǎn)結(jié)點(diǎn)2結(jié)點(diǎn)結(jié)點(diǎn)3結(jié)點(diǎn)結(jié)點(diǎn)3結(jié)點(diǎn)結(jié)點(diǎn)5結(jié)點(diǎn)結(jié)點(diǎn)3結(jié)點(diǎn)結(jié)點(diǎn)6結(jié)點(diǎn)結(jié)點(diǎn)7結(jié)點(diǎn)結(jié)點(diǎn)3結(jié)點(diǎn)結(jié)點(diǎn)7結(jié)點(diǎn)結(jié)點(diǎn)9n在搜索的過

13、程中在搜索的過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，在求得最，在求得最優(yōu)解時(shí)，從葉子結(jié)點(diǎn)不斷回溯到根結(jié)點(diǎn)，以確定最優(yōu)解時(shí)，從葉子結(jié)點(diǎn)不斷回溯到根結(jié)點(diǎn)，以確定最優(yōu)解中的各個(gè)分量。優(yōu)解中的各個(gè)分量。例如，例如， 0/1背包問題。設(shè)一個(gè)表背包問題。設(shè)一個(gè)表ST，在表，在表PT中取出最中取出最大值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最大值結(jié)點(diǎn)存儲(chǔ)到表大值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最大值結(jié)點(diǎn)存儲(chǔ)到表ST中，中，表表PT和表和表ST的數(shù)據(jù)結(jié)構(gòu)為的數(shù)據(jù)結(jié)構(gòu)為(物品物品i-1的選擇結(jié)果，的選擇結(jié)果，ub)，在搜索過程中表，在搜索過程中表PT和表和表ST的狀態(tài)如下：的狀態(tài)如下：(a) 擴(kuò)展根結(jié)點(diǎn)后擴(kuò)展根結(jié)點(diǎn)后 (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)

14、展結(jié)點(diǎn)2后后(c) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)5后后 (d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)6后，最優(yōu)解為后，最優(yōu)解為(1,0,1,0)65(0,76) (0,60)PTST(0,60) (1,70)PTST(0,76)(0,60) (0,69) (0,64)PTST(0,76) (1,70)(0,60) (0,64) (1,65)PTST(0,76) (1,70) (0,69)說明：說明：ST中記錄的就是得到最優(yōu)解的搜索路徑上的各個(gè)結(jié)點(diǎn)！中記錄的就是得到最優(yōu)解的搜索路徑上的各個(gè)結(jié)點(diǎn)！n分支限界法與回溯法的分支限界法與回溯法的區(qū)別區(qū)別：求解目標(biāo)不同求解目標(biāo)不同：n回溯法回溯法找出滿足約束條件的所有解找出滿足約束條件的

15、所有解n分支限界法分支限界法找出滿足條件的一個(gè)解，或某種意找出滿足條件的一個(gè)解，或某種意義下的最優(yōu)解義下的最優(yōu)解搜索方式不同搜索方式不同：n回溯法回溯法深度優(yōu)先深度優(yōu)先n分支限界法分支限界法廣度優(yōu)先或最小耗費(fèi)優(yōu)先廣度優(yōu)先或最小耗費(fèi)優(yōu)先此外，在分支限界法中，每一個(gè)活結(jié)點(diǎn)此外，在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。9.2.1 TSP問題問題例例9-2：TSP問題。問題。n問題描述：略。問題描述：略。 各個(gè)城市間的距離用代價(jià)矩陣來表示各個(gè)城市間的距離用代價(jià)矩陣來表示, 如果如果(i,j) E，則則cij=。n分析：設(shè)城市按自然數(shù)分析：設(shè)城市按自然數(shù)1, 2,

16、 ., n編號(hào)編號(hào)解向量：解向量：(x1, x2, ., xn)約束條件：約束條件：n顯式約束：顯式約束：xi=1, 2, ., n (i=1, 2, ., n)n隱式約束：隱式約束：(xixj) (cij)9.2 廣度優(yōu)先分支限界法應(yīng)用舉例廣度優(yōu)先分支限界法應(yīng)用舉例目標(biāo)函數(shù)：目標(biāo)函數(shù)： (kV)n下界：下界：ddb= (1+3)+(3+6)+(1+2)+ (3+4)+(2+3)/2=14n上界：上界：dub=16(135421)下限界函數(shù)：設(shè)已確定的頂點(diǎn)集合下限界函數(shù)：設(shè)已確定的頂點(diǎn)集合U=(r1, r2, ., rk) (式式9.2)2/ )2(111UrjUrikiiijirrrrcdb

17、行最小的兩個(gè)元素素行不在路徑上的最小元目標(biāo)函數(shù)的界：目標(biāo)函數(shù)的界：14, 16),(min) ,(kVkdcVidik271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一個(gè)無向圖一個(gè)無向圖 (b) 無向圖的代價(jià)矩陣無向圖的代價(jià)矩陣從集合從集合U中出來的邊中出來的邊一條進(jìn)邊，一條出邊一條進(jìn)邊，一條出邊n優(yōu)先隊(duì)列式分支限界法求解優(yōu)先隊(duì)列式分支限界法求解TSP問題問題:目標(biāo)函數(shù)范圍：目標(biāo)函數(shù)范圍：14, 16412db=142356781startdb=1413db=1414db=1615db=1923db=1624db=16

18、25db=1932db=1634db=1535db=149101152db=1954db=14121342db=161442db=1845db=15151652db=2017db=19PT=2, 3, 4db=19PT=6, 7 , 9, 10, 11, 4db=18db=19PT=6, 7, 9, 16, 14, 4db=20PT=6, 7, 9, 14, 4PT=6, 7, 9, 10, 13, 4PT=6, 7, 3, 4PT=6, 7, 9, 10, 14, 4d=16135421C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 n對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存

19、根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑：對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑：(g) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)16后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為135421(1, 2)14 (1, 3)14 (1, 4)16(a) 擴(kuò)展根結(jié)點(diǎn)后的狀態(tài)擴(kuò)展根結(jié)點(diǎn)后的狀態(tài) (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)2后的狀態(tài)后的狀態(tài)(c) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)3后的狀態(tài)后的狀態(tài)(d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)11后的狀態(tài)后的狀態(tài)(e) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)13后的狀態(tài)后的狀態(tài)(1, 3)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)

20、15 (1, 3, 5)14(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4, 2)16(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16

21、(1, 3, 4, 5)15(f) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)10后的狀態(tài)后的狀態(tài)nTSP問題算法的偽代碼描述：?jiǎn)栴}算法的偽代碼描述：1根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up；2將待處理結(jié)點(diǎn)表將待處理結(jié)點(diǎn)表PT初始化為空；初始化為空；3for (i=1; i=1) 5.1 i=k+1; 5.2 xi=1; 5.3 while (xi=n) 5.3.1 如果路徑上頂點(diǎn)不重復(fù)，則如果路徑上頂點(diǎn)不重復(fù)，則 5.3.1.1 根據(jù)式根據(jù)式7.2計(jì)算目標(biāo)函數(shù)值計(jì)算目標(biāo)函數(shù)值db； 5.3.1.2 if (db kijpiEvrijjjjvrc

22、rrcdbpi21,11min1段的最短邊段的最短邊第第與頂點(diǎn)與頂點(diǎn)ri+1相連的邊中相連的邊中, 代價(jià)最小的邊代價(jià)最小的邊( (剩余頂點(diǎn)能夠達(dá)到剩余頂點(diǎn)能夠達(dá)到的最小代價(jià)的最小代價(jià)) )n優(yōu)先隊(duì)列式分支限界法求解：優(yōu)先隊(duì)列式分支限界法求解：64sAdb=20231startdb=14sBdb=16sCdb=157BDdb=188BEdb=189BFdb=185CEdb=16CFdb=181110EGdb=22EHdb=16目標(biāo)函數(shù)范圍：目標(biāo)函數(shù)范圍：14, 18ABsCDEFGHt492386884756866537PT=3, 4PT=3, 5, 6PT=7, 8, 9, 5, 6PT=7,

23、 8, 9, 11, 6c=16sCEHt(4+8+(5+3)n搜索算法描述：搜索算法描述：while (true) for (int j = 1; j = n; j+) if (cE.ijinf)&(E.length+cE.ijdistj) / 頂點(diǎn)頂點(diǎn)i到頂點(diǎn)到頂點(diǎn)j可達(dá)，且滿足控制約束可達(dá)，且滿足控制約束 distj=E.length+cE.ij; prevj=E.i; / 加入活結(jié)點(diǎn)優(yōu)先隊(duì)列加入活結(jié)點(diǎn)優(yōu)先隊(duì)列 MinHeapNode N; N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一擴(kuò)展結(jié)點(diǎn)取下一擴(kuò)展

24、結(jié)點(diǎn) catch (OutOfBounds) break; / 優(yōu)先隊(duì)列空優(yōu)先隊(duì)列空 頂點(diǎn)頂點(diǎn)i和和j間有邊，且此路間有邊，且此路徑長(zhǎng)小于原先從原點(diǎn)到徑長(zhǎng)小于原先從原點(diǎn)到j(luò)的路徑長(zhǎng)的路徑長(zhǎng) 9.2.3 裝載問題裝載問題n問題描述：略。問題描述：略。n分析：分析：解空間：解空間：X=(x1,x2,xn)，xiSi=0, 1，i=1,2,n約束函數(shù)：約束函數(shù)：目標(biāo)函數(shù)：目標(biāo)函數(shù)：n下界：下界：n上界：上界：上限界函數(shù)：上限界函數(shù)：11cxwniiiniiixw1max111)(cwEwcEwubi左孩子：左孩子：Ew+wi+1 bestwnijjw1改進(jìn)改進(jìn)n搜索算法設(shè)計(jì)：搜索算法設(shè)計(jì)：隊(duì)列式隊(duì)列

25、式分支限界：分支限界：while (true) / 檢查左兒子結(jié)點(diǎn)檢查左兒子結(jié)點(diǎn) Type wt = Ew + wi; / 左兒子結(jié)點(diǎn)的重量左兒子結(jié)點(diǎn)的重量 if (wt bestw) bestw = wt; / 加入活結(jié)點(diǎn)隊(duì)列加入活結(jié)點(diǎn)隊(duì)列 if (i bestw & i n) Q.Add(Ew); / 可能含最優(yōu)解可能含最優(yōu)解 Q.Delete(Ew); / 取下一擴(kuò)展結(jié)點(diǎn)取下一擴(kuò)展結(jié)點(diǎn)if (Ew = -1) / 同層結(jié)點(diǎn)尾部同層結(jié)點(diǎn)尾部 if (Q.IsEmpty() return bestw; Q.Add(-1); / 同層結(jié)點(diǎn)尾部標(biāo)志同層結(jié)點(diǎn)尾部標(biāo)志 Q.Delete(Ew

26、); / 取下一擴(kuò)展結(jié)點(diǎn)取下一擴(kuò)展結(jié)點(diǎn) i+; r-=wi; / 進(jìn)入下一層進(jìn)入下一層 提前更新提前更新bestw 右兒子剪枝右兒子剪枝 優(yōu)先隊(duì)列式優(yōu)先隊(duì)列式分支限界：分支限界： 采用最大優(yōu)先隊(duì)列存儲(chǔ)活結(jié)點(diǎn)表?；罱Y(jié)點(diǎn)采用最大優(yōu)先隊(duì)列存儲(chǔ)活結(jié)點(diǎn)表。活結(jié)點(diǎn)x在優(yōu)先隊(duì)在優(yōu)先隊(duì)列中的列中的優(yōu)先級(jí)定義為優(yōu)先級(jí)定義為：從根結(jié)點(diǎn)到結(jié)點(diǎn)：從根結(jié)點(diǎn)到結(jié)點(diǎn)x的路徑所相應(yīng)的路徑所相應(yīng)的載重量的載重量Ew + 剩余集裝箱的重量剩余集裝箱的重量r。 子集樹中葉結(jié)點(diǎn)所相應(yīng)的載重量與其優(yōu)先級(jí)相同，子集樹中葉結(jié)點(diǎn)所相應(yīng)的載重量與其優(yōu)先級(jí)相同，一旦有一個(gè)葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，則可以斷言該一旦有一個(gè)葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，則可

27、以斷言該葉結(jié)點(diǎn)所相應(yīng)的解即為最優(yōu)解。此時(shí)可終止算法。葉結(jié)點(diǎn)所相應(yīng)的解即為最優(yōu)解。此時(shí)可終止算法。n 實(shí)現(xiàn)方法實(shí)現(xiàn)方法：(PT表結(jié)點(diǎn)的結(jié)構(gòu)表結(jié)點(diǎn)的結(jié)構(gòu))在活結(jié)點(diǎn)中保存從解空間樹的根結(jié)點(diǎn)到該活結(jié)點(diǎn)的在活結(jié)點(diǎn)中保存從解空間樹的根結(jié)點(diǎn)到該活結(jié)點(diǎn)的路徑；路徑；搜索進(jìn)程中保存當(dāng)前已構(gòu)造出的部分解空間樹；搜索進(jìn)程中保存當(dāng)前已構(gòu)造出的部分解空間樹；n算算法描述（采用第二種方式實(shí)現(xiàn)法描述（采用第二種方式實(shí)現(xiàn)PT表）：表）：template class HeapNode;class bbnode friend void AddLiveNode(MaxHeapHeapNode &, bbbnode *, i

28、nt, bool, int); friend int MaxLoading(int *, int, int, int *); friend class AdjacencyGraph; private: bbnode * parent; /指向父結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)的指針 bool LChild; /左孩子結(jié)點(diǎn)標(biāo)志左孩子結(jié)點(diǎn)標(biāo)志;templateclass HeapNode friend void AddLiveNode(MaxHeapHeapNode &, bbnode *, Type, bool, int); friend Type MaxLoading(Type *, Type,

29、int, int *); public: operator Type() const return uweight; private: bbnode *ptr; /指向活結(jié)點(diǎn)在子集樹中相應(yīng)結(jié)點(diǎn)的指針指向活結(jié)點(diǎn)在子集樹中相應(yīng)結(jié)點(diǎn)的指針 Type uweight; /活結(jié)點(diǎn)優(yōu)先級(jí)活結(jié)點(diǎn)優(yōu)先級(jí)(上界上界) int level; /活結(jié)點(diǎn)在子集樹中所處的層序號(hào)活結(jié)點(diǎn)在子集樹中所處的層序號(hào);templatevoid AddLiveNode(MaxHeapHeapNode &H, bbnode *E, Type wt, bool ch, int lev)/將活結(jié)點(diǎn)加入到表示活結(jié)點(diǎn)優(yōu)先隊(duì)列的最大堆將

30、活結(jié)點(diǎn)加入到表示活結(jié)點(diǎn)優(yōu)先隊(duì)列的最大堆H中中 bbnode *b = new bbnode; b-parent = E; b-Lchild = ch; HeapNode N; N.uweight = wt; N.level = lev; N.ptr = b; H.Inset(N);templateType MaxLoading(Type w, Type c, int n, int bestx)/優(yōu)先隊(duì)列式優(yōu)先隊(duì)列式分支限界法分支限界法, 返回最優(yōu)裝載重量，返回最優(yōu)裝載重量，bestx返回最優(yōu)解返回最優(yōu)解 /定義最大堆的容量為定義最大堆的容量為1000 MaxHeapHeapNode H(100

31、0); /定義剩余重量數(shù)組定義剩余重量數(shù)組r Type *r = new Typen+1; rn = 0; for(int j=n-1; j0; j-) rj = rj+1 + wj+1; /初始化初始化 int i = 1; /當(dāng)前擴(kuò)展結(jié)點(diǎn)所處的層當(dāng)前擴(kuò)展結(jié)點(diǎn)所處的層 bbnode * E = 0; /當(dāng)前擴(kuò)展結(jié)點(diǎn)當(dāng)前擴(kuò)展結(jié)點(diǎn) Type Ew = 0; /擴(kuò)展結(jié)點(diǎn)所相應(yīng)的載重量擴(kuò)展結(jié)點(diǎn)所相應(yīng)的載重量 /搜索子集空間樹搜索子集空間樹 while (i != n+1) /非葉子結(jié)點(diǎn)非葉子結(jié)點(diǎn) /檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的孩子結(jié)點(diǎn)檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的孩子結(jié)點(diǎn) if(Ew + wi = c) /左孩子結(jié)點(diǎn)為可

32、行結(jié)點(diǎn)左孩子結(jié)點(diǎn)為可行結(jié)點(diǎn) AddLiveNode(H, E, Ew+wi+ri, true, i+1); /右孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn) AddLiveNode(H, E, Ew+ri, false, i+1); /取下一擴(kuò)展結(jié)點(diǎn)取下一擴(kuò)展結(jié)點(diǎn) HeapNode N; H.DeleteMax(N); /非空非空 i = N.level; E = N.prt; Ew = N.uweight ri-1; /構(gòu)造當(dāng)前最優(yōu)解構(gòu)造當(dāng)前最優(yōu)解 for (int j=n; j0; j-) bestxj = E-Lchild; E = E-parent; return Ew;9.2.4 批處理作業(yè)調(diào)度問題批處理作業(yè)

33、調(diào)度問題例例9-4：批處理作業(yè)調(diào)度問題。：批處理作業(yè)調(diào)度問題。n問題描述：給定問題描述：給定n個(gè)作業(yè)的集合個(gè)作業(yè)的集合J=J1, J2, , Jn，每個(gè)作業(yè)都有每個(gè)作業(yè)都有3項(xiàng)任務(wù)分別在項(xiàng)任務(wù)分別在3臺(tái)機(jī)器上完成，作臺(tái)機(jī)器上完成，作業(yè)業(yè)Ji需要機(jī)器需要機(jī)器j的處理時(shí)間為的處理時(shí)間為tij(1in, 1j3)，每個(gè)，每個(gè)作業(yè)必須先由機(jī)器作業(yè)必須先由機(jī)器1處理，再由機(jī)器處理，再由機(jī)器2處理，最后處理，最后由機(jī)器由機(jī)器3處理。處理。批處理作業(yè)調(diào)度問題要求確定這批處理作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)處個(gè)作業(yè)的最優(yōu)處理順序，使得從第理順序，使得從第1個(gè)作業(yè)在機(jī)器個(gè)作業(yè)在機(jī)器1上處理開始，上處理開始，

34、到最后一個(gè)作業(yè)在機(jī)器到最后一個(gè)作業(yè)在機(jī)器3上處理結(jié)束所需的時(shí)間最上處理結(jié)束所需的時(shí)間最少。少。實(shí)例：設(shè)實(shí)例：設(shè)J=J1, J2, J3, J4是是4個(gè)待處理的作業(yè)，需要個(gè)待處理的作業(yè)，需要的處理時(shí)間如下所示。的處理時(shí)間如下所示。若處理順序?yàn)槿籼幚眄樞驗(yàn)?J2, J3, J1, J4)，則從作業(yè)，則從作業(yè)2在機(jī)器在機(jī)器1處理處理開始到作業(yè)開始到作業(yè)4在機(jī)器在機(jī)器3處理完成的調(diào)度方案如下：處理完成的調(diào)度方案如下：T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4機(jī)器1 機(jī)器2 機(jī)器3J2:10 J3:9 J1:5 J4:7機(jī)器機(jī)器1機(jī)器機(jī)器2機(jī)器機(jī)器3( 表示空閑，最后完成處理時(shí)

35、間為表示空閑，最后完成處理時(shí)間為54)空閑空閑:10 J2:5 空閑空閑:4 J3:9 J1:7 J4:8空閑空閑:15 J2:2 空閑空閑:11 J3:5 空閑空閑:2 J1:9 J4:10等待時(shí)間等待時(shí)間+處理時(shí)間處理時(shí)間n分析：分析：解向量：解向量：X=(x1, x2, ., xn)排列樹排列樹約束條件：約束條件：n顯式：顯式：xi=J1, J2, ., Jn目標(biāo)函數(shù)目標(biāo)函數(shù):sum3=下限界函數(shù)：下限界函數(shù)：3 2ntnsum3 1 3ntnsum機(jī)器機(jī)器3有空閑有空閑機(jī)器機(jī)器3有積壓有積壓，極小化，極小化minsum2k,1sum1kmax, 132MjkjjMiittdb其中其中，

36、 sum2n=maxsum1n, sum2n-1 + tn2 ； sum1n=sum1n-1+ tn1設(shè)設(shè)M是已安排好的作業(yè)集合，是已安排好的作業(yè)集合，M 1, 2, ., n, |M|=k?，F(xiàn)在要處理作業(yè)現(xiàn)在要處理作業(yè)k+1，有：，有：sum1k+1=sum1k+ tk+1,1sum2k+1=maxsum1k+1, sum2k + tk+1,2maxsum2n, sum3n-1+tn3 n目標(biāo)函數(shù)的下界目標(biāo)函數(shù)的下界:sum3db= 說明說明：最理想的情況下，機(jī)器：最理想的情況下，機(jī)器1和機(jī)器和機(jī)器2均無空閑，均無空閑，最后處理的作業(yè)恰好是在機(jī)器最后處理的作業(yè)恰好是在機(jī)器3上處理時(shí)間最短的作

37、上處理時(shí)間最短的作業(yè)。業(yè)。如上實(shí)例，如上實(shí)例，sum3db= =36遍歷并估算解空間樹上各結(jié)點(diǎn)的目標(biāo)函數(shù)的下界遍歷并估算解空間樹上各結(jié)點(diǎn)的目標(biāo)函數(shù)的下界值：值：根結(jié)點(diǎn)：根結(jié)點(diǎn)：sum1=0, sum2=0, M= k=0ikknjjitttmin31212341211tttjjT 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4機(jī)器1 機(jī)器2 機(jī)器3n優(yōu)先隊(duì)列式分支限界法求解過程：優(yōu)先隊(duì)列式分支限界法求解過程：J4, sum1=0+7db=38sum2=152 M= k=1J1, sum1=0+5db=36sum2=5+7=121 M= k=0startsum1=0, sum2

38、=03 M= k=1J2, sum1=0+10db=44sum2=124 M= k=1J3, sum1=0+9db=40sum2=185 M= k=16 M=1 k=2J1J2, sum1=15db=42sum2=207 M=1 k=2J1J3, sum1=14db=38sum2=228 M=1 k=2J1J4, sum1=12db=36sum2=209 M=1, 4 k=3J1J4J2, sum1=22db=41sum2=2710 M=1, 4 k=3J1J4J3, sum1=21db=37sum2=3011 M=1, 4, 3 k=4J1J4J3J2, sum1=31db=36sum24=

39、36PT=2, 3, 4, 5PT=6, 7, 8, 3, 4, 5PT=6, 7, 9, 10, 3, 4, 5PT=6, 7, 9, 11, 3, 4, 5X=(J1, J4, J3, J2)sum3=sum24+t23=38min1-sum2k,sum1kmax,32MjkjjMiittdbsum1k=sum1k-1+ tk,1sum2k=maxsum1k, sum2k-1 + tk,2T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4機(jī)器機(jī)器1 機(jī)器機(jī)器2 機(jī)器機(jī)器3下界下界sum3db=36n從上例可知：優(yōu)先隊(duì)列式分支限界法中，從上例可知：優(yōu)先隊(duì)列式分支限界法中，擴(kuò)

40、展結(jié)點(diǎn)表擴(kuò)展結(jié)點(diǎn)表PT取得極值的葉子結(jié)點(diǎn)就對(duì)應(yīng)的是問取得極值的葉子結(jié)點(diǎn)就對(duì)應(yīng)的是問題的最優(yōu)解；題的最優(yōu)解；擴(kuò)展結(jié)點(diǎn)的過程，一開始實(shí)際類似擴(kuò)展結(jié)點(diǎn)的過程，一開始實(shí)際類似“深度優(yōu)先深度優(yōu)先”。n思考：思考：將例將例9-2和例和例9-4改成改成FIFO式分支限界法，搜索過式分支限界法，搜索過程有何不同？程有何不同？在算法的實(shí)現(xiàn)上，在算法的實(shí)現(xiàn)上，F(xiàn)IFO式分支限界法和優(yōu)先隊(duì)列式分支限界法和優(yōu)先隊(duì)列式分支限界法的式分支限界法的PT表數(shù)據(jù)結(jié)構(gòu)一樣嗎？表數(shù)據(jù)結(jié)構(gòu)一樣嗎？課后作業(yè)課后作業(yè)n采用分支限界法求解下列作業(yè)調(diào)度問題，采用分支限界法求解下列作業(yè)調(diào)度問題，4個(gè)作業(yè)個(gè)作業(yè)J1, J2, J3, J4在機(jī)器

41、在機(jī)器M1, M2上處理的時(shí)間矩陣如圖上處理的時(shí)間矩陣如圖所示。求最佳的處理順序，使得所示。求最佳的處理順序，使得4個(gè)作業(yè)從開始到個(gè)作業(yè)從開始到結(jié)束處理的時(shí)間最短。結(jié)束處理的時(shí)間最短。(要求：畫出解空間的展開要求：畫出解空間的展開)9710541059CM1M2J1J2J3J49.3 最小消耗最小消耗(LC)搜索法搜索法9.3.1 LC檢索檢索n在在FIFO分枝限界法中，對(duì)下一個(gè)分枝限界法中，對(duì)下一個(gè)E-結(jié)點(diǎn)的選擇規(guī)結(jié)點(diǎn)的選擇規(guī)則相當(dāng)死板，在某種意義上是盲目的。則相當(dāng)死板，在某種意義上是盲目的。n對(duì)活結(jié)點(diǎn)使用一個(gè)對(duì)活結(jié)點(diǎn)使用一個(gè)“有智力有智力”的排序函數(shù)的排序函數(shù) c(.) 來來選取下一個(gè)選取

42、下一個(gè)E-結(jié)點(diǎn)往往可以加快到達(dá)一答案結(jié)點(diǎn)結(jié)點(diǎn)往往可以加快到達(dá)一答案結(jié)點(diǎn)的速度。的速度。n對(duì)任意結(jié)點(diǎn)對(duì)任意結(jié)點(diǎn)x，可用兩種標(biāo)準(zhǔn)來量度：，可用兩種標(biāo)準(zhǔn)來量度：在生成一個(gè)答案結(jié)點(diǎn)之前，子樹在生成一個(gè)答案結(jié)點(diǎn)之前，子樹x需要生成的需要生成的結(jié)點(diǎn)結(jié)點(diǎn)個(gè)數(shù)個(gè)數(shù)；在子樹在子樹x中離中離x最近的那個(gè)答案結(jié)點(diǎn)到最近的那個(gè)答案結(jié)點(diǎn)到x的的路徑長(zhǎng)度路徑長(zhǎng)度。n使用第一種度量：使用第一種度量：圖中樹的根結(jié)點(diǎn)付出的代價(jià)是圖中樹的根結(jié)點(diǎn)付出的代價(jià)是4。結(jié)點(diǎn)。結(jié)點(diǎn)(18和和34)，(29和和35)以以及及(30和和38)的代價(jià)分別是的代價(jià)分別是3,2和和1。所有在所有在2,3和和4級(jí)上剩余結(jié)點(diǎn)的代價(jià)應(yīng)分別大于級(jí)上剩余結(jié)點(diǎn)的

43、代價(jià)應(yīng)分別大于3,2和和1。以這。以這些代價(jià)作為選擇下一個(gè)些代價(jià)作為選擇下一個(gè)E-結(jié)點(diǎn)的依據(jù)，則結(jié)點(diǎn)的依據(jù)，則E-結(jié)點(diǎn)依次為結(jié)點(diǎn)依次為1,18,29和和30。另外，不得已生成的結(jié)點(diǎn)為。另外，不得已生成的結(jié)點(diǎn)為2,34,50,19,24,32。n使用第二種度量，則使用第二種度量，則E-結(jié)點(diǎn)只是由根到最近的那個(gè)答案結(jié)結(jié)點(diǎn)只是由根到最近的那個(gè)答案結(jié)點(diǎn)路徑上的那些結(jié)點(diǎn)。點(diǎn)路徑上的那些結(jié)點(diǎn)。圖圖9.1 4-皇后問題皇后問題總是生成最小數(shù)目的結(jié)點(diǎn)總是生成最小數(shù)目的結(jié)點(diǎn)9.3.2 LC方法要點(diǎn)方法要點(diǎn)n對(duì)狀態(tài)空間樹上的一個(gè)對(duì)狀態(tài)空間樹上的一個(gè)答案結(jié)點(diǎn)答案結(jié)點(diǎn)x, 定義定義實(shí)際代價(jià)實(shí)際代價(jià)函數(shù)函數(shù)cost(x

44、)。cost(x)的內(nèi)涵：從狀態(tài)空間樹根結(jié)點(diǎn)出發(fā)，到達(dá)一的內(nèi)涵：從狀態(tài)空間樹根結(jié)點(diǎn)出發(fā)，到達(dá)一個(gè)答案結(jié)點(diǎn)個(gè)答案結(jié)點(diǎn)x，實(shí)際需要付出的，實(shí)際需要付出的“代價(jià)代價(jià)”。cost(x)的定義：原則上應(yīng)根據(jù)具體問題加以定義。的定義：原則上應(yīng)根據(jù)具體問題加以定義。n對(duì)狀態(tài)空間樹對(duì)狀態(tài)空間樹上任一結(jié)點(diǎn)上任一結(jié)點(diǎn)x，定義，定義代價(jià)函數(shù)代價(jià)函數(shù)c(x)。c(x)的內(nèi)涵：從狀態(tài)空間樹根結(jié)點(diǎn)出發(fā)，經(jīng)過的內(nèi)涵：從狀態(tài)空間樹根結(jié)點(diǎn)出發(fā)，經(jīng)過x結(jié)結(jié)點(diǎn)，在點(diǎn)，在以結(jié)點(diǎn)以結(jié)點(diǎn)x為根的子樹上為根的子樹上，搜索到一個(gè)答案結(jié)，搜索到一個(gè)答案結(jié)點(diǎn)，所需要付出的代價(jià)。點(diǎn)，所需要付出的代價(jià)。定義定義c(x)的一般原則：的一般原則：n若若

45、x是答案結(jié)點(diǎn)，則：是答案結(jié)點(diǎn)，則：c(x) = cost(x)；n若若x不是答案結(jié)點(diǎn)，但以不是答案結(jié)點(diǎn)，但以x為根的子樹上為根的子樹上至少有一個(gè)至少有一個(gè)答案結(jié)點(diǎn)，則：答案結(jié)點(diǎn)，則：c(x) = minc(answer) |answer : x上所有答案結(jié)點(diǎn)上所有答案結(jié)點(diǎn)n若若x不是答案結(jié)點(diǎn)，且以不是答案結(jié)點(diǎn)，且以x為根的子樹上也沒有答案為根的子樹上也沒有答案結(jié)點(diǎn)，則：結(jié)點(diǎn)，則：c(x) = +n對(duì)狀態(tài)空間樹上結(jié)點(diǎn)對(duì)狀態(tài)空間樹上結(jié)點(diǎn)x, 定義定義估算函數(shù)估算函數(shù) ，且使?jié)M，且使?jié)M足：足： c(x)。注：與注：與c(x)相比，相比， 應(yīng)是當(dāng)前應(yīng)是當(dāng)前“可計(jì)算可計(jì)算”的。的。n設(shè)計(jì)一個(gè)活結(jié)點(diǎn)表設(shè)計(jì)

46、一個(gè)活結(jié)點(diǎn)表L，用于存放搜索過程的，用于存放搜索過程的“活活結(jié)點(diǎn)結(jié)點(diǎn)”。該表的數(shù)據(jù)結(jié)構(gòu)可選擇。該表的數(shù)據(jù)結(jié)構(gòu)可選擇有序表有序表或或堆堆。即要求：活結(jié)點(diǎn)表上的所有結(jié)點(diǎn)，按照它們即要求：活結(jié)點(diǎn)表上的所有結(jié)點(diǎn)，按照它們估算估算函數(shù)取值函數(shù)取值，構(gòu)成一個(gè)有序表或堆。，構(gòu)成一個(gè)有序表或堆。)(xc)(xc)(xc=h(x)+g(x)nLC法搜索過程：法搜索過程：初始：把狀態(tài)空間樹的根結(jié)點(diǎn)，做為活結(jié)點(diǎn)表初始：把狀態(tài)空間樹的根結(jié)點(diǎn)，做為活結(jié)點(diǎn)表L的的第一個(gè)結(jié)點(diǎn)；第一個(gè)結(jié)點(diǎn)；重復(fù)以下兩步，直到找到一個(gè)解，或重復(fù)以下兩步，直到找到一個(gè)解，或L為空：為空：n從從L上選出具有最小上選出具有最小 的結(jié)點(diǎn)，作為當(dāng)前的結(jié)

47、點(diǎn)，作為當(dāng)前E-結(jié)點(diǎn)。結(jié)點(diǎn)。n依次搜索當(dāng)前依次搜索當(dāng)前E-結(jié)點(diǎn)的所有子結(jié)點(diǎn)。若子結(jié)點(diǎn)是答結(jié)點(diǎn)的所有子結(jié)點(diǎn)。若子結(jié)點(diǎn)是答案結(jié)點(diǎn)，則結(jié)束；否則，把子結(jié)點(diǎn)加入有序表案結(jié)點(diǎn)，則結(jié)束；否則，把子結(jié)點(diǎn)加入有序表L。)(xc9.3.3 LC方法應(yīng)用舉例方法應(yīng)用舉例n15迷問題。迷問題。n問題描述：把編號(hào)為問題描述：把編號(hào)為115的棋子，隨意放在的棋子，隨意放在44格的格的棋盤上棋盤上(空出一個(gè)格空出一個(gè)格)。要求：經(jīng)過有限步的移動(dòng)，把。要求：經(jīng)過有限步的移動(dòng)，把棋盤上棋子的棋盤上棋子的“初態(tài)初態(tài)”，變成棋子號(hào)與棋盤號(hào)一致的，變成棋子號(hào)與棋盤號(hào)一致的目標(biāo)狀態(tài)。目標(biāo)狀態(tài)。(注：注：“移動(dòng)移動(dòng)”僅限于僅限于空格周

48、圍空格周圍棋子棋子)實(shí)例：實(shí)例： 初態(tài)初態(tài) 目標(biāo)狀態(tài)目標(biāo)狀態(tài)124563791012813141115123456789101112131415n分析：分析：實(shí)際代價(jià)函數(shù)實(shí)際代價(jià)函數(shù)cost(x): 若若x是目標(biāo)狀態(tài)，則：是目標(biāo)狀態(tài)，則：cost(x)等于從棋盤初態(tài)，等于從棋盤初態(tài)，經(jīng)逐步移動(dòng)棋子而到達(dá)目標(biāo)狀態(tài)經(jīng)逐步移動(dòng)棋子而到達(dá)目標(biāo)狀態(tài)x，實(shí)際需要移動(dòng)實(shí)際需要移動(dòng)棋子總步數(shù)棋子總步數(shù)。代價(jià)函數(shù)代價(jià)函數(shù)c(x):n若若x是目標(biāo)狀態(tài)，則：是目標(biāo)狀態(tài)，則：c(x) = cost(x)n若若x不是目標(biāo)狀態(tài)，但不是目標(biāo)狀態(tài)，但x所在子樹上存在目標(biāo)狀態(tài)結(jié)所在子樹上存在目標(biāo)狀態(tài)結(jié)點(diǎn)，點(diǎn)， 則：則：c(x)

49、 = min c(x) | x：x子樹上所有目標(biāo)狀子樹上所有目標(biāo)狀態(tài)結(jié)點(diǎn)態(tài)結(jié)點(diǎn)n若若x不是目標(biāo)狀態(tài)，且不是目標(biāo)狀態(tài)，且x所在子樹上也不存在任何目所在子樹上也不存在任何目標(biāo)狀態(tài)結(jié)點(diǎn)，則標(biāo)狀態(tài)結(jié)點(diǎn)，則c(x) = +定義估算函數(shù)：定義估算函數(shù)： = h(x) + g(x)n其中，其中，h(x):從狀態(tài)空間樹的根結(jié)點(diǎn)到從狀態(tài)空間樹的根結(jié)點(diǎn)到x結(jié)點(diǎn)結(jié)點(diǎn)路徑長(zhǎng)度路徑長(zhǎng)度；g(x)：x狀態(tài)下，狀態(tài)下，沒有沒有達(dá)到達(dá)到“目標(biāo)狀態(tài)目標(biāo)狀態(tài)”的的棋子數(shù)量棋子數(shù)量。124563791012813141115124563791012813141115123456791012813141115124563791012813141115g1=6h1=01g2=7g3=5g4=7234左左下下右右1)(xc123456791012813141115g3=531123456791012813141115123456791012813141115123456127910813141115123567491012813141115123456789101213141115g5=6657左左右右下下g6=4g7=52g9=3g8=5下下上上983123456789