算法分析與設計分枝限界法

1、第七章 分枝-限界法1上章知識回顧問題狀態(tài)解狀態(tài)狀態(tài)空間答案狀態(tài)狀態(tài)空間樹活結(jié)點E-結(jié)點死結(jié)點通過對n-皇后問題的分析，復習以上概念和回溯法2n-皇后問題描述將n個皇后放置在一個nn的棋盤上，要求沒有兩個皇后可以互相攻擊。攻擊的定義：兩個皇后出現(xiàn)在同一行、或同一列、或者同一條斜線上都視為出現(xiàn)了攻擊。38-皇后問題的一個解1234567812345678該解的8元組表示:(4,6,8,2,7,1,3,5) 4n-皇后問題用n-元組(x1,x2,xn)表示棋盤上皇后的位置狀態(tài)下標表示皇后i (i=1,2,n)xi表示放置皇后i所在的列號顯式約束條件：每個xi只從集合Si=1,2,n取值滿足顯式約束

2、的所有元組確定一個可能的解空間 解空間由nn個n-元組組成隱式約束條件沒有兩個xi可以相同，而且沒有兩個皇后可以在同一條斜線上 由前者得，所有解都是n-元組(1,2,n)的置換，因此，解空間縮小為 n！個元組54-皇后問題解空間的樹結(jié)構(gòu)結(jié)點按深度優(yōu)先檢索編號葉子結(jié)點有4！ 24個 6解空間樹結(jié)構(gòu)的術(shù)語樹中每個結(jié)點確定求解問題的一個問題狀態(tài)(problem state)由根結(jié)點到其它結(jié)點的所有路徑確定了這個問題的狀態(tài)空間(state space)解狀態(tài)(solution states)是這樣一些問題狀態(tài)S，對于這些問題狀態(tài)，由根到S的那條路徑確定了這解空間中的一個元組（滿足顯式約束）答案狀態(tài)(s

3、olution states)是這樣一些解狀態(tài)S，由根到S的路徑確定了問題的一個解（滿足隱式約束）解空間的樹結(jié)構(gòu)為狀態(tài)空間樹(state space tree)7利用狀態(tài)空間樹解題1 設想狀態(tài)空間樹2 生成問題狀態(tài)3 確定問題狀態(tài)中哪些是解狀態(tài)4 哪些解狀態(tài)是答案狀態(tài)生成問題狀態(tài) 構(gòu)造狀態(tài)空間樹8狀態(tài)空間樹術(shù)語活結(jié)點：自己已經(jīng)生成而其所有的兒子結(jié)點還沒有全部生成的結(jié)點。E-結(jié)點（正在擴展的結(jié)點）：當前正在生成其兒子結(jié)點的活結(jié)點。死結(jié)點：不再進一步擴展或者其兒子結(jié)點已全部生成的生成結(jié)點。9構(gòu)造狀態(tài)空間樹的兩個方法回溯法當前E-結(jié)點R，生成一個新的兒子C，則C就變成一個新的E-結(jié)點，對子樹C完全檢

4、測后，R結(jié)點再次成為E-結(jié)點。分枝-限界方法一個E-結(jié)點一直保持到變成死結(jié)點為止。限界函數(shù)以上兩種方法都使用限界函數(shù)殺死還沒有全部生成其兒子結(jié)點的那些活結(jié)點。104-皇后問題的限界函數(shù)如果(x1, x2, , xi)是到當前E-結(jié)點的路徑，那么具有父-子標記xi+1的所有兒子結(jié)點是一些這樣的結(jié)點，它們使得(x1, x2, , xi+1)表示沒有兩個皇后正在互相攻擊的一種棋盤格局。114-皇后問題回溯法vs狀態(tài)空間樹結(jié)點按深度優(yōu)先檢索編號葉子結(jié)點有4！ 24個 124-皇后問題回溯期間的生成樹13分枝限界法在生成當前E-結(jié)點全部兒子之后再生成其它活結(jié)點的兒子，并且，用限界函數(shù)幫助避免生成不包含答

