計算機(jī)算法設(shè)計與分析 第九章分枝-限界法

9.1一般方法9.1.1LC-檢索9.1.215謎問題9.1.3LC-檢索的抽象化控制9.1.4LC-檢索的特性9.1.5分枝-限界算法第九章分枝-限界法1分枝-限界法:

是在生成當(dāng)前E-結(jié)點(diǎn)全部兒子之后,再生成其他活結(jié)點(diǎn)的兒子,并且使用限界函數(shù)幫助避免生成不包含答案結(jié)點(diǎn)子樹的狀態(tài)空間的檢索方法根據(jù)對狀態(tài)空間樹中結(jié)點(diǎn)檢索次序的不同，可將分枝-限界的設(shè)計策略分為兩種:FIFO檢索(FirstInFirstOut)

活結(jié)點(diǎn)表采用先進(jìn)先出表(即隊列)LIFO檢索(LastInFirstOut)

活結(jié)點(diǎn)表采用后進(jìn)先出表(即棧)9.1一般方法2例:4-皇后問題:用FIFO檢索生成解空間樹的過程

起初只有一個活結(jié)點(diǎn),即結(jié)點(diǎn)1,這表示沒有皇后被放在棋盤上。1

擴(kuò)展結(jié)點(diǎn)1,生成兒子結(jié)點(diǎn)2,18,34和50。這些結(jié)點(diǎn)分別表示皇后1在第1行的1,2,3,4列情況下的棋盤。3813234現(xiàn)在活結(jié)點(diǎn)是2,18,34和50下一個E-結(jié)點(diǎn)是結(jié)點(diǎn)2,擴(kuò)展結(jié)點(diǎn)2,生成結(jié)點(diǎn)3,8和13。利用限界函數(shù),結(jié)點(diǎn)3立即被殺死,將結(jié)點(diǎn)8和13加到活結(jié)點(diǎn)隊列21834503421kill3192429134124354045

結(jié)點(diǎn)18變成E-結(jié)點(diǎn),生成結(jié)點(diǎn)19,24和29,限界函數(shù)殺死結(jié)點(diǎn)19和24,結(jié)點(diǎn)29被加到活結(jié)點(diǎn)隊列中。123515661killkill3813234kill121834503421killkillkill

結(jié)點(diǎn)34變成E-結(jié)點(diǎn),生成結(jié)點(diǎn)35,40和45,限界函數(shù)殺死結(jié)點(diǎn)40和45,結(jié)點(diǎn)35被加到活結(jié)點(diǎn)隊列中。

