四川理工學(xué)院算法剖析PPT課件

1、分支限界法離不開對(duì)問題狀態(tài)空間樹的搜索，基本搜索方法是先進(jìn)先出（FIFO）搜索，它類似BFS；或者是后進(jìn)先出（LIFO）搜索，它類似于DFS。FIFO搜索法與LIFO搜索法的定義如下：對(duì)當(dāng)前E-結(jié)點(diǎn)，先從左至右地產(chǎn)生它的兒子，用限界函數(shù)對(duì)這些兒子進(jìn)行檢查，如果不是死結(jié)點(diǎn)，就將它放入活結(jié)點(diǎn)表中，然后從活結(jié)點(diǎn)表中依次取出一個(gè)結(jié)點(diǎn)作為E-結(jié)點(diǎn)在生成問題的狀態(tài)的方法中，需要一張活結(jié)點(diǎn)表。對(duì)E-結(jié)點(diǎn)檢索完畢之后檢測(cè)以隊(duì)列或棧的，重復(fù)前面過程，如果只要求找出一個(gè)解，搜索進(jìn)行到產(chǎn)生一個(gè)解為止；如果要求找出全部解，搜索進(jìn)行到活結(jié)點(diǎn)表空為止。以隊(duì)列形式存放活結(jié)點(diǎn)的表的檢索方式稱為FIFO-檢索；以棧形式存放活結(jié)

2、點(diǎn)的表的檢索方式稱為L(zhǎng)IFO-檢索。這兩種方法都用限界函數(shù)殺死還沒有全部生成其兒子結(jié)點(diǎn)的那些活結(jié)點(diǎn)。 第1頁(yè)/共48頁(yè) 回溯法和分枝-限界法不一樣?；厮莘ㄊ钱?dāng)前E-結(jié)點(diǎn)R一旦生成一個(gè)新的兒子C，這個(gè)兒子結(jié)點(diǎn)就變成一個(gè)新的E-結(jié)點(diǎn)，當(dāng)完全檢索了子樹C之后，R再次成為E-結(jié)點(diǎn)，在檢索中不斷地用限界函數(shù)殺死不可能成為答案結(jié)點(diǎn)的那些結(jié)點(diǎn)?；厮莘ㄏ喈?dāng)于圖的深度優(yōu)先，再配之遞歸。而分枝-限界法中，下一個(gè)E-結(jié)點(diǎn)取自于對(duì)頭元素或棧頂元素，一個(gè)E-結(jié)點(diǎn)一直保持到變成死結(jié)點(diǎn)為止，在檢索過程中也不斷地用限界函數(shù)殺死那些不可能成為答案結(jié)點(diǎn)的結(jié)點(diǎn)。它的檢索順序完全由活結(jié)點(diǎn)表控制，并且分支限界法適合與最優(yōu)化問題。 第2

3、頁(yè)/共48頁(yè)為了說(shuō)明這兩種檢索方式再看4-后問題（例4.1）設(shè)想棋盤的風(fēng)格用A(1:n,1:n)的下標(biāo)標(biāo)記，假定兩個(gè)皇后被放置在(i,j)和(k,l)位置上，那么當(dāng)且僅當(dāng)i-j=k-l或i+j=k+l時(shí)，這兩個(gè)皇后在同一斜角線上，將這兩個(gè)等式變形j-l=i-k和j-l=k-i，因此|j-l|i-k|，描述了隱式約束的第二條規(guī)定，以|j-l|i-k|作為限界函數(shù)。2181349圖8.1 由FIFO分枝-限界法生成的一部分4-后狀態(tài)空間樹111416303236385254575938131924293540455156615015311234567891011121314151617181920

4、21 2223 2425262728293031B答案結(jié)點(diǎn)BBBBBBBBBBBBBB第3頁(yè)/共48頁(yè)用FIFO檢索4-后問題的狀態(tài)空間樹(如圖8.1)的過程如下：起初，只有一個(gè)活結(jié)點(diǎn)，它表示沒有皇后放入棋盤這一狀態(tài)，擴(kuò)展這個(gè)結(jié)點(diǎn)，生成它的兒子結(jié)點(diǎn)，18， 34， 50，這些結(jié)點(diǎn)分別表示皇后1放在第一行上的1或2 或3或4列的情況下所成的棋盤格局，此刻將活結(jié)點(diǎn)，18，34，50依次放入隊(duì)列，從隊(duì)列中取出，作為E-結(jié)點(diǎn)，擴(kuò)展生成，13，利用限界函數(shù)被殺死，將，13加入活結(jié)點(diǎn)隊(duì)列，此時(shí)隊(duì)列形如 隊(duì)頭隊(duì)尾183450813第4頁(yè)/共48頁(yè) 接下來(lái)，從隊(duì)列中取出18作為E-結(jié)點(diǎn)，生成19，24,29,

5、限界函數(shù)殺死，24，結(jié)點(diǎn)29加入活結(jié)點(diǎn)隊(duì)列，下一個(gè)E-結(jié)點(diǎn)是34，圖8.4說(shuō)明了用FIFO分枝-限界檢索的過程，用限界函數(shù)殺死的那些結(jié)點(diǎn)的下方有一個(gè)B字，在到達(dá)答案結(jié)點(diǎn)31時(shí)，僅剩下活結(jié)點(diǎn)38以及54仔細(xì)分析用FIFO分枝-限界檢索4-后問題的狀態(tài)空間樹的過程，在結(jié)點(diǎn)29之后，30并不是馬上成為E-結(jié)點(diǎn)，而是從活結(jié)點(diǎn)表中取得35作為E-結(jié)點(diǎn)，如果能將30作為E-結(jié)點(diǎn)的話，生成的兒子結(jié)點(diǎn)31便是答案結(jié)點(diǎn)。FIFO沒有把如果變?yōu)楝F(xiàn)實(shí)，盡管距獲得答案結(jié)點(diǎn)僅一步之遙，可FIFO毫不理會(huì)，固執(zhí)地按活結(jié)點(diǎn)表的先進(jìn)先出原則決定誰(shuí)是下一個(gè)E-結(jié)點(diǎn)，直到按此刻板的順序，輪到30作為E-結(jié)點(diǎn)，才生成31這個(gè)答案結(jié)