5、案結(jié)點子樹的狀態(tài)空間FIFO檢索：活結(jié)點表采用隊LIFO檢索：活結(jié)點表采用棧14FIFO分枝限界法例7.1（4-皇后問題）3955154-皇后問題回溯 vs FIFO分枝-限界回溯 Win！16LC-檢索（Least Cost）分枝-限界失敗的原因?qū)ο乱粋€E-結(jié)點的選擇規(guī)則過于死板。如何解決？排序，讓答案結(jié)點排在前面！尋找一種“有智力”的排序函數(shù)C()，該函數(shù)能夠讓答案結(jié)點盡早生成。排序的標準下一個E-結(jié)點應當是生成答案結(jié)點花費成本最小的結(jié)點，因此C()又稱作結(jié)點成本函數(shù)。LC：Least Cost17分枝-限界策略的種類根據(jù)對狀態(tài)空間樹中結(jié)點檢索次序的不同，可將分枝-限界的設計策略分為：FI

6、FO檢索，活結(jié)點采用一張先進先出表LIFO檢索，活結(jié)點采用一張先進后出表LC分枝-限界檢索，活結(jié)點采用一張易于操作的線性表。18LC-檢索（結(jié)點成本的兩個標準）一、在生成一個答案結(jié)點之前，子樹X需要生成的結(jié)點數(shù)。二、在子樹X中離X最近的那個答案結(jié)點到X的路徑長度。以圖7.1為例節(jié)點1、18和34、29和35、30和38的代價分別是4，3，2，1其他2，3，4級上的點代價應分別大于3，2，1生成結(jié)點（12 18 34 5019 24 2930 3231）19LC-檢索（結(jié)點成本函數(shù)）C()定義如果X是答案結(jié)點，則C(X)是由狀態(tài)空間樹的根結(jié)點到X的成本（即花費的代價，可以是級數(shù)、計算復雜度等）。

7、如果X不是答案結(jié)點且子樹X不包含任何答案結(jié)點，則C(X)。如果X不是答案結(jié)點但子樹X包含答案結(jié)點，則C(X)等于子樹X中具有最小成本的答案結(jié)點的成本。20LC-檢索（成本估計函數(shù)）從前面的兩個成本度量標準看， 計算C()的工作量與原問題的解具有相同復雜度。這是因為計算一個結(jié)點的代價通常要檢索包含一個答案結(jié)點的子樹才能確定，而這正是解決此問題所要作的檢索工作，因此要得到精確的成本函數(shù)一般是不現(xiàn)實的。因此需要成本估計函數(shù)g(X)出現(xiàn)的新問題僅利用g(X) 會導致算法偏向縱深檢查，無法有效處理下面這種情況：即g(W)=g(Y)。LC分枝-限界檢索：伴之有限界函數(shù)的LC-檢索22例：15-謎問題134

8、152512761114891013123456789101112131415abc問題描述：在一個分成16格的方形棋盤上，放有15塊編了號碼的牌（見下圖）。對這些牌給定一種初始排列如圖7.2(a)，要求通過一系列的合法移動將這一初始排列轉(zhuǎn)換成圖7.2(b)所示的那樣的目標排列。圖7.2 15-謎的排列圖23例：15-謎問題 圖7.2(a)所示的初始排列有四種可能的移動，可以將編號為2,3,5或6的任何一塊牌移到空格。在作了這次移動之后，可作其他的移動。每移動一次，就產(chǎn)生一種新的排列。這些排列稱為這個謎問題的狀態(tài)。初始排列和目標排列叫做初始狀態(tài)和目標狀態(tài)。若由初始狀態(tài)到某狀態(tài)存在一系列合法的移