結(jié)點(diǎn)50變成E-結(jié)點(diǎn),生成結(jié)點(diǎn)51,56和61,限界函數(shù)殺死結(jié)點(diǎn)61,結(jié)點(diǎn)51和56被加到活結(jié)點(diǎn)隊列中。411942161432323031383642192429134killkill8132343kill121834503421124354045killkill123515661kill545232595731killkillkillkillkillkillkillkill153313392552kill5631x4=318x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill19x2=124x2=3killkill29x2=430x3=1回溯法生成的解空間樹對于4-皇后問題,比較回溯法和分枝-限界法的解空間樹,很明顯回溯法占優(yōu)勢79.1.1LC-檢索分枝-限界法中存在的問題:對下一個E-結(jié)點(diǎn)的選擇規(guī)則相當(dāng)死板,這種選擇對于有可能快速檢索到一個答案的結(jié)點(diǎn)沒有給出任何的優(yōu)先權(quán)。改進(jìn)方法:對活結(jié)點(diǎn)使用一個“有智力”排序函數(shù)c(.)來選取下一個E-結(jié)點(diǎn),這樣通常可以更快地到達(dá)一個答案結(jié)點(diǎn)。對可能導(dǎo)致答案的活結(jié)點(diǎn)賦以優(yōu)先權(quán),需要增加額外的計算工作(即需要付出相應(yīng)的代價)對任一結(jié)點(diǎn)X,要付出的代價可使用兩種標(biāo)準(zhǔn)來度量:在生成一個答案結(jié)點(diǎn)之前,子樹X需要生成的結(jié)點(diǎn)數(shù)在子樹X中離X最近的那個答案結(jié)點(diǎn)到X的路徑長度8使用第2種度量,圖中樹的根結(jié)點(diǎn)的代價是4;結(jié)點(diǎn)18和34的代價是3;結(jié)點(diǎn)29和35的代價是2;結(jié)點(diǎn)30和38的代價是1。在2,3和4級上的其他結(jié)點(diǎn)的代價應(yīng)分別大于3,2和1以這些代價作為選擇下一個E-結(jié)點(diǎn)的依據(jù),則E-結(jié)點(diǎn)依次為1,18,29和3011942161432323031383642192429134killkill8132343kill121834503421124354045killkill123515661kill545232595731killkillkillkillkillkillkillkill153313kill39答案答案2255kill9結(jié)論:使用度量1,對于每一種分枝-限界算法,總是生成最小數(shù)目的結(jié)點(diǎn)。使用度量2,要成為E-結(jié)點(diǎn)的結(jié)點(diǎn)只是由根到最近的那個答案結(jié)點(diǎn)路徑上的那些結(jié)點(diǎn)?！坝兄橇Φ摹迸判蚝瘮?shù)C(.)又稱為結(jié)點(diǎn)成本函數(shù)C(.)函數(shù)定義如下:

如果X是答案結(jié)點(diǎn),則C(X)是由狀態(tài)空間樹的根結(jié)點(diǎn)到X的成本(如路徑長度);如果X不是答案結(jié)點(diǎn)且子樹X不包含任何答案結(jié)點(diǎn),則C(X)=∞;否則C(X)等于子樹X中具有最小成本的答案結(jié)點(diǎn)的成本。注:要得到結(jié)點(diǎn)成本函數(shù)C(.)所用的計算工作量與解原問題具有相同的復(fù)雜度,所以要得到精確的成本函數(shù)一般是不現(xiàn)實(shí)的10在算法中檢測活結(jié)點(diǎn)的次序通?？梢愿鶕?jù)能大致估計結(jié)點(diǎn)成本的函數(shù)g(.)來排列。^為了不使算法過分偏向作縱深檢查,需要改進(jìn)成本估計函數(shù)單純使用函數(shù)g(.)并不合適,它會導(dǎo)致算法偏向于作縱深檢查?！驹较蛳略娇赡芙咏鸢腹?jié)點(diǎn)】^如果g(X)就是C(X),這種縱深檢索正是所希望的,因?yàn)檫@樣可以用最小成本到達(dá)離根最近的答案結(jié)點(diǎn),其它子樹的結(jié)點(diǎn)無需生成。^但是g(X)僅是精確成本的估計值,因此偏向于縱深檢查可能導(dǎo)致不能很快找到更接近根的答案結(jié)點(diǎn)。^11改進(jìn)的成本估計函數(shù):不僅考慮X到一個答案結(jié)點(diǎn)的估計成本值,還考慮了由根結(jié)點(diǎn)到X的成本(路徑長)h(X)用c(.)來表示新的成本估計函數(shù)^c(X)=f(h(X))+g(X)^^要求函數(shù)f(.)是一個非降函數(shù),用f(.)不等于0可以減少算法作偏向于縱深檢查的可能性^用成本估計函數(shù)c(X)選擇下一個E-結(jié)點(diǎn)的檢索策略總是選取c(.)值最小的活結(jié)點(diǎn)作為下一個E-結(jié)點(diǎn)。^這種檢索策略稱為最小成本檢索,簡稱LC-檢索。伴之有限界函數(shù)的LC-檢索稱為LC分枝-限界檢索129.1.215謎問題134152512761114891013123456789101112131415圖a圖b問題描述:在一個分成16格的方形棋盤上,放有15塊編了號碼的牌。對這些牌給定一種初始排列,如圖a,要求通過一系列的合法移動將初始排列轉(zhuǎn)換成圖b所示那樣的目標(biāo)排列。13134152512761114891013圖a所示的初始排列有四種可能的移動,可以將編號為2,3,5或6的任何一塊牌移到空格。在作了這次移動之后,可作其他的移動。每移動一次，就產(chǎn)生一種新的排列。這些排列稱為這個15謎問題的狀態(tài)。初始排列和目標(biāo)排列叫做初始狀態(tài)和目標(biāo)狀態(tài)。若由初始狀態(tài)到某狀態(tài)存在一系列合法的移動,則稱該狀態(tài)可由初始狀態(tài)到達(dá)。一種初始狀態(tài)的狀態(tài)空間由所有可從初始狀態(tài)到達(dá)的狀態(tài)構(gòu)成。圖a14在求解問題之前應(yīng)判定目標(biāo)狀態(tài)是否在這個初始狀態(tài)的狀態(tài)空間中。一個簡單的判定方法:先給棋盤的方格位置編上1~16的號碼。位置i是在圖b所示的目標(biāo)排列中放i號牌的方格位置,位置16是空格的位置。假設(shè)POSITION(i)是編號為i的那塊牌在初始狀態(tài)下的位置號,1≤i<16;POSITION(16)表示空格的位置。12345678910111213141516134152512761114891013圖a圖bPOSITION(1)=1POSITION(2)=5POSITION(3)=2POSITION(16)=615對于任意一種狀態(tài),設(shè)LESS(i)是使牌j<牌i,且使POSITION(j)>POSITION(i)的數(shù)目。134152512761114891013圖a圖c在初始狀態(tài)下,如果空格在圖c的陰影位置中的某一格處,則令X=1;否則X=0。例如:對于圖a所示的狀態(tài)LESS(1)=0,LESS(2)=0,LESS(3)=1LESS(4)=1,LESS(12)=6定理9.1:

當(dāng)且僅當(dāng)∑LESS(i)+X(1≤i≤16)是偶數(shù)時,圖b所示的目標(biāo)狀態(tài)可由此初始狀態(tài)到達(dá)。例如圖a,算出∑LESS(i)+X=37+0=37,因此由圖a的初始狀態(tài)不能到達(dá)圖b的目標(biāo)狀態(tài)16定理9.1用來判定目標(biāo)狀態(tài)是否在初始狀態(tài)的狀態(tài)空間中。若在就可以開始確定導(dǎo)致目標(biāo)狀態(tài)的一系列移動。為實(shí)現(xiàn)這一檢索,可以將此狀態(tài)空間構(gòu)造成一棵樹。在這棵樹中,每一個結(jié)點(diǎn)的兒子表示由狀態(tài)X通過一次合法的移動可到達(dá)的狀態(tài)。移動牌與移動空格實(shí)質(zhì)上是等效的,而且在作實(shí)際移動時移動空格更為直觀,因此將父狀態(tài)到子狀態(tài)的一次轉(zhuǎn)換看成是空格的一次合法移動。1715-謎問題一個實(shí)例的狀態(tài)空間樹該樹已做部分修剪,如果結(jié)點(diǎn)P的兒子中有和P的父親的狀態(tài)相同的就將該枝剪去123456891071113141512124563891071113141512123456891071113141512123456789101113141512123456891071113141512123456789101113141512123456789101511131412123456789101113141512123456791011813141512123456789101112131415………上右下左右下左上下目標(biāo)狀態(tài)按照FIFO檢索方法不管開始格局如何,總是采取由根開始的那條最左路徑因而檢索是呆板而盲目的1819我們期望的是有一種能按不同具體實(shí)例作出不同處理的有一定“智能”的檢索方法。這就需給狀態(tài)空間樹的每個結(jié)點(diǎn)X賦予一定的成本c(X),如果具體實(shí)例有解,則將由根出發(fā)到最近目標(biāo)結(jié)點(diǎn)路徑上的每個結(jié)點(diǎn)賦予這條路徑長度作為它們的成本。在上例的狀態(tài)空間樹中,由根結(jié)點(diǎn)1到目標(biāo)結(jié)點(diǎn)23的路徑長度為3,因此有c(1)=c(4)=c(10)=c(23)=3,而樹中、的其他結(jié)點(diǎn)的成本均賦為∞,如果能做到這一點(diǎn),寬度優(yōu)先檢索將很有效,但這是一種很不實(shí)際的策略,因?yàn)橄胍玫侥菢拥某杀竞瘮?shù)c(.)是不可能的20實(shí)際的做法是:給出一個便于計算成本估計值的函數(shù)c(X)=f(X)+g(X),