6、點(diǎn)。這是一個(gè)刻板的、尋規(guī)蹈矩的方法。如果能讓30有著比其它活結(jié)點(diǎn)表中的結(jié)點(diǎn)更高的優(yōu)先權(quán)，在選擇下一個(gè)E-結(jié)點(diǎn)時(shí)，按優(yōu)先權(quán)作出選擇，那么可大大地提前找到答案結(jié)點(diǎn)。如果只需找到一個(gè)答案結(jié)點(diǎn)，那么剩下的活結(jié)點(diǎn)就不必再檢索了。FIFO檢索帶有盲目性，LIFO檢索也亦如此，不再累贅敘述。下面介紹LC-檢索，它克服了這種盲目性。第5頁(yè)/共48頁(yè)8.1.2 LC-檢索要使可能導(dǎo)致出答案結(jié)點(diǎn)的活結(jié)點(diǎn)X獲得比其它結(jié)點(diǎn)更高的優(yōu)先權(quán)，需要測(cè)試X到答案結(jié)點(diǎn)之間的“距離”，對(duì)于“距離”最自然的是想到用下面兩個(gè)標(biāo)準(zhǔn)之一去度量。1.在生成一個(gè)答案結(jié)點(diǎn)之前，子樹X需要生成的結(jié)點(diǎn)數(shù)。2.在子樹X中，X到最近一個(gè)答案結(jié)點(diǎn)的路徑長(zhǎng)

7、。使用1的標(biāo)準(zhǔn)，則對(duì)分枝-限界算法，總是生成最少的結(jié)點(diǎn)；如果使用2，則要成為E-結(jié)點(diǎn)的結(jié)點(diǎn)，只能是由根到最近的那個(gè)答案結(jié)點(diǎn)路徑上的那些結(jié)點(diǎn)。除了以上1，2之外，還有其它合理的定義。一般地，定義一個(gè)成本函數(shù)來(lái)描述狀態(tài)空間樹中結(jié)點(diǎn)的這一遠(yuǎn)近關(guān)系。C函數(shù)定義如下：第6頁(yè)/共48頁(yè) 如果X是答案結(jié)點(diǎn)，則C(X)是狀態(tài)空間樹中從根到X的成本（所謂成本，可以是級(jí)數(shù)，可以是上述“距離”，也可以是計(jì)算復(fù)雜度）； 如果X不是答案結(jié)點(diǎn)，且子樹X不包含任何答案結(jié)點(diǎn)C(X)=；否則C(X)等于子樹X中具有最小成本的答案結(jié)點(diǎn)的成本。 這個(gè)定義是遞歸的，用計(jì)算結(jié)點(diǎn)的成本函數(shù)，對(duì)結(jié)點(diǎn)賦予優(yōu)先權(quán)是很合理的，但是仔細(xì)想一想，計(jì)

8、算結(jié)點(diǎn)X的成本函數(shù)值C(X)并不容易，它和解決原問題有同樣的復(fù)雜度，因此，雖然C(X)是精確的，但是卻是不容易的。因此，試圖在解決問題中計(jì)算結(jié)點(diǎn)X的成本，C(X)的方法是不可取的。第7頁(yè)/共48頁(yè) 既然精確成本不易求得，那么可以考慮計(jì)算結(jié)點(diǎn)的估計(jì)成本，估計(jì)成本函數(shù)g(X)C(X)。 g(X)易于計(jì)算。在選擇下一個(gè)E-結(jié)點(diǎn)時(shí)，選擇活結(jié)點(diǎn)表中g(shù)(X)最小的活結(jié)點(diǎn)，作為下一個(gè)E-結(jié)點(diǎn)。但是如果僅用g(X)作為選擇下一個(gè)E-結(jié)點(diǎn)的標(biāo)準(zhǔn)也未必就合理，因?yàn)樗鼤?huì)導(dǎo)致檢索偏向縱深進(jìn)行。設(shè)X是當(dāng)前的E-結(jié)點(diǎn)，它的兒子為Y，那么g(Y)C(X)。因此在活結(jié)點(diǎn)表中的其它結(jié)點(diǎn)的估計(jì)成本均大于g(Y)，于是Y在X之后變