9、動，則稱該狀態(tài)可由初始狀態(tài)到達。一種初始狀態(tài)的狀態(tài)空間由所有可從初始狀態(tài)到達的狀態(tài)構(gòu)成。24例：15-謎問題 可以看出棋盤上這些牌有16！種不同的排列，所以這個問題的狀態(tài)空間是相當龐大的。有必要在具體求解問題之前判定目標狀態(tài)是否在這個初始狀態(tài)的狀態(tài)空間中。對此有一個非常簡單的判定方法：我們先給棋盤的方格位置編上116的號碼。位置i 是在圖7.2(b)所示的目標排列中放i 號牌的方格位置，位置16是空格的位置。假設POSITION(i)是編號為i的那塊牌在初始狀態(tài)下的位置號，1 i POSITION(i)的數(shù)目。例如，對于圖7.2(a)所示的狀態(tài)，有LESS (1)=0， LESS (4)=1和

10、LESS (12)=6。在初始狀態(tài)下，如果空格在圖7.2的陰影位置中的某一格處，則令X=1；否則X=0。于是有定理7.1： 當且僅當LESS (i)+X（1 i16)是偶數(shù)時，圖7.2(b)所示的目標狀態(tài)可由此初始狀態(tài)到達?？梢杂枚ɡ?.1來判定目標狀態(tài)是否在初始狀態(tài)的狀態(tài)空間中。若在，就可以著手確定導致目標狀態(tài)的一系列移動。例：15-謎問題26 為了實現(xiàn)這一檢索，可以將此狀態(tài)空間構(gòu)造成一棵樹。在這棵樹中，每一個結(jié)點的兒子表示由狀態(tài)X通過一次合法的移動可到達的狀態(tài)。不難看出，移動牌與移動空格實質(zhì)上是等效的，而且在作實際移動時，因此以后都將父狀態(tài)到子狀態(tài)的一次轉(zhuǎn)換看成是空格的一次合法移動。例：1

11、5-謎問題2715-謎問題(寬度優(yōu)先)2815-謎問題(寬度優(yōu)先前十步)29例：15-謎問題按照FIFO檢索方法不管開始格局如何，總是采取由根開始的那條最左路徑，因而檢索是呆板而盲目的。我們所期望的是：有一個具有一定“智能”的檢索方法。這就需給狀態(tài)空間樹的每個結(jié)點X賦予一定的成本值c(X)，可將由根出發(fā)到最近目標結(jié)點路徑上的每個結(jié)點X賦予這條路徑長度作為他們的成本值。切合實際的做法是： 給出一個便于計算成本估計值的函數(shù)c(X)=f(X)+g(X)，其中f(X)是由根到結(jié)點X的路徑長度30例：15-謎問題g(X)是以X為根的子樹中由X到目標狀態(tài)的一條最短路徑長度的估計值。因此，g(X)至少應是能

12、把狀態(tài)X轉(zhuǎn)換成目標狀態(tài)所需的最小移動數(shù)。一種可能的選擇是：g(X)=不在其目標位置的非空白牌數(shù)目使用c(X)圖7.3(a)的LC-檢索將結(jié)點1作為E-結(jié)點的開始。結(jié)點1在生成它的兒子結(jié)點2,3,4和5之后死去。變成E-結(jié)點的下一個結(jié)點是具有最小c(X)的活結(jié)點。3115-謎問題（使用C (X)的LC-檢索）555355332例：15-謎問題c(2)=1+4， c(3)=1+4， c(4)=1+2， c(5)=1+4，所以結(jié)點4成為E-結(jié)點。生成結(jié)點4的兒子結(jié)點，此時的活結(jié)點是2,3,5,10,11,12。c(10)=2+1， c(11)=2+3， c(12)=2+3，具有最小c值的活結(jié)點10成

13、為下一個E-結(jié)點。接著生成結(jié)點22和23，結(jié)點23被判定是目標結(jié)點，此次檢索結(jié)束。33分支限界法的基本思想分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。在搜索問題的解空間樹時，分支限界法與回溯法對當前擴展結(jié)點所使用的擴展方式不同。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點。活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。34分支限界法的基本思想在這些兒子結(jié)點中，那些導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入到活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所求的解或活結(jié)點表為