其中f(X)是由根到結(jié)點(diǎn)X的路徑長度,g(X)是以X為根的子樹中由X到目標(biāo)狀態(tài)的一條最短路徑長度的估計值。^^^g(X)是能把狀態(tài)X轉(zhuǎn)換成目標(biāo)狀態(tài)所需的最小移動數(shù)。一種選擇是:g(X)=不在其目標(biāo)位置的非空白牌數(shù)目^^為達(dá)到目標(biāo)狀態(tài)所需要的移動數(shù)可能大于g(x),對于右圖,只有7號牌不在目標(biāo)位置上,所以有g(shù)(x)=1,很明顯為到達(dá)目標(biāo)狀態(tài)所需的移動次數(shù)比g(x)大得多,因此c(x)是c(x)的下界^^^^12345689101112131415721使用c(X))的LC-檢索將結(jié)點(diǎn)1作為E-結(jié)點(diǎn)的開始,結(jié)點(diǎn)1在生成它的兒子結(jié)點(diǎn)2,3,4和5之后死去。變成E-結(jié)點(diǎn)的下一個結(jié)點(diǎn)是具有最小c(X)的活結(jié)點(diǎn)。^^c(2)=1+4=5,c(3)=1+4=5c(4)=1+2=3,c(5)=1+4=5^^^^結(jié)點(diǎn)4成為E-結(jié)點(diǎn),結(jié)點(diǎn)4生成兒子結(jié)點(diǎn),此時的活結(jié)點(diǎn)是2,3,5,10,11,121215141311710986543211上右下左1215141311710983654212121514131171098654321312151413111098765432141215141311710986543215右下左121514131110987654321101214131115109876543211112151413111098765432112c(10)=2+1=3c(11)=2+3=5c(12)=2+3=5^^^具有最小值的活結(jié)點(diǎn)10成為下一個E-結(jié)點(diǎn)22活結(jié)點(diǎn)10生成結(jié)點(diǎn)22和23,結(jié)點(diǎn)23被判定是目標(biāo)結(jié)點(diǎn),此次檢索結(jié)束目標(biāo)狀態(tài)上12151413811109765432122下151413121110987654321231215141311710986543211上右下左1215141311710983654212121514131171098654321312151413111098765432141215141311710986543215右下左12151413111098765432110121413111510987654321111215141311109876543211223分枝-限界法的基本思想分枝-限界法常以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問題的解空間樹。在搜索問題的解空間樹時,在分支限界法中,每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(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)表中。此后從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn),并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程,這個過程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時為止。249.1.3