9、成E-結(jié)點(diǎn)，然后Y的兒子們中又有一個(gè)變成E-結(jié)點(diǎn)，如此進(jìn)行下去，直到子樹X全部檢索完畢后，才也可能使那些在另外一棵子樹上的結(jié)點(diǎn)成為E-結(jié)點(diǎn)。如果g(X)=C(X)，這種縱深檢索正是所希望的。因?yàn)榘催@種最小成本優(yōu)先檢索可以很快地到達(dá)離根最近的答案結(jié)點(diǎn)，其它子樹上的結(jié)點(diǎn)就不必檢索了，但是若g(X)C(X)，偏向縱深檢索，可能導(dǎo)致不能很快地去檢索離根結(jié)點(diǎn)最近的答案結(jié)點(diǎn)。比如，設(shè)結(jié)點(diǎn)W和Z，若g(W)g(Z)，且Z比W更接近答案結(jié)點(diǎn)，但卻不能優(yōu)先地檢索Z。為了避免這種“縱深”的弊端，改革估計(jì)成本函數(shù)，其做法是不僅考慮結(jié)點(diǎn)的估計(jì)成本g(X)，同時(shí)考慮，由根結(jié)點(diǎn)到X的成本h(X)，定義新的成本估計(jì)函數(shù)c(

10、X)=f(h(X)+g(X)，其中f是一個(gè)非降函數(shù)。用f0可以減少偏向縱深檢查的弊端。如果g(Y) g(Z) ，但c(Y)c(Z)，強(qiáng)迫優(yōu)先檢索Z。第8頁(yè)/共48頁(yè)用c(X)=f(h(X)+g(X)，根據(jù)c值最小的結(jié)點(diǎn)作為E-結(jié)點(diǎn)的檢索方法稱為最小成本檢索，簡(jiǎn)稱LC-檢索(least cost search)，伴之以限界函數(shù)的LC-檢索，稱為L(zhǎng)C-分枝-限界檢索。FIFO-檢索和LIFO-檢索是LC-檢索的特殊情況。如果令g(X)0，f(h(X)是結(jié)點(diǎn)X的級(jí)數(shù)，則LC-檢索根據(jù)級(jí)數(shù)小的優(yōu)先成為E-結(jié)點(diǎn)，這就是FIFO-檢索；如果f(h(X) 0，且當(dāng)Y是X的兒子時(shí)，總有g(shù)(Y) g(X)，這就

11、是LIFO檢索。從c的定義可以看出，定義g(X)是很重要的，它需要對(duì)原問題有深入的理解和較強(qiáng)的數(shù)學(xué)表達(dá)能力，恰當(dāng)?shù)亟o出g(X)是要付出艱辛的勞動(dòng)的，而g(X)的好壞又直接影響了算法的優(yōu)劣。第9頁(yè)/共48頁(yè)例8.1 15謎問題（15-puzzle）在44的方格棋盤上，將數(shù)字1，2，3，15以任意順序放置在棋盤的各個(gè)方格中，空出一格，如圖8.2(a)為15謎問題的一種初始棋盤格局。134151234251256787611149101112891013131415(a)初始狀態(tài) (b)目標(biāo)狀態(tài) 第10頁(yè)/共48頁(yè) 要求通過有限次移動(dòng)，把一個(gè)初始狀態(tài)變成圖8.2(b)的目標(biāo)狀態(tài)。移動(dòng)規(guī)則是：每次只能

12、在空格周圍的四個(gè)數(shù)字任選一個(gè)移入空格，當(dāng)空格在邊角位置時(shí)，只有二種或三種數(shù)字向空格的移動(dòng)是合法的，這個(gè)規(guī)則就是原問題的規(guī)范函數(shù)，其目標(biāo)函數(shù)是描述目標(biāo)狀態(tài)的棋盤格局。顯然移動(dòng)數(shù)字與移動(dòng)空格是等效的，如果對(duì)于某個(gè)狀態(tài)A可以通過一系列合法移動(dòng)得到另一狀態(tài)B。則稱狀態(tài)A可達(dá)狀態(tài)B。一個(gè)實(shí)例的狀態(tài)空間樹由初始狀態(tài)可達(dá)的所有狀態(tài)構(gòu)成。15謎問題一共有16！個(gè)棋盤格局。有人證明了，對(duì)于任一給定的初始狀態(tài)，有16！/2狀態(tài)可由初始狀態(tài)到達(dá)。因此15謎問題的狀態(tài)空間樹很大。在求解15謎問題的一個(gè)實(shí)例時(shí)，首先應(yīng)確定目標(biāo)狀態(tài)是否存在于這一實(shí)例的狀態(tài)空間樹中，也就是說(shuō)實(shí)例是否有解，這是首先要解決的問題。如果給棋盤上的

13、各個(gè)方格按行為主序編號(hào)116，空格為16號(hào)，定義l(i)是棋盤上第i+1格到第16格中，比i格中棋子號(hào)碼小的棋子的個(gè)數(shù)，對(duì)于圖8.2(a)，l(1)=0，l(2)=1，l(6)=10，l(16)=0，在圖8.2(b)中有l(wèi)(i)=0，1i16，設(shè)空格位于棋盤第j行，第k列，可以證明如下事實(shí)。第11頁(yè)/共48頁(yè) 161)(ikjil定理8.1 對(duì)于一個(gè)給定的狀態(tài)如果這個(gè)和數(shù)是偶數(shù)，則這個(gè)狀態(tài)可達(dá)目標(biāo)狀態(tài)，否則其它任何初態(tài)都不可達(dá)目標(biāo)狀態(tài)。證明從略。利用定理8.1，可以解決15謎問題的實(shí)例的解的存在性問題。如果有解，就可以從初態(tài)開始，通過一系列合法的移動(dòng)到達(dá)目標(biāo)狀態(tài)。至于如何求解，這需要在狀態(tài)空間

14、樹上去檢索目標(biāo)狀態(tài)，從根到目標(biāo)狀態(tài)的路徑上的狀態(tài)，確定了這一實(shí)例的一個(gè)解。由于實(shí)例的狀態(tài)空間樹很大，并且空格的移動(dòng)是可逆的，搞不好會(huì)形成死循環(huán)。如果每產(chǎn)生一個(gè)新狀態(tài)都要和已產(chǎn)生的狀態(tài)一一對(duì)比，把重復(fù)狀態(tài)刪去，這勢(shì)必要搜索整個(gè)狀態(tài)空間樹，工作量太大是不許可的。 第12頁(yè)/共48頁(yè)第13頁(yè)/共48頁(yè)圖8.3給出了一個(gè)實(shí)例的狀態(tài)空間樹的前幾級(jí)，圖中已對(duì)樹作了一些修剪，對(duì)此實(shí)例，F(xiàn)IFO檢索的順序按圖中結(jié)點(diǎn)的編號(hào)順序進(jìn)行。從檢索的路徑可以看出，這樣的檢索是很盲目的。下面考慮如何用LC-分枝限界解此實(shí)例，成本函數(shù)c(X)定義成從根到最近目標(biāo)結(jié)點(diǎn)的路徑長(zhǎng)度。如前所述精確成本一般是不容易求得的，估計(jì)成本c(

15、X)=f(X)+g(X),f(X)定義成從根到X的路徑長(zhǎng)度，剩下的問題也是關(guān)鍵的問題，是如何定義g(X)。第14頁(yè)/共48頁(yè)設(shè)想1：g(X)是結(jié)點(diǎn)X表示的狀態(tài)中沒有到達(dá)目標(biāo)位置的非空白牌的數(shù)目。顯然狀態(tài)X到達(dá)目標(biāo)狀態(tài)所需要的移動(dòng)空白牌的次數(shù)大于g(X)，比如狀態(tài)X123456891011121314157只有7號(hào)牌不在目標(biāo)位置上（空白牌除外），于是g(X)=1，但是要使這個(gè)狀態(tài)X變成目標(biāo)狀態(tài)，需要移動(dòng)空白牌的次數(shù)比1多得多。因此g(X)是精確成本c(X)的下界，而且g(X)是容易求得的。有如此定義的c(X)，對(duì)于圖8-3所示的實(shí)例，由初始狀態(tài)出發(fā)，把作為E-結(jié)點(diǎn)，生成它的四個(gè)兒子，后成為死結(jié)點(diǎn)

16、，因?yàn)閏(2)=1+4，c(3)=1+4，c(4)=1+2，c(5)=1+4，因此成為E-結(jié)點(diǎn)，生成它的兒子10 11 12，此時(shí)活結(jié)點(diǎn)是、10、 11 12；因?yàn)閏(10)=2+1，c(11)=2+3，c(12)=2+3，此刻具有最小c值的活結(jié)點(diǎn)是10，它成為下一個(gè)E-結(jié)點(diǎn)，接著生成22、 23，結(jié)點(diǎn)23被判定是目標(biāo)結(jié)點(diǎn) 。這個(gè)設(shè)想是可行的，而且是一個(gè)很好的方法。第15頁(yè)/共48頁(yè) 161)()()(ijlilXg設(shè)想2，f(x)同設(shè)想1， 這里j表示空格的位置。它也是一個(gè)可行的方法，似乎不及設(shè)想1中的g(X)好，因?yàn)閷?duì)圖8.3給定的初態(tài)，它需要產(chǎn)生更多的結(jié)點(diǎn)，但是如果檢索如23456789