14、空時為止。35LC-檢索的抽象化控制設T是一棵狀態(tài)空間樹，C(.)是T中結(jié)點的成本函數(shù)。如果，C(X)是其根為X的子樹中任一答案結(jié)點的最小成本，則C(T)是T中最小成本答案結(jié)點的成本。由于函數(shù)C(.)不容易實現(xiàn)，所以使用一個對C(.)估值的啟發(fā)性函數(shù)C(.)來代替。這個啟發(fā)函數(shù)應易于計算并具有如下性質(zhì)：如果X是一個答案結(jié)點或者是一個葉結(jié)點，則C(X)= C(X)。36算法7.1 LC-檢索Procedure LC(T,c)if T是答案結(jié)點 then 輸出T; return end ifET / E-結(jié)點 /將活結(jié)點表初始化為空loopfor E 的每個兒子X doif X是答案結(jié)點 then

15、 輸出從X到T的那條路徑return; end ifcall ADD(X) / X是新的活結(jié)點 /PARENT(X)E repeatif 不在有活結(jié)點 then print(no answer node)stop; end ifcall LEAST(E)repeatEnd LC將一個活結(jié)點加入到隊列中找一個具有最小C值的活結(jié)點并從活結(jié)點表中刪除這個結(jié)點保存結(jié)點X的父結(jié)點E通常把這個活結(jié)點表作成一個min-堆37LC-檢索說明只有當有限狀態(tài)空間樹下才能保證LC終止。對于無限狀態(tài)空間樹，在其至少有一個答案結(jié)點并假定對成本估計函數(shù)C能作出“適當”的選擇時，才能保證算法LC終止。實際上LC算法與狀態(tài)空

16、間樹的寬度優(yōu)先檢索算法和D-檢索算法基本相同。38LC-檢索的抽象化控制（vs. BFS, D-Search）LC算法與BFS及D-Search基本相同活結(jié)點表采用隊列 vs BFS活節(jié)點表采用棧 vs D-Search不同：活結(jié)點表的構(gòu)造，即下一個E-結(jié)點的選擇規(guī)則不同。39LC-檢索的特性LC是否一定能找到具有最小成本的答案結(jié)點呢？考慮下圖所示的狀態(tài)空間樹，方形葉子結(jié)點是答案結(jié)點。每個結(jié)點有兩個數(shù)，上面的是C的值，下面的是C的值。10020220201041010 40LC-檢索的特性定理7.2 在有限狀態(tài)空間樹T中，對于每一個結(jié)點X，令c(X)是c(X)的估計值且具有以下性質(zhì)：對于每一個

17、結(jié)點Y、Z，當且僅當c(Y)c(Z)時有c(Y)U的所有活結(jié)點X可以被殺死，這是因為由X可以到達的所有答案結(jié)點有UU，所以結(jié)點7被殺死；結(jié)點8是不可行結(jié)點，也被殺死。結(jié)點3成為E-結(jié)點，生成其兒子結(jié)點9和10。 u(9)=8，因此U變成8； C(10)=11U，所以10被殺死。結(jié)點9只有一個兒子且不可行，因此結(jié)點9是最小成本答案結(jié)點，其成本值為8。53上界U的確定在實現(xiàn)分枝限界算法時，每修改一次U，在活結(jié)點隊中那些c(X)U或者在U是已找到的一個成本值情況下有c(X)U的結(jié)點應被殺死。必須識別出這個修改了的U是一個已找到的解的成本還是一個不是解成本的單純上界。這個單純上界U或者是還沒找到一個答

18、案結(jié)點，U由處理一可行結(jié)點時修改而得；或者是雖然找到一答案結(jié)點，但它的成本值大于它的上界值，說明這答案結(jié)點的子孫中還有成本更小的答案結(jié)點，U取這個上界值。算法實現(xiàn)時，可引進一個很小的正常數(shù)來進行這一識別。此要取得足夠小，使得對于任意兩個可行結(jié)點X和Y，如果u(X)u(Y),則u(X)u(X)+ u(Y)。當U是由一答案結(jié)點的成本值而得時，U就是這個成本值，而當U是由一單純上界得到時，U等于此上界值u(X)+ 。54找最小成本答案結(jié)點的FIFO分枝-限界方法如何處理c(X) = U的情況為什么要處理？如何處理？引進，當u(X) u(Y)時， u(X) u(X) + u(Y)。在算法中，比較c(X

19、) 與U的時候，可以對U作以下處理：當U是成本值，則不變當U由一單純上界得出，U= u(X) + 55找最小成本答案結(jié)點的FIFO分枝-限界算法procedure FIFOBB(T,c,u,cost)/為找出最小成本結(jié)點檢索T。假定T至少包含一個解結(jié)點且c(X)c(X)u(X)E=T; PARENT(E)=0if T是解結(jié)點 then U=min(cost(T),u(T)+); ans=T else U=u(T)+; ans=0endif將隊置初值為空loop for E的每個兒子X do if c(X)U then call ADD(X); PARENT(X)=E case :X是解結(jié)點 a