LC-檢索的抽象化控制設(shè)T是一棵狀態(tài)空間樹,c(.)是T中結(jié)點(diǎn)的成本函數(shù)。如果c(X)是其根為X的子樹中任一答案結(jié)點(diǎn)的最小成本,則c(T)是T中最小成本答案結(jié)點(diǎn)的成本。^如前所述,函數(shù)c(.)不容易實(shí)現(xiàn),所以使用一個對c(.)估值的啟發(fā)性函數(shù)c(.)來代替這個啟發(fā)函數(shù)應(yīng)易于計算并具有如下性質(zhì):如果X是一個答案結(jié)點(diǎn)或者是一個葉結(jié)點(diǎn),則c(X)=c(X)^25procedureLC(T,c)ifT是答案結(jié)點(diǎn)then{輸出T;return;}E=T;活結(jié)點(diǎn)表初始化為空;loop{forE結(jié)點(diǎn)的每個兒子結(jié)點(diǎn)Xdo {ifX是答案結(jié)點(diǎn)then{輸出從X到T的那條路徑;return;}

callADD(X);

PARENT(X)=E;}if不再有活結(jié)點(diǎn)then{print(“noanswernode”);stop;}

callLEAST(E);}endLC^//使結(jié)點(diǎn)T成為E-結(jié)點(diǎn)//LC用函數(shù)c(.)去尋找一個答案結(jié)點(diǎn)//將新的活結(jié)點(diǎn)X添加到活結(jié)點(diǎn)表中//用來找一個具有最小成本值的活結(jié)點(diǎn),并從活結(jié)點(diǎn)表中刪除該結(jié)點(diǎn),然后將此結(jié)點(diǎn)放在變量X中返回//用信息段PARENT保存X的父結(jié)點(diǎn)E26LC算法正確性證明有限狀態(tài)空間樹算法過程同LC檢索定義相吻合無限狀態(tài)空間樹若不加限定，則可能陷入無限深度中如果X的級數(shù)大于Y的級數(shù)達(dá)到一定程度，則?(X)>?(Y),阻止進(jìn)一步下陷沒有答案的無限狀態(tài)空間樹，LC不停機(jī)可以規(guī)定殺死成本大于一個限界的活節(jié)點(diǎn)，保證停機(jī)LEAST按隊列：FIFO,寬度優(yōu)先檢索LEAST按棧：LIFO,D-檢索279.1.4

LC-檢索的特性

在許多應(yīng)用中希望在所有答案結(jié)點(diǎn)中找到一個最小成本的結(jié)點(diǎn),LC檢索是否一定能找到具有最小成本的答案結(jié)點(diǎn)呢？^考慮下圖所示的狀態(tài)空間樹,方結(jié)點(diǎn)是答案結(jié)點(diǎn)。每個結(jié)點(diǎn)有兩個數(shù),上面的是c的值,下面的是c的值132654710020220201041010∞∞∞∞LC算法先生成根結(jié)點(diǎn)的兒子結(jié)點(diǎn)2和3,因c(2)=2,所以結(jié)點(diǎn)2成為E-結(jié)點(diǎn),它擴(kuò)展出結(jié)點(diǎn)4和5,結(jié)點(diǎn)4就是答案結(jié)點(diǎn),其成本為20,但成本最小的答案結(jié)點(diǎn)應(yīng)該是結(jié)點(diǎn)7。^28LC算法沒能找到最小成本答案結(jié)點(diǎn)的原因在于存在這樣兩個結(jié)點(diǎn)X和Y,當(dāng)c(X)>c(Y)時,c(X)<c(Y)^^定理9.2:

在有限狀態(tài)空間樹T中,對于每一個結(jié)點(diǎn)X,令c(X)是c(X)的估計值且具有以下性質(zhì):對于每一個結(jié)點(diǎn)Y、Z,當(dāng)且僅當(dāng)c(Y)<c(Z)時有c(Y)<c(Z),

那么在使c(.)作為c(.)的估計值時,算法LC到達(dá)一個最小的成本答案結(jié)點(diǎn)且終止。^^^^

如果對于每一個結(jié)點(diǎn)X有c(X)≤c(X),且對于答案結(jié)點(diǎn)X有c(X)=c(X),