17、1011121314151的狀態(tài)空間樹，按設(shè)想1，g(1)=1，按設(shè)想2，g(1)=14。這里f(X)+14=14顯然更接近c(diǎn)(X)，c(X)是初態(tài)到目標(biāo)狀態(tài)的路徑長(zhǎng)度，即需要移動(dòng)空白牌的次數(shù)。第16頁(yè)/共48頁(yè)8.1.3 LC-檢索的抽象化描述設(shè)T是一棵狀態(tài)空間樹，C是T中結(jié)點(diǎn)的成本函數(shù)，如果X是T中的一個(gè)結(jié)點(diǎn)，C(X)是其根為X的子樹中任一答案結(jié)點(diǎn)的最小成本，從而C（T）是T中最小成本答案結(jié)點(diǎn)的成本，C（X）是估計(jì)成本函數(shù)，C易于計(jì)算，C（X）C(X)。如果X是一個(gè)答案結(jié)點(diǎn)或者是一個(gè)葉結(jié)點(diǎn)，則C（X）C(X)。在許多應(yīng)用中，并不是僅僅滿足找到一個(gè)答案結(jié)點(diǎn)，而是要找到具有最小成本的答案結(jié)點(diǎn)，

18、為了達(dá)到這一目的，要求在定義C時(shí)，除上述要求外還必須滿足對(duì)每一對(duì)C(X)C（Y）的X，Y結(jié)點(diǎn)，都有C（X）C（Y）。在這些前提之下，找最小成本答案結(jié)點(diǎn)的LC-檢索描述如下：第17頁(yè)/共48頁(yè)算法8.1：procedure LC(T，C)；beginET；置活結(jié)點(diǎn)表為空；loop if E是答案結(jié)點(diǎn) then begin 輸出從E到T的路徑； return；end；for E的每個(gè)兒子結(jié)點(diǎn)X do begin call add(x)； parent(x)E； end；if 不再有活結(jié)點(diǎn) then begin print(No answer node)； stop； end；call least(

19、E)；repeat；endp；第18頁(yè)/共48頁(yè)在上面算法中有兩子算法，least(X)和add(X)，least(X)在活結(jié)點(diǎn)表中找出一個(gè)具有最小C值的活結(jié)點(diǎn)，并在活結(jié)點(diǎn)表中刪除這個(gè)結(jié)點(diǎn)，將此結(jié)點(diǎn)放在變量X中返回。add(X)，將新的活結(jié)點(diǎn)X加到活結(jié)點(diǎn)表?；罱Y(jié)點(diǎn)表作為一個(gè)最小堆。實(shí)際上LC算法與FIFO，LIFO檢索基本相同，區(qū)別在活結(jié)點(diǎn)表的結(jié)構(gòu)與其上的操作，F(xiàn)IFO的活結(jié)點(diǎn)表是隊(duì)列，下一個(gè)E-結(jié)點(diǎn)總是取當(dāng)前表的隊(duì)頭元素。LIFO的活結(jié)點(diǎn)表是棧，下一個(gè)E-結(jié)點(diǎn)總是取至于棧頂元，而LC檢索是取活結(jié)點(diǎn)表中具有最小C值的結(jié)點(diǎn)作為下一個(gè)E-結(jié)點(diǎn)，因此三者的區(qū)別在于下一個(gè)E-結(jié)點(diǎn)的選擇規(guī)則不同。第19