20、nd cost(X)U: U=min(cost(X),u(X)+); ans=X :u(X)+U: U=u(X)+ endcase endif repeat loop /得到下一個E-結(jié)點/ if 隊為空 then print(least cost=,U) then print(least cost=,U) while ans0 do print(ans); ans=PARENT(ans) repeat return endif call DELETEQ(X) if c(X)U then exit repeatrepeatend LCBB56找最小成本結(jié)點的LC分枝限界算法procedure

21、LCBB(T,c,u,cost)/為找出最小成本結(jié)點檢索T。假定T至少包含一個解結(jié)點且c(X)c(X)u(X)E=T; PARENT(E)=0if T是解結(jié)點 then U=min(cost(T),u(T)+); ans=T else U=u(T)+; ans=0endif將活結(jié)點表初始化為空loop for E的每個兒子X do if c(X)U then call ADD(X) PARENT(X)=E case :X是解結(jié)點 and cost(X)U: U=min(cost(X),u(X)+) ans=X :u(X)+U: U=u(X)+ endcase endif repeat if 不

22、再有活結(jié)點 or 下一個E結(jié)點有cU then print(least cost=,U) while ans0 do print(ans) ans=PARENT(ans) repeat return endif call LEAST(E)repeatend LCBB57效率分析上下界函數(shù)的選擇是決定分枝-限界算法效率的主要因素。對U選擇一個更好的初值是否能減少生成的結(jié)點數(shù)？ （否，根據(jù)定理7.4）擴展一些C(.)U的結(jié)點是否能減少所生成的結(jié)點數(shù)？ （否，根據(jù)定理7.5）假定有兩個成本估計函數(shù)C1(.)和C2(.)，對于狀態(tài)空間樹的每一個結(jié)點X，若有C1(X) C2(X) C(X)，則稱C2(.

23、)比C1(.)好。是否用較好的成本估計函數(shù)C2(.)比用C1(.)生成的結(jié)點數(shù)要少呢？ （否，根據(jù)定理7.6和定理7.7 ）58定理7.4設U1和U2是狀態(tài)空間樹T中最小成本答案結(jié)點的兩個初始上界且U1U的結(jié)點X而減少。60定理7.6在FIFO和LIFO分枝-限界算法中使用一個更好的成本估計函數(shù)C(.)不會增加其生成的結(jié)點數(shù)。61定理7.7在LC分枝-限界算法中使用一個更好的成本估計函數(shù)C(.)可能增加所生成的結(jié)點的個數(shù)。62定理7.7的證明13276333361334 4 495864 如上圖，所有葉子結(jié)點都是答案結(jié)點，葉結(jié)點下面的數(shù)是其成本值，從這些值中可以得出C(1)=C(3)=3，C(

24、2)=4。結(jié)點1 ， 2和3外面的數(shù)是對應的C1、C2（上、下）值顯然C2是比C1更好的成本估計函數(shù)。如果使用C2，由于C2(2)=C2(3)，因此結(jié)點2會在結(jié)點3之前變成E-結(jié)點,于是所有9個結(jié)點都將被生成，而使用C1將不會生成結(jié)點4，5和6。637.2 0/1背包問題用函數(shù)-pixi來代替目標函數(shù)pixi，從而將背包問題由一個極大問題轉(zhuǎn)換成一個極小化問題。本節(jié)只計論在大小固定的元組表示下如何求解0/1背包問題。狀態(tài)空間樹中那些pixiM(1 i n)的裝包方案的每一個葉結(jié)點是答案結(jié)點，其它的葉結(jié)點均不可行。64上界函數(shù)算法7.5 背包問題的上界函數(shù)u(.)Procedure UBOUND(

25、p,w,k,M)global W(1:n),P(1:n);integer i,k,nb=p;c=wfor i=k+1 to n do if c+w(i) M then c=c+W(i); b=b-P(i) endifrepeatreturn(b)end UBOUND65估價函數(shù)C(X)的定義令C(X)=-BOUND，其中BOUND函數(shù)是算法6.11（見教材P210）。顯然有C(x) C(X) u(X)。667.2.1 LC分枝-限界求解例7.2 LCBB考慮背包問題：n=4(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)M=156713275