只要對LC算法稍作修改就可得到一個在達(dá)到某個最小成本答案結(jié)點(diǎn)時終止的檢索算法LC1^^29procedureLC1(T,c)E=T;活結(jié)點(diǎn)表初始化為空;loop{ifE是答案結(jié)點(diǎn)then{輸出從E到T的路徑;return;}forE結(jié)點(diǎn)的每個兒子結(jié)點(diǎn)Xdo {callADD(X);

PARENT(X)=E;}if不再有活結(jié)點(diǎn)then{print(“noanswernode”);stop;}

callLEAST(E);}endLC1^找最小成本答案結(jié)點(diǎn)的LC-檢索將if語句放在for循環(huán)的外面先執(zhí)行,如果滿足條件則結(jié)束loop循環(huán),即結(jié)束算法LC1309.1.5分枝-限界算法

檢索狀態(tài)空間樹的各種分枝-限界算法都是在生成當(dāng)前E-結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)后,再將另一個結(jié)點(diǎn)變?yōu)镋-結(jié)點(diǎn)。之前我們使用一個成本估計函數(shù)c(.)來給出可由任一結(jié)點(diǎn)X得出的解的下界。采用下界函數(shù)使算法具有一定的“智能”,另外還可以通過設(shè)置最小成本的上界使算法進(jìn)一步加速。^如果U是最小成本解的上界,則具有c(X)>U的所有活結(jié)點(diǎn)X可以被殺死,因?yàn)橛蒟可以到達(dá)的所有答案結(jié)點(diǎn)有c(X)≥c(X)>U^^U的初始值可用某種啟發(fā)性方法得到,也可以置為∞,每當(dāng)找到一個新的答案結(jié)點(diǎn)就可以修改U的值。31求解最優(yōu)化問題的分枝限界法只考慮極小化問題成本函數(shù)定義為目標(biāo)函數(shù)【而非達(dá)到答案節(jié)點(diǎn)的代價】成本函數(shù)分三種情況：X為答案，則為目標(biāo)函數(shù)；X為不可行(部分)解，則為；否則為X子樹中最小成本節(jié)點(diǎn)的成本。

?(X)c(X)32實(shí)例:帶限期的作業(yè)排序問題問題描述:假定有n個作業(yè)和一臺處理機(jī),每一個作業(yè)i與一個三元組(pi,di,ti)相聯(lián)系,它要求ti個單位處理時間,如果在期限di內(nèi)作業(yè)沒處理完則要招致pi的罰款。目標(biāo)是從這n個作業(yè)中選取一個子集合J,要求在J中的作業(yè)都能在相應(yīng)的期限內(nèi)完成,并且使不在J中的作業(yè)招致的罰款總額最小。33實(shí)例:n=4;(p1,d1,t1)=(5,1,1);(p2,d2,t2)=(10,3,2);(p3,d3,t3)=(6,2,1);(p4,d4,t4)=(3,1,1);該實(shí)例的解空間由作業(yè)指標(biāo)集{1,2,3,4}的所有可能的子集合組成,使用元組大小可變的表示方法,構(gòu)造一棵解空間樹如下:911710612345x1=1x1=2x1=3x1=4x2=2x2=3x2=4x3=3x2=3x2=4x3=4x3=4x3=4812131415x2=4c=8c=0^c=0^c=0^c=10^c=5^c=5^c=11^c=15^c=15^c=21^樹中方形結(jié)點(diǎn)代表不可行的子集合,所有的圓形結(jié)點(diǎn)都是答案結(jié)點(diǎn)結(jié)點(diǎn)9代表最優(yōu)解,并且是僅有的最小成本答案結(jié)點(diǎn)J={2,3}罰款值為p1+p4=834成本函數(shù)c(.)定義為,對于圓形結(jié)點(diǎn),c(X)是根為X的子樹中結(jié)點(diǎn)的最小罰款;對于方形結(jié)點(diǎn),c(X)=∞911710612345x1=1x1=2x1=3x1=4x2=2x2=3x2=4x3=3x2=3x2=4x3=4x3=4x3=4812131415x2=4c=8c=0^c=0^c=0^c=10^c=5^c=5^c=11^c=15^c=15^c=21^c(2)=min{9,13}=9c(3)=min{8,11}=8c(4)=15,c(5)=21c(1)=min{9,8,15,21}=8定義下界函數(shù)c(.),使c(X)≤c(X)。設(shè)SX是在結(jié)點(diǎn)X對J所選擇的作業(yè)的子集。如果m=max{i|i屬于SX},則c(X)=∑pi,(i<m且iSX),即c(X)等于作業(yè)i小于m,且作業(yè)i不屬于SX的所有罰款累加和。^^^^子樹X中最小成本答案結(jié)點(diǎn)的成本的一個簡單上界u(X)定義為:u(X)=∑pi(i

SX)35開始時U=∞,