20、頁(yè)/共48頁(yè)8.2 分枝-限界法解最優(yōu)化問題 在前面8.1講解狀態(tài)空間樹中，曾提到過問題的解應(yīng)滿足限界函數(shù)P(x-1,x2,，xn)。在生成狀態(tài)空間樹時(shí)，對(duì)于結(jié)點(diǎn)X，如果它的某個(gè)兒子Y對(duì)應(yīng)的狀態(tài)不滿足規(guī)范函數(shù)（也作限界函數(shù)）P(x1,x2,，xn)，則X的這個(gè)分枝即被剪去。也就是通過限界函數(shù)P可以對(duì)狀態(tài)空間樹作出一次剪枝。在這樣的狀態(tài)空間樹上，對(duì)于任意結(jié)點(diǎn)定義成本函數(shù)C(X)和成本估計(jì)函數(shù)C（X）。當(dāng)C(X)C（Y）時(shí)，C（X）C（Y）。于是在這個(gè)狀態(tài)空間樹上，當(dāng)有至少一個(gè)答案結(jié)點(diǎn)時(shí)，可以用LC-檢索求得最小成本的結(jié)點(diǎn)，在求解過程中函數(shù)C的使用，使分枝-限界算法減少了FIFO，LIFO檢索的盲

21、目性，加快了找最小成本結(jié)點(diǎn)的速度。在算法中，函數(shù)C是C的下界，另外，還可以通過設(shè)置最小成本的上界使算法進(jìn)一步加速，具體做法是，如果U是最小成本的上界，則凡是C（X）U的所有活結(jié)點(diǎn)X可以殺死，也就是說(shuō)剪去這個(gè)分枝。因?yàn)橛蒟可以到達(dá)的所有答案結(jié)點(diǎn)C(X)C（X）U。U的初始值可以用某種啟發(fā)性方法得到，也可置為，只要U的初始值不小于成本答案結(jié)點(diǎn)的成本，剪去的分枝就不可能有最小成本的答案結(jié)點(diǎn)。每當(dāng)找到一個(gè)新的答案結(jié)點(diǎn)就修改U的值。 第20頁(yè)/共48頁(yè) 下面著重討論用分枝-限界法解最優(yōu)化問題，僅考慮極小化問題，極大化問題可以通過改變目標(biāo)函數(shù)的符號(hào)轉(zhuǎn)化成極小化問題。規(guī)范函數(shù)定義了解的特征，也就是說(shuō)滿足規(guī)范

22、函數(shù)的向量是問題的解。最優(yōu)化問題是求使某個(gè)稱為目標(biāo)函數(shù)取得極小值且成本又最小的解。這種解稱為最優(yōu)解。這需要進(jìn)一步地在狀態(tài)空間樹的答案結(jié)點(diǎn)中進(jìn)行選擇。既要找到答案結(jié)點(diǎn)，也就是說(shuō)找到的結(jié)點(diǎn)的目標(biāo)函數(shù)值最小，又要使該結(jié)點(diǎn)的成本最小。要二者具佳，最簡(jiǎn)單的方法是直接把目標(biāo)函數(shù)作為成本函數(shù)C。在這樣的定義之下，代表可行解的結(jié)點(diǎn)X，X是答案結(jié)點(diǎn)。它的成本函數(shù)C(X)就是X的目標(biāo)函數(shù)值。代表不可行解的結(jié)點(diǎn)X，它的成本函數(shù)C(X)，代表部分解的結(jié)點(diǎn)X，C(X)是根為X的子樹中最小成本結(jié)點(diǎn)的成本。最優(yōu)解對(duì)應(yīng)著成本最小的答案結(jié)點(diǎn)。在最優(yōu)化問題中，如此定義的C也與前面求解一般問題一樣，計(jì)算C(X)和求解原問題有相同的

23、計(jì)算復(fù)雜度，也就是去計(jì)算對(duì)于所有X，使C（X）C(X)的估計(jì)函數(shù)C。在最優(yōu)化問題中，C函數(shù)不是用來(lái)估計(jì)到達(dá)一個(gè)答案結(jié)點(diǎn)在計(jì)算方面的難易程度，而是對(duì)目標(biāo)函數(shù)進(jìn)行估計(jì)。第21頁(yè)/共48頁(yè)例8.2 帶限期的作業(yè)排序問題假定有n個(gè)作業(yè)Wi,i=1,，n,和一臺(tái)處理機(jī)，每個(gè)作業(yè)Wi與一個(gè)三元組（pi,di,ti）對(duì)應(yīng)，其中ti是完成作業(yè)Wi需要的時(shí)間，di是完成作業(yè)Wi需要的期限，如果不在這個(gè)期限di之內(nèi)完成Wi則將受到pi的罰款。問題的目標(biāo)是從n個(gè)作業(yè)中選取一個(gè)子集J，要求J中的作業(yè)都能在相應(yīng)的限期內(nèi)完成，且使不在J中的作業(yè)受到的罰款總額最小，這樣的J就是最優(yōu)解。實(shí)例：n=4這個(gè)實(shí)例的解是向量。解空間