26、-38-32-32-224968-38-32-38-32-38-32-36-22-38-38-38-38-20-20上面的數(shù)=C下面的數(shù)=u例7.2 LCBB考慮背包問題：n=4(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)M=1568例7.2 LCBB在找到答案結(jié)點8的情況下，無論哪一個結(jié)點變成下一個E-結(jié)點都要有C(E) U，因此，終止檢索，這時打印出值-38和路徑8,7,4,2,1，算法結(jié)束。要指出的是，由路徑8,7,4,2,1并不能得出由哪些物品裝入背包才得到-pixi=U，即看不出這些Xi的取值情況。因此在實現(xiàn)過程LCBB時應保留

27、一些能反映Xi取值情況的附加信息。69例7.2 LCBB一種解決辦法是每一個結(jié)點增設一個位信息段TAG。若該結(jié)點為左孩子，則TAG(X)=1；若該結(jié)點為右孩子，則TAG(X)=0。于是，對此問題將有： TAG(2)=TAG(4)=TAG(6)=TAG(8)=1； TAG(3)=TAG(5)=TAG(7)=TAG(9)=0。70LCBB求解背包問題分析狀態(tài)空間樹中結(jié)點的結(jié)構(gòu)如何生成一給定結(jié)點的兒子如何識別答案結(jié)點如何表示活結(jié)點表71狀態(tài)空間樹中結(jié)點的結(jié)構(gòu)PARENT父結(jié)點鏈接指針LEVEL狀態(tài)空間樹中的級數(shù)TAGXi的取值CU背包的剩余空間PE已裝入物品的效益值的和UBc(X)72如何生成一給定

28、結(jié)點的兒子左兒子生成PARENT(Y) = XLEVEL(Y) = LEVEL(X) + 1CU(Y) = CU(X) WLEVEL(X)PE(Y) = PE(X) + P LEVEL(X)TAG = 1UB(Y) = UB(X)73如何識別答案結(jié)點當且僅當LEVEL(X) = n 1X是答案結(jié)點74如何表示活結(jié)點表Min-堆測試活結(jié)點表是否為空常量時間加結(jié)點到活結(jié)點表 log(n)刪除最小UB值的結(jié)點 log(n)75計算上界和下界的算法line procedure LUBOUND(P, W, rw, cp, N, k, LBB, UBB)1 LBB cp; c rw;2 for i k t

29、o N do 3 if c=W(j) then c c-W(j) 6 LBB LBB+P(j)7 endif8 repeat9 return10 endif11 c c-W(i); LBB LBB+P(i)12 repeat13 UBB LBB14 end LUBOUND76生成一個新結(jié)點line procedure NEWNODE(par, lev, t, cap, prof, ub)1 call GETNODE(I)2 PARENT(I) par； LEVEL(i) lev；TAG(I) t3 CU(I) cap；PE(I) prof；UB(I) ub4 call ADD(I)5 end

30、NEWNODE77背包問題的LC分枝-限界算法line procedure LCKNAP(P, W, M, N, )/ 大小固定元組表示狀態(tài)空間樹/ 假設P(1)/W(1)=P(2)/W(2)=P(N)/W(N) real P(N), W(N), M, L, LBB, UBB, cap, prof int ANS, X, N1 call INIT2 call GETNODE(E) 3 PARENT(E) 0; LEVEL(e) 1; CU(E) M; PE(E) 04 call LUBOUND(P, W, M, N, 0, 1, LBB, UBB)5 L LBB - ; UB(E) UBB 6