結(jié)點(diǎn)1為E-結(jié)點(diǎn),依次生成結(jié)點(diǎn)2,3,4和5作業(yè)排序問題的一個FIFO分枝-限界算法開始時可以將最小成本答案結(jié)點(diǎn)的成本上界取為U=∞或U=∑pi1≤i≤n因?yàn)閏(4)和c(5)大于U,所以結(jié)點(diǎn)4和5被殺死。^^u(2)=p2+p3+p4=19u(3)=p1+p3+p4=14

u(4)=p1+p2+p4=18u(5)=p1+p2+p3=21在生成結(jié)點(diǎn)3時,將上界修改為U=141c=0^2345x1=1x1=2x1=3x1=4c=0^c=5^c=15^c=21^c(1)=0;c(2)=0;c(3)=p1=5;c(4)=p1+p2=15;c(5)=p1+p2+p3=21;^^^^^killkill361c=0^2345x1=1x1=2x1=3x1=4c=0^c=5^c=15^c=21^killkill活節(jié)點(diǎn)（2，3）；結(jié)點(diǎn)2成為E-結(jié)點(diǎn),生成兒子結(jié)點(diǎn)6,7,876x2=2x2=3x2=48c=0^c=10^u(6)=p3+p4=9,u(7)=p2+p4=13,因此U=9;c(6)=0,c(7)=p2=10>U,

結(jié)點(diǎn)7被殺死;結(jié)點(diǎn)8是不可行結(jié)點(diǎn)^^killkillx2=3x2=4c=5^c=11^910活節(jié)點(diǎn)(3);結(jié)點(diǎn)3成為E-結(jié)點(diǎn),生成兒子結(jié)點(diǎn)9和10u(9)=p1+p4=8,u(10)=p1+p3=11,因此U=8;?(9)=p1=5,c(10)=p1+p2=11>U,

所以10被殺死^活節(jié)點(diǎn)(6,3);結(jié)點(diǎn)6成為E-結(jié)點(diǎn),其兒子結(jié)點(diǎn)12和13均不可行活節(jié)點(diǎn)表(9);結(jié)點(diǎn)9成為E-結(jié)點(diǎn),其兒子結(jié)點(diǎn)15,不可行活節(jié)點(diǎn)表空。所以結(jié)點(diǎn)9是最小成本答案結(jié)點(diǎn)（U最?。﹛3=3x3=41213x3=41537因活結(jié)點(diǎn)隊列中符合條件的結(jié)點(diǎn)是隨機(jī)分布的,每修改一次U就在隊列中找出這些結(jié)點(diǎn)并將其殺死是很麻煩的,一種方法是在應(yīng)殺死的結(jié)點(diǎn)要變成E-結(jié)點(diǎn)時才將其殺掉。在實(shí)現(xiàn)FIFO分枝-限界算法時,每修改一次U,在活結(jié)點(diǎn)隊列中那些有?(X)>U的結(jié)點(diǎn),或者在U是已找到的一個成本