24、是作業(yè)的下標(biāo)集1，2，3，4所有可能的子集組成。用子集 第22頁(yè)/共48頁(yè)5111032621311pdtw1w2w3w4和數(shù)問題（例4.3）對(duì)解的兩種表示方法，均可以將它的解空間表示成一棵狀態(tài)空間樹。如圖8.4和8.5。在圖8.4表示的樹中，方形結(jié)點(diǎn)代表不可行解，圓形結(jié)點(diǎn)代表答案結(jié)點(diǎn)，結(jié)點(diǎn)是最優(yōu)解；圖8.5表示的樹中，方形結(jié)點(diǎn)代表不可行解，圓形葉子結(jié)點(diǎn)代表答案結(jié)點(diǎn)，結(jié)點(diǎn)25是最優(yōu)解。在圖8.5中各答案結(jié)點(diǎn)的罰款數(shù)標(biāo)在這些結(jié)點(diǎn)的下面。第23頁(yè)/共48頁(yè)在兩種狀態(tài)空間表示中，成本函數(shù)C定義為，對(duì)于圓形結(jié)點(diǎn)X，C(X)是根為X的子樹中結(jié)點(diǎn)的最小罰款，對(duì)于方形結(jié)點(diǎn)C(X)。在圖8.4中，C(3)8，

25、因?yàn)樵谝詾楦淖訕渲?，最小罰款是結(jié)點(diǎn)對(duì)應(yīng)的罰款8，它是這棵子樹中的最小罰款，而結(jié)點(diǎn)的罰款是11，根據(jù)C的定義C(3)8；而的最左子樹，因?yàn)镃(6)9，C(7)13，所以C(2)9；圖8.4 大小可變的元組表示對(duì)應(yīng)的狀態(tài)空間樹231451c=8c=0c=0c=556789101114131215x1=2x1=3x1=4x1=1c=15c=21x2=2x2=3x2=4c=0c=0c=5c=11c=15x2=3x2=4x2=4x3=3x3=4x3=4x3=4而圖8.5中C(1)8，C(2)9，C(5)13，C(6)8。第24頁(yè)/共48頁(yè)在前面已講過，求C值與解原問題有相同的難度，關(guān)鍵是如何定義C函數(shù)

26、，它是C的下界函數(shù)。設(shè)Sx是圓形結(jié)點(diǎn)X所對(duì)應(yīng)的對(duì)作業(yè)集J作出的一個(gè)子集，如果m=maxi|iSx則定義 ；如此定義的C，滿足C(X) C(X)。對(duì)于方形結(jié)點(diǎn)X，C(X)；而子樹X中最小成本答案結(jié)點(diǎn)的上界函數(shù)u(X)定義為： 在圖8.4中，對(duì)于結(jié)點(diǎn)，它是一個(gè)答案結(jié)點(diǎn)，S2=（1），m=1，于是C(2)0，u(2)=19，對(duì)于結(jié)點(diǎn)，它也是一個(gè)答案結(jié)點(diǎn)，S7=（1，3），m=3，于是C(7)10，u(7)=13。在圖8.5中，對(duì)于結(jié)點(diǎn)12，它是一個(gè)部分解（0，1，1，*），不是答案結(jié)點(diǎn)。S2=（2，3），m=3， xSiipu(X)xSimiipxC)( 第25頁(yè)/共48頁(yè)圖8.5 大小固定的元組表

27、示對(duì)應(yīng)的狀態(tài)空間樹2131c=8c=05x1=0 x1=145910111921236713141525293112302827260051015515106161121212418151411819139x3=1x3=0 x3=1x3=0 x2=1x2=0 x2=0 x2=1C(12)5，u(12)=8。以圖8.4元組大小不固定的狀態(tài)空間樹為例說(shuō)明作業(yè)排序的LC分枝-限界算法。開始時(shí)置最小成本答案結(jié)點(diǎn)的成本上界U=，或niip1U第26頁(yè)/共48頁(yè)假定使用圖8.4大小可變的元組，開始時(shí)作為E-結(jié)點(diǎn)，生成它的兒子，u(2)=19，u(3)=14，u(4)=18，u(5)=21，將U修改為U=1

28、4，因?yàn)镃(2)0，C(3)5，C(4)15，C(5)21。C(4)15U，C(5)21U，于是，殺死，也就是說(shuō)剪去，為根的兩棵子樹。，進(jìn)入活結(jié)點(diǎn)表，因?yàn)镃(2)0C(3)5，成為E-結(jié)點(diǎn)，生成它的兒子，由于是不可行解，被規(guī)范函數(shù)殺死，而u(6)=9，u(7)=13，將U改為9，C(6)0，C(7)10，因?yàn)镃(7) U，殺死，此時(shí)活結(jié)點(diǎn)進(jìn)入活結(jié)點(diǎn)表，而此時(shí)表中結(jié)點(diǎn)有，C(3)5C(6)0，作為E-結(jié)點(diǎn)，生成它的兩個(gè)兒子12，13，但12，13均是不可行解，被規(guī)范函數(shù)殺死，活結(jié)點(diǎn)表中只有，作為E-結(jié)點(diǎn)，生成它的兩個(gè)兒子，u(9)=8，u(10)=11，將U改為8 ，C(9)5，C(10)11，

29、C(10) U，被殺死。進(jìn)入活結(jié)點(diǎn)表，活結(jié)點(diǎn)表中只有一個(gè)結(jié)點(diǎn)，它作為E-結(jié)點(diǎn)，生成兒子15，但15是不可行解，被規(guī)范函數(shù)殺死，此時(shí)活結(jié)點(diǎn)表已空，是最優(yōu)解，它的成本值是C(9)8。由于圖8.4中每個(gè)圓形結(jié)點(diǎn)都是答案結(jié)點(diǎn)，按U的定義，xSiipu(X)第27頁(yè)/共48頁(yè)u(X)是結(jié)點(diǎn)X對(duì)應(yīng)的解Sx的成本值，即u(X)=c(X)。對(duì)于一般問題的LC分枝-限界求解，u(X)不一定總是結(jié)點(diǎn)X的成本，每次修改U后，如果U是一個(gè)單純的上界，那么凡是使C(X) U的活結(jié)點(diǎn)X都被殺死；如果U是一個(gè)已找到的答案結(jié)點(diǎn)的成本值時(shí)，使C(X) U的X應(yīng)被殺死。為了區(qū)別這兩種情況，在算法實(shí)現(xiàn)時(shí)，引進(jìn)一個(gè)很小的正數(shù)來(lái)進(jìn)行識(shí)