31、 loop7 i LEVEL(E); cap CU(E); prof PE(E)78背包問題的LC分枝-限界算法8 case9 :i=N+1:10 if profL then L prof; ANS E11 endif12 :else: 13 if cap=W(i) then14 call NEWNODE(E,i+1,1,cap-W(i), prof+P(1)UB(E)15 endif16 call LUBOUND(P,W,cap,prof,N,i+1, LBB,UBB)17 if UBBL then18 call NEWNODE(E,i+1,0,cap,prof,UBB)19 L max(L

32、,LBB- )20 endif21 endcase79背包問題的LC分枝-限界算法22 if 不再有活結(jié)點 then exit endif23 call LARGEST(E)24 until UB(E)=P(2)/W(2)=P(N)/W(N) real P(N), W(N), M, L, LBB, UBB, E, cap, prof int ANS, X, N1 call INIT; i 12 call LUBOUND(P,W,M,0,N,1,L,UBB) 3 call NNODE(0,0,M,0,UBB)4 call ADDQ(#)5 while i=L:11 cap CU(E); prof

33、 PE(E)12 if cap=W(i) then13 call NNODE(E,1,cap-W(i), prof+P(i),UB(E)14 endif15 call LUBOUND(P,W,cap,prof,N,i+1, LBB,UBB)16 if UBB=L then17 call NNODE(E,0,cap,prof,UBB)18 L max(L,LBB)19 endif20 endcase21 repeat22 call ADDQ(#)23 i i + 124 repeat25 ANS PE(X)=L的活結(jié)點X26 call FINISH(L,ANS,N)27 end FIFOKNAP

34、847.3 貨郎擔問題問題描述：某售貨員要到若干個村莊售貨，各村莊之間的路程是己知的，為了提高效率，售貨員決定從所在商店出發(fā)，到每個村莊售一次貨然后返回商店，問他應選擇一條什么路線才能使所走的總路程最短?設G(V,E)是一個具有邊成本cij的有向圖。G的一條周游路線是包含V中每個結(jié)點的一個有向環(huán)。周游路線的成本是此路線上所有邊的成本之和，貨郎擔問題(traveling salesperson problem)是求取具有最小成本的周游路線問題。85貨郎擔問題的狀態(tài)空間樹12345769812111016151413n=4，i0=i4=1的貨郎擔問題的狀態(tài)空間樹i1=2i1=3i1=4i2=3i2

35、=4i2=2i2=4i2=2i2=3i3=4i3=3i3=4i3=2i3=3i3=286用LC分枝-限界法檢索貨郎擔問題的狀態(tài)空間樹成本函數(shù)C(.)的定義：（1）若X是葉結(jié)點，則C(X)為由根到X的路徑確定的周游路線成本。（2）若X不是葉結(jié)點，子樹X中最小成本葉結(jié)點的成本。87歸約矩陣如果矩陣的一行（列）至少包含一個零且其余無素均非負，則此行（列）稱為已歸約行（列）。所有行和列均已歸約行和列的矩陣稱為歸約矩陣?？梢酝ㄟ^對一行（列）中每個元素都減去同一個常數(shù)t（稱為約數(shù)）將該行（列）變?yōu)橐褮w約行（列）。逐行逐列施行歸約就可得到原矩陣的歸約矩陣。88矩陣約數(shù)假設第i行的約數(shù)ti，第j列的約數(shù)為rj，那么各行、列的約數(shù)之和L=ti+ ri，其中1i,j n. 20 30 10 1115 16 4 2 3 5 2 419 6 18 316 4 7 16 10 17 0 112 11 2 0 0 3 0 215 3 12 011 0 0 12 C=C=在上例中，C的歸約成本矩陣C，矩陣約數(shù)L=2589估計函數(shù)C(.)