30、別。取得足夠小，使得對(duì)于任意兩個(gè)可行結(jié)點(diǎn)X，Y，如果u(X) u(Y)，則u(X) u(X )+ u(Y)。當(dāng)U是一答案結(jié)點(diǎn)的成本值時(shí)，U= u(X)= c(X)。當(dāng)U是一個(gè)單純上界時(shí)，U取u(X )+ ，當(dāng)U以這種方式更新時(shí)，凡是u(Y)U的活結(jié)點(diǎn)都被殺死，不必比較C值和U值。對(duì)于帶限期的作業(yè)排序，LC分枝-限界法并沒有體現(xiàn)出比FIFO分枝-限界法太多的優(yōu)越性。讀者可對(duì)上述實(shí)例用FIFO分枝-限界法實(shí)現(xiàn)求解過程，與LC分枝-限界法作一比較。 第28頁(yè)/共48頁(yè)下面是最優(yōu)化問題的LC分枝-限界算法8.2。procedure LCBB(T,c,u, ,cost)/為了找出最小成本結(jié)點(diǎn)，檢索狀態(tài)空

31、間樹T，假定T至少包含一個(gè)解結(jié)點(diǎn)，且C(X)C(X)u(X )/begin ET；parent(E)0； if T是解結(jié)點(diǎn) then begin Umin(cost(T),u(T)+ )； ansT； end else begin Uu(T)+ ； ans0； end；將活結(jié)點(diǎn)表初始化為空； loop for E的每個(gè)兒子 do if C(X) U then begin call ADD(X)； parent(X) E；第29頁(yè)/共48頁(yè)case：X是解結(jié)點(diǎn)and cost(X) U： begin Umin(cost(X),u(X)+ )； ansX； end；： u(X)+ U : Uu(X

32、)+ ： endcase；end； if 不再有活結(jié)點(diǎn) or 下一個(gè)E-結(jié)點(diǎn)有CU then beginprint(least cost=,U)；while ans0 do beginprint(ans)；ansparent(ans)； end；return；end；call least(E)； repeat； endp；第30頁(yè)/共48頁(yè)對(duì)算法LCBB還需強(qiáng)調(diào)以下幾點(diǎn)：1.當(dāng)下一個(gè)E-結(jié)點(diǎn)，使CU時(shí)，算法終止；2.子算法ADD是加入一個(gè)結(jié)點(diǎn)到活結(jié)點(diǎn)表中，LEAST是從一個(gè)活結(jié)點(diǎn)表中刪去一個(gè)結(jié)點(diǎn)，活結(jié)點(diǎn)表作成一個(gè)min-堆；3.如果U是已找到的一個(gè)解X的成本值，U=c(X)u(X)，對(duì)于X的兒

33、子Y，不僅c(Y) U而且c(Y) =U的結(jié)點(diǎn)Y都要被殺死；4.如果U是一個(gè)單純的上界，它是由一可行結(jié)點(diǎn) X的u值修改而得，U=u(X)+。對(duì)于X的兒子只殺死c(Y) U的Y，c(Y) =U的Y不被殺死，Y入堆；5.雖然找到了一個(gè)答案結(jié)點(diǎn)X，但它的成本值大于它的上界值u(X)，這說(shuō)明，這個(gè)答案結(jié)點(diǎn)的子孫中還有成本更小的答案結(jié)點(diǎn)，U取u(X)+ ，對(duì)于X的兒子結(jié)點(diǎn)Y，只殺死c(Y) U的Y，c(Y) =U的Y不被殺死，Y入堆；第31頁(yè)/共48頁(yè)8.3 0/1背包問題的LC分枝-限界求解的實(shí)現(xiàn)例8.3 0/1背包問題。已知有n種物品和一個(gè)可容納M重量的背包，每種物品i的重量為wi，假定將物品i放入

34、背包，可以得到pi的效益，問采用何種裝包方案，可以使背包中物品的總效益最大。為了獲得問題的最優(yōu)解，讓背包容量盡可能地緩慢消耗。要求將物品按容量的非降次序放入背包，同時(shí)為了使背包的效益值迅速增加，很自然地應(yīng)在效益值的增長(zhǎng)率與容量的消耗率之間取得平衡，也就是每一次放入背包的物品應(yīng)使它的每一單位容量獲得最大的效益，這就需要使物品的裝入次序按pi/wi比值的非增序進(jìn)行。第32頁(yè)/共48頁(yè)nixxMxwiiniii1101，或問題可描述如下：極小化： niiiwp1規(guī)范函數(shù)： 若干問題考慮如下：解空間：0/1背包問題的解可以表示成一個(gè)n元向量，各分量xi可以取0或1，解空間最多有2n個(gè)向量，這個(gè)解空間與

35、子集和數(shù)問題的解空間相同，有元組大小可變與元組大小固定兩種狀態(tài)空間樹。下面僅考慮第一種狀態(tài)空間樹，在這棵樹中，滿足的葉子是答案結(jié)點(diǎn)，而其它葉子都是不可行結(jié)點(diǎn)。第33頁(yè)/共48頁(yè)niiixp1成本函數(shù)：為了使最小成本答案結(jié)點(diǎn)與最優(yōu)解對(duì)應(yīng)，成本函數(shù)定義如下：1.如果X是答案結(jié)點(diǎn) C(X)= 2.如果X是不可行的葉子結(jié)點(diǎn)C(X)=；3.如果X是非葉子結(jié)點(diǎn)C(X)=minC(LCHILD(X),C(RCHILD(X)。界函數(shù)：下界函數(shù)C和上界函數(shù)u，要求對(duì)于狀態(tài)空間樹上的每個(gè)結(jié)點(diǎn)X，有C(X) C(X)u(X)。第34頁(yè)/共48頁(yè)niiixp1jiiixpXC1)(jiiixpXu1)(jiiixpX

36、C1)(設(shè)X是第j級(jí)上的一個(gè)結(jié)點(diǎn)，1jn+1。在結(jié)點(diǎn)X處已對(duì)前j-1種物品是否裝包作出了抉擇xi（xi =0或1，1ij。于是當(dāng)前背包的成本為,由C的定義 ，可知 ，取 ，對(duì)于第j到n種物品，如果 ，則修改u(X)。具體實(shí)現(xiàn)如下：第35頁(yè)/共48頁(yè)算法8.3procedure UBOUND(P，W，k，M)；/P：當(dāng)前效益總量；W：當(dāng)前背包重量；k：上次處理的物品的下標(biāo)號(hào)；M：背包容量，W(i)：第i種物品的重量；P(i)：第i種物品的效益值，并且P(i)/W(i)P(i+1)/W(i+1)，1in/begin bP；cW； for ik+1 to n do if c+ W(i)M then

37、begin cc+ W(i)； bb- P(i)； end； return(b)；endp；第36頁(yè)/共48頁(yè)jiiixw1jiiixp1如果X是j級(jí)上的一個(gè)結(jié)點(diǎn)，1jn+1，則u(X)=UBOUND ( , ,j-1,M)下界函數(shù)C(X)可以定義如下：對(duì)于jin，將xi=0或1的要求放寬到0 xi1，然后用貪婪法求解這個(gè)放寬了要求的問題，具體實(shí)現(xiàn)如下：第37頁(yè)/共48頁(yè)算法8.4.算法中涉及的說(shuō)明同算法8.3.procedure BOUND(P，W，k，M)；begin bP；cW； for ik+1 to n do begin cc+ W(i)； if cM then bb-P(i)els

38、ereturn(b-(1-(c-M)/W(i)*P(i)； end；return(b)；endp；第38頁(yè)/共48頁(yè)jiiixp1jiiixw1C(X)=BOUND( , ,j-1,M)考慮背包問題的一個(gè)實(shí)例 n=4； P=(10，10，12，18)；W=(2，4，6，9)， M=15。由u和C的定義，LCBB分枝-限界函數(shù)的檢索過程如下：開始將根（圖8.6）作為E-結(jié)點(diǎn)，C(1)=-（10+10+12+1/318）=-38，u(1)=-10-10-12=-32；由于不是答案結(jié)點(diǎn)，因此過程LCBB置ans=0和U=-32+。擴(kuò)展，生成它的兒子、，C(2)=-38，C(3)=-(10+12+5/

39、918)=-32，u(2)=-32,u(3)=-(10+12)=-22，因?yàn)镃(2)U，C(3)U，所以，進(jìn)入活結(jié)點(diǎn)表即min堆中，而C(2)C(3)，是下一個(gè)E-結(jié)點(diǎn)，生成兒子、，C(4)=-38，u(4)=-32，C(5)= -(10+12+7/918)=-36，u(5)=-(10+12)=-22，對(duì)于、 第39頁(yè)/共48頁(yè)圖8.6 0/1背包問題的一個(gè)實(shí)例的分枝-限界檢索-38-32-32-22-38-32-38-32-38-32-38-38-36-22-38-38-20-20上面的樹=下面的樹=u第40頁(yè)/共48頁(yè)C(4)=-38U=-32+，進(jìn)入min堆，不是解結(jié)點(diǎn)，u(4) +=-

40、32+=U，不修改U值，C(5) U，入min堆，u(5) +=-22+U，不修改U值，這時(shí)min堆中的元素為、，堆頂元是，成為下一個(gè)E-結(jié)點(diǎn)，生成兒子、 ， C(6)=-38，u(6)=-32，C(7)= -(10+10+18)=-38，u(7)=-38，C(6) U，入min堆，u(6) +=-32+=U，不修改U值，C(7) U，入min堆，u(7) +=-38+U，修改U=-38+，因?yàn)镃(6) =C(7)=-38，、都可能是堆頂元，假定堆頂元是，生成兒子、，C(8)=-38，u(8)=-38，C(8) U，入min堆。因?yàn)槭谴鸢附Y(jié)點(diǎn)，并且cost(8)= C(8)=-38U=-38+，修改U=-38，ans=8,而C(9)=-20U=38，被殺死?，F(xiàn)在堆頂元是或，無(wú)論試圖把或變成E-結(jié)點(diǎn)，都因C(E-結(jié)點(diǎn))U，被殺死，隨后，、也因C值大于U被殺死，此時(shí)堆空，因?yàn)閍ns=80，打印出U=-38和路徑、，算法結(jié)束。由于狀態(tài)空間樹中的結(jié)點(diǎn)只反映了檢索的狀態(tài)，并不能明確地給出最優(yōu)的裝包方案，即，使的xi的取值情況。因此，可以對(duì)每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)信息段tag，由答案結(jié)點(diǎn)到根結(jié)點(diǎn)的tag值給出了xi 的值。tag(2)=tag(4)=tag(6)=tag(8)=1，tag(3)=tag(5)=tag(7)=tag(9)=0, 路徑、，、的tag值是1，0，