尋找問(wèn)題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個(gè)，在檢查完所有或部分候選解后，即可找到所需要的解。理論上，當(dāng)候選解數(shù)量有限并且通過(guò)檢查所有或部分候選解能夠得到所需解時(shí)，上述方法是可行的。不過(guò)，在實(shí)際應(yīng)用中，很少使用這種方法，因?yàn)楹蜻x解的數(shù)量通常都非常大（比如指數(shù)級(jí)，甚至是大數(shù)階乘），即便采用最快的計(jì)算機(jī)也只能解決規(guī)模很小的問(wèn)題。對(duì)候選解進(jìn)行系統(tǒng)檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方法。按照這兩種方法對(duì)候選解進(jìn)行系統(tǒng)檢查通常會(huì)使問(wèn)題的求解時(shí)間大大減少（無(wú)論對(duì)于最壞情形還是對(duì)于一般情形）。事實(shí)上，這些方法可以使我們避免對(duì)很大的候選解集合進(jìn)行檢查，同時(shí)能夠保證算法運(yùn)行結(jié)束時(shí)可以找到所需要的解。因此，這些方法通常能夠用來(lái)求解規(guī)模很大的問(wèn)題。
本章集中闡述回溯方法，這種方法被用來(lái)設(shè)計(jì)貨箱裝船、背包、最大完備子圖、旅行商和電路板排列問(wèn)題的求解算法。
4.1 算法思想
回溯（b a c k t r a c k i n g）是一種系統(tǒng)地搜索問(wèn)題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問(wèn)題定義一個(gè)解空間（ solution space），這個(gè)空間必須至少包含問(wèn)題的一個(gè)解（可能是最優(yōu)的）。在迷宮老鼠問(wèn)題中，我們可以定義一個(gè)包含從入口到出口的所有路徑的解空間；在具有n 個(gè)對(duì)象的0 / 1背包問(wèn)題中（見(jiàn)1 . 4節(jié)和2 . 2節(jié)），解空間的一個(gè)合理選擇是2n 個(gè)長(zhǎng)度為n 的0 / 1向量的集合，這個(gè)集合表示了將0或1分配給x的所有可能方法。當(dāng)n= 3時(shí)，解空間為{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 , 0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 , 1 ) }。
下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖或樹(shù)。圖1 6 - 1用圖的形式給出了一個(gè)3×3迷宮的解空間。從( 1 , 1 )點(diǎn)到( 3 , 3 )點(diǎn)的每一條路徑都定義了3×3迷宮解空間中的一個(gè)元素，但由于障礙的設(shè)置，有些路徑是不可行的。
圖1 6 - 2用樹(shù)形結(jié)構(gòu)給出了含三個(gè)對(duì)象的0 / 1背包問(wèn)題的解空間。從i 層節(jié)點(diǎn)到i+ 1層節(jié)點(diǎn)的一條邊上的數(shù)字給出了向量x 中第i個(gè)分量的值xi ，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑定義了解空間中的一個(gè)元素。從根節(jié)點(diǎn)A到葉節(jié)點(diǎn)H的路徑定義了解x= [ 1 , 1 , 1 ]。根據(jù)w 和c 的值，從根到葉的路徑中的一些解或全部解可能是不可行的。
一旦定義了解空間的組織方法，這個(gè)空間即可按深度優(yōu)先的方法從開(kāi)始節(jié)點(diǎn)進(jìn)行搜索。在迷宮老鼠問(wèn)題中，開(kāi)始節(jié)點(diǎn)為入口節(jié)點(diǎn)( 1 , 1 )；在0 / 1背包問(wèn)題中，開(kāi)始節(jié)點(diǎn)為根節(jié)點(diǎn)A。開(kāi)始節(jié)點(diǎn)既是一個(gè)活節(jié)點(diǎn)又是一個(gè)E-節(jié)點(diǎn)（expansion node）。從E-節(jié)點(diǎn)可移動(dòng)到一個(gè)新節(jié)點(diǎn)。如果能從當(dāng)前的E-節(jié)點(diǎn)移動(dòng)到一個(gè)新節(jié)點(diǎn)，那么這個(gè)新節(jié)點(diǎn)將變成一個(gè)活節(jié)點(diǎn)和新的E-節(jié)點(diǎn)，舊的E-節(jié)點(diǎn)仍是一個(gè)活節(jié)點(diǎn)。如果不能移到一個(gè)新節(jié)點(diǎn)，當(dāng)前的E-節(jié)點(diǎn)就“死”了（即不再是一個(gè)活節(jié)點(diǎn)），那么便只能返回到最近被考察的活節(jié)點(diǎn)（回溯），這個(gè)活節(jié)點(diǎn)變成了新的E-節(jié)點(diǎn)。當(dāng)我們已經(jīng)找到了答案或者回溯盡了所有的活節(jié)點(diǎn)時(shí)，搜索過(guò)程結(jié)束。
例4-1 [迷宮老鼠] 考察圖16-3a 的矩陣中給出的3×3的“迷宮老鼠”問(wèn)題。我們將利用圖1 6 -1給出的解空間圖來(lái)搜索迷宮。
從迷宮的入口到出口的每一條路徑都與圖1 6 - 1中從( 1 , 1 )到( 3 , 3 )的一條路徑相對(duì)應(yīng)。然而，圖1 6 - 1中有些從( 1 , 1 )到( 3 , 3 )的路徑卻不是迷宮中從入口到出口的路徑。搜索從點(diǎn)( 1 , 1 )開(kāi)始，該點(diǎn)是目前唯一的活節(jié)點(diǎn)，它也是一個(gè)E-節(jié)點(diǎn)。為避免再次走過(guò)這個(gè)位置，置m a z e( 1 , 1 )為1。從這個(gè)位置，能移動(dòng)到( 1 , 2 )或( 2 , 1 )兩個(gè)位置。對(duì)于本例，兩種移動(dòng)都是可行的，因?yàn)樵诿恳粋€(gè)位置都有一個(gè)值0。假定選擇移動(dòng)到( 1 , 2 )，m a z e( 1 , 2 )被置為1以避免再次經(jīng)過(guò)該點(diǎn)。迷宮當(dāng)前狀態(tài)如圖16-3b 所示。這時(shí)有兩個(gè)活節(jié)點(diǎn)(1,1) (1,2)。( 1 , 2 )成為E-節(jié)點(diǎn)。
在圖1 6 - 1中從當(dāng)前E-節(jié)點(diǎn)開(kāi)始有3個(gè)可能的移動(dòng)，其中兩個(gè)是不可行的，因?yàn)槊詫m在這些位置上的值為1。唯一可行的移動(dòng)是( 1 , 3 )。移動(dòng)到這個(gè)位置，并置m a z e( 1 , 3 )為1以避免再次經(jīng)過(guò)該點(diǎn)，此時(shí)迷宮狀態(tài)為1 6 - 3 c。圖1 6 - 1中，從( 1 , 3 )出發(fā)有兩個(gè)可能的移動(dòng)，但沒(méi)有一個(gè)是可行的。所以E-節(jié)點(diǎn)( 1 , 3 )死亡，回溯到最近被檢查的活節(jié)點(diǎn)( 1 , 2 )。在這個(gè)位置也沒(méi)有可行的移動(dòng)，故這個(gè)節(jié)點(diǎn)也死亡了。唯一留下的活節(jié)點(diǎn)是( 1 , 1 )。這個(gè)節(jié)點(diǎn)再次變?yōu)镋-節(jié)點(diǎn)，它可移動(dòng)到( 2 , 1 )。現(xiàn)在活節(jié)點(diǎn)為( 1 , 1 )，( 2 , 1 )。繼續(xù)下去，能到達(dá)點(diǎn)( 3 , 3 )。此時(shí)，活節(jié)點(diǎn)表為( 1 , 1 )，( 2 , 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，這即是到達(dá)出口的路徑。
程序5 - 1 3是一個(gè)在迷宮中尋找路徑的回溯算法。
例4-2 [0/1背包問(wèn)題] 考察如下背包問(wèn)題：n= 3，w= [ 2 0 , 1 5 , 1 5 ]，p= [ 4 0 , 2 5 , 2 5 ]且c= 3 0。從根節(jié)點(diǎn)開(kāi)始搜索圖1 6 - 2中的樹(shù)。根節(jié)點(diǎn)是當(dāng)前唯一的活節(jié)點(diǎn)，也是E-節(jié)點(diǎn)，從這里能夠移動(dòng)到B或C點(diǎn)。假設(shè)移動(dòng)到B，則活節(jié)點(diǎn)為A和B。B是當(dāng)前E-節(jié)點(diǎn)。在節(jié)點(diǎn)B，剩下的容量r 為1 0，而收益c p 為4 0。從B點(diǎn)，能移動(dòng)到D或E。移到D是不可行的，因?yàn)橐频紻所需的容量w2 為1 5。到E的移動(dòng)是可行的，因?yàn)樵谶@個(gè)移動(dòng)中沒(méi)有占用任何容量。E變成新的E-節(jié)點(diǎn)。這時(shí)活節(jié)點(diǎn)為A , B , E。在節(jié)點(diǎn)E，r= 1 0，c p= 4 0。從E，有兩種可能移動(dòng)（到J 和K），到J 的移動(dòng)是不可行的，而到K的移動(dòng)是可行的。節(jié)點(diǎn)K變成了新的E-節(jié)點(diǎn)。因?yàn)镵是一個(gè)葉子，所以得到一個(gè)可行的解。這個(gè)解的收益為c p= 4 0。x 的值由從根到K的路徑來(lái)決定。這個(gè)路徑（ A , B , E , K）也是此時(shí)的活節(jié)點(diǎn)序列。既然不能進(jìn)一步擴(kuò)充K，K節(jié)點(diǎn)死亡，回溯到E，而E也不能進(jìn)一步擴(kuò)充，它也死亡了。接著，回溯到B，它也死亡了，A再次變?yōu)镋-節(jié)點(diǎn)。它可被進(jìn)一步擴(kuò)充，到達(dá)節(jié)點(diǎn)C。此時(shí)r= 3 0，c p= 0。從C點(diǎn)能夠移動(dòng)到F或G。假定移動(dòng)到F。F變?yōu)樾碌腅-節(jié)點(diǎn)并且活節(jié)點(diǎn)為A, C,F。在F，r= 1 5，c p= 2 5。從F點(diǎn)，能移動(dòng)到L或M。假定移動(dòng)到L。此時(shí)r= 0，c p= 5 0。既然L是一個(gè)葉節(jié)點(diǎn)，它表示了一個(gè)比目前找到的最優(yōu)解（即節(jié)點(diǎn)K）更好的可行解，我們把這個(gè)解作為最優(yōu)解。節(jié)點(diǎn)L死亡，回溯到節(jié)點(diǎn)F。繼續(xù)下去，搜索整棵樹(shù)。在搜索期間發(fā)現(xiàn)的最優(yōu)解即為最后的解。
例4-3 [旅行商問(wèn)題] 在這個(gè)問(wèn)題中，給出一個(gè)n 頂點(diǎn)網(wǎng)絡(luò)（有向或無(wú)向），要求找出一個(gè)包含所有n 個(gè)頂點(diǎn)的具有最小耗費(fèi)的環(huán)路。任何一個(gè)包含網(wǎng)絡(luò)中所有n 個(gè)頂點(diǎn)的環(huán)路被稱作一個(gè)旅行（t o u r）。在旅行商問(wèn)題中，要設(shè)法找到一條最小耗費(fèi)的旅行。
圖1 6 - 4給出了一個(gè)四頂點(diǎn)網(wǎng)絡(luò)。在這個(gè)網(wǎng)絡(luò)中，一些旅行如下： 1 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 1和1 , 4 , 3 , 2 , 1。旅行2 , 4 , 3 , 1 , 2；4 , 3 , 1 , 2 , 4和3 , 1 , 2 , 4 , 3和旅行1 , 2 , 4 , 3 , 1一樣。而旅行1 , 3 , 4 , 2 , 1是旅行1 , 2 , 4 , 3 , 1的“逆”。旅行1 , 2 , 4 , 3 , 1的耗費(fèi)為6 6；而1 , 3 , 2 , 4 , 1的耗費(fèi)為2 5；1 , 4 , 3 , 2 , 1為5 9。故1 , 3 , 2 , 4 , 1是該網(wǎng)絡(luò)中最小耗費(fèi)的旅行。
顧名思義，旅行商問(wèn)題可被用來(lái)模擬現(xiàn)實(shí)生活中旅行商所要旅行的地區(qū)問(wèn)題。頂點(diǎn)表示旅行
商所要旅行的城市（包括起點(diǎn)）。邊的耗費(fèi)給出了在兩個(gè)城市旅行所需的時(shí)間（或花費(fèi)）。旅行表示當(dāng)旅行商游覽了所有城市再回到出發(fā)點(diǎn)時(shí)所走的路線。
旅行商問(wèn)題還可用來(lái)模擬其他問(wèn)題。假定要在一個(gè)金屬薄片或印刷電路板上鉆許多孔。孔的位置已知。這些孔由一個(gè)機(jī)器鉆頭來(lái)鉆，它從起始位置開(kāi)始，移動(dòng)到每一個(gè)鉆孔位置鉆孔，然后回到起始位置。總共花的時(shí)間是鉆所有孔的時(shí)間與鉆頭移動(dòng)的時(shí)間。鉆所有孔所需的時(shí)間獨(dú)立于鉆孔順序。然而，鉆頭移動(dòng)時(shí)間是鉆頭移動(dòng)距離的函數(shù)。因此，希望找到最短的移動(dòng)路徑。
另有一個(gè)例子，考察一個(gè)批量生產(chǎn)的環(huán)境，其中有一個(gè)特殊的機(jī)器可用來(lái)生產(chǎn)n 個(gè)不同的產(chǎn)品。利用一個(gè)生產(chǎn)循環(huán)不斷地生產(chǎn)這些產(chǎn)品。在一個(gè)循環(huán)中，所有n 個(gè)產(chǎn)品被順序生產(chǎn)出來(lái)，然后再開(kāi)始下一個(gè)循環(huán)。在下一個(gè)循環(huán)中，又采用了同樣的生產(chǎn)順序。例如，如果這臺(tái)機(jī)器被用來(lái)順序?yàn)樾∑噰娂t、白、藍(lán)漆，那么在為藍(lán)色小汽車噴漆之后，我們又開(kāi)始了新一輪循環(huán)，為紅色小汽車噴漆，然后是白色小汽車、藍(lán)色小汽車、紅色小汽車，..，如此下去。一個(gè)循環(huán)的花費(fèi)包括生產(chǎn)一個(gè)循環(huán)中的產(chǎn)品所需的花費(fèi)以及循環(huán)中從一個(gè)產(chǎn)品轉(zhuǎn)變到另一個(gè)產(chǎn)品的花費(fèi)。雖然生產(chǎn)產(chǎn)品的花費(fèi)獨(dú)立于產(chǎn)品生產(chǎn)順序，但循環(huán)中從生產(chǎn)一個(gè)產(chǎn)品轉(zhuǎn)變到生產(chǎn)另一個(gè)產(chǎn)品的花費(fèi)卻與順序有關(guān)。為了使耗費(fèi)最小化，可以定義一個(gè)有向圖，圖中的頂點(diǎn)表示產(chǎn)品，邊＜(i , j)＞上的耗費(fèi)值為生產(chǎn)過(guò)程中從產(chǎn)品i 轉(zhuǎn)變到產(chǎn)品j 所需的耗費(fèi)。一個(gè)最小耗費(fèi)的旅行定義了一個(gè)最小耗費(fèi)的生產(chǎn)循環(huán)。
既然旅行是包含所有頂點(diǎn)的一個(gè)循環(huán)，故可以把任意一個(gè)點(diǎn)作為起點(diǎn)（因此也是終點(diǎn)）。
針對(duì)圖1 6 - 4，任意選取點(diǎn)1作為起點(diǎn)和終點(diǎn)，則每一個(gè)旅行可用頂點(diǎn)序列1, v2 ,., vn , 1來(lái)描述，
v2 , ., vn 是(2, 3, ., n) 的一個(gè)排列。可能的旅行可用一個(gè)樹(shù)來(lái)描述，其中每一個(gè)從根到葉的路
徑定義了一個(gè)旅行。圖1 6 - 5給出了一棵表示四頂點(diǎn)網(wǎng)絡(luò)的樹(shù)。從根到葉的路徑中各邊的標(biāo)號(hào)定義了一個(gè)旅行（還要附加1作為終點(diǎn)）。例如，到節(jié)點(diǎn)L的路徑表示了旅行1 , 2 , 3 , 4 , 1，而到節(jié)點(diǎn)O的路徑表示了旅行1 , 3 , 4 , 2 , 1。網(wǎng)絡(luò)中的每一個(gè)旅行都由樹(shù)中的一條從根到葉的確定路徑來(lái)表示。因此，樹(shù)中葉的數(shù)目為(n- 1 )！。
回溯算法將用深度優(yōu)先方式從根節(jié)點(diǎn)開(kāi)始，通過(guò)搜索解空間樹(shù)發(fā)現(xiàn)一個(gè)最小耗費(fèi)的旅行。對(duì)圖1 6 - 4的網(wǎng)絡(luò)，利用圖1 6 - 5的解空間樹(shù)，一個(gè)可能的搜索為A B C F L。在L點(diǎn)，旅行1 , 2 , 3 , 4 , 1作為當(dāng)前最好的旅行被記錄下來(lái)。它的耗費(fèi)是5 9。從L點(diǎn)回溯到活節(jié)點(diǎn)F。由于F沒(méi)有未被檢查的孩子，所以它成為死節(jié)點(diǎn)，回溯到C點(diǎn)。C變?yōu)镋-節(jié)點(diǎn)，向前移動(dòng)到G，然后是M。這樣構(gòu)造出了旅行1 , 2 , 4 , 3 , 1，它的耗費(fèi)是6 6。既然它不比當(dāng)前的最佳旅行好，拋棄它并回溯到G，然后是C , B。從B點(diǎn)，搜索向前移動(dòng)到D，然后是H , N。這個(gè)旅行1 , 3 , 2 , 4 , 1的耗費(fèi)是2 5，比當(dāng)前的最佳旅行好，把它作為當(dāng)前的最好旅行。從N點(diǎn)，搜索回溯到H，然后是D。在D點(diǎn)，再次向前移動(dòng)，到達(dá)O點(diǎn)。如此繼續(xù)下去，可搜索完整個(gè)樹(shù)，得出1 , 3 , 2 , 4 , 1是最少耗費(fèi)的旅行。
當(dāng)要求解的問(wèn)題需要根據(jù)n 個(gè)元素的一個(gè)子集來(lái)優(yōu)化某些函數(shù)時(shí)，解空間樹(shù)被稱作子集樹(shù)（subset tree）。所以對(duì)有n 個(gè)對(duì)象的0 / 1背包問(wèn)題來(lái)說(shuō)，它的解空間樹(shù)就是一個(gè)子集樹(shù)。這樣一棵樹(shù)有2n 個(gè)葉節(jié)點(diǎn)，全部節(jié)點(diǎn)有2n+ 1－1個(gè)。因此，每一個(gè)對(duì)樹(shù)中所有節(jié)點(diǎn)進(jìn)行遍歷的算法都必須耗時(shí)W ( 2n )。當(dāng)要求解的問(wèn)題需要根據(jù)一個(gè)n 元素的排列來(lái)優(yōu)化某些函數(shù)時(shí)，解空間樹(shù)被稱作排列樹(shù)（permutation tree）。這樣的樹(shù)有n! 個(gè)葉節(jié)點(diǎn)，所以每一個(gè)遍歷樹(shù)中所有節(jié)點(diǎn)的算法都必須耗時(shí)W (n! )。圖1 6 - 5中的樹(shù)是頂點(diǎn){ 2 , 3 , 4 }的最佳排列的解空間樹(shù)，頂點(diǎn)1是旅行的起點(diǎn)和終點(diǎn)。
通過(guò)確定一個(gè)新近到達(dá)的節(jié)點(diǎn)能否導(dǎo)致一個(gè)比當(dāng)前最優(yōu)解還要好的解，可加速對(duì)最優(yōu)解的搜索。如果不能，則移動(dòng)到該節(jié)點(diǎn)的任何一個(gè)子樹(shù)都是無(wú)意義的，這個(gè)節(jié)點(diǎn)可被立即殺死，用來(lái)殺死活節(jié)點(diǎn)的策略稱為限界函數(shù)（ bounding function）。在例1 6 - 2中，可使用如下限界函數(shù)：殺死代表不可行解決方案的節(jié)點(diǎn)；對(duì)于旅行商問(wèn)題，可使用如下限界函數(shù)：如果目前建立的部分旅行的耗費(fèi)不少于當(dāng)前最佳路徑的耗費(fèi)，則殺死當(dāng)前節(jié)點(diǎn)。如果在圖1 6 - 4的例子中使用該限界函數(shù)，那么當(dāng)?shù)竭_(dá)節(jié)點(diǎn)I時(shí)，已經(jīng)找到了具有耗費(fèi)2 5的1 , 3 , 2 , 4 , 1的旅行。在節(jié)點(diǎn)I，部分旅行1 , 3 , 4的耗費(fèi)為2 6，若旅行通過(guò)該節(jié)點(diǎn)，那么不能找到一個(gè)耗費(fèi)小于2 5的旅行，故搜索以I為根節(jié)點(diǎn)的子樹(shù)毫無(wú)意義。
小結(jié)
回溯方法的步驟如下：
1) 定義一個(gè)解空間，它包含問(wèn)題的解。
2) 用適于搜索的方式組織該空間。
3) 用深度優(yōu)先法搜索該空間，利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。
回溯算法的一個(gè)有趣的特性是在搜索執(zhí)行的同時(shí)產(chǎn)生解空間。在搜索期間的任何時(shí)刻，僅保留從開(kāi)始節(jié)點(diǎn)到當(dāng)前E-節(jié)點(diǎn)的路徑。因此，回溯算法的空間需求為O（從開(kāi)始節(jié)點(diǎn)起最長(zhǎng)路徑的長(zhǎng)度）。這個(gè)特性非常重要，因?yàn)榻饪臻g的大小通常是最長(zhǎng)路徑長(zhǎng)度的指數(shù)或階乘。所以如果要存儲(chǔ)全部解空間的話，再多的空間也不夠用。
練習(xí)
1. 考察如下0 / 1背包問(wèn)題：n= 4，w= [ 2 0 , 2 5 , 1 5 , 3 5 ]，p= [ 4 0 , 4 9 , 2 5 , 6 0 ]，c= 6 2。
1) 畫出該0 / 1背包問(wèn)題的解空間樹(shù)。
2) 對(duì)該樹(shù)運(yùn)用回溯算法（利用給出的p s , w s , c值），依回溯算法遍歷節(jié)點(diǎn)的順序標(biāo)記節(jié)點(diǎn)。確定回溯算法未遍歷的節(jié)點(diǎn)。
2. 1) 當(dāng)n= 5時(shí)，畫出旅行商問(wèn)題的解空間樹(shù)。
2) 在該樹(shù)上，運(yùn)用回溯算法（使用圖1 6 - 6的例子）。依回溯算法遍歷節(jié)點(diǎn)的順序標(biāo)記節(jié)點(diǎn)。確定未被遍歷的節(jié)點(diǎn)。
3. 每周六， Mary 和Joe 都在一起打乒乓球。她們每人都有一個(gè)裝有1 2 0個(gè)球的籃子。
這樣一直打下去，直到兩個(gè)籃子為空。然后她們需要從球桌周圍拾起2 4 0個(gè)球，放入各自
的籃子。Mary 只拾她這邊的球，而Joe 拾剩下的球。描述如何用旅行商問(wèn)題幫助Mary 和
Joe 決定她們拾球的順序以便她們能走最少的路徑。
4.2 應(yīng)用
4.2.1 貨箱裝船
1. 問(wèn)題
在1 . 3節(jié)中，考察了用最大數(shù)量的貨箱裝船的問(wèn)題。現(xiàn)在對(duì)該問(wèn)題做一些改動(dòng)。在新問(wèn)題中，有兩艘船， n 個(gè)貨箱。第一艘船的載重量是c1，第二艘船的載重量是c2，wi 是貨箱i 的重量且
n ?i = 1wi≤c1+c2。我們希望確定是否有一種可將所有n 個(gè)貨箱全部裝船的方法。若有的話，找出該方法。
例4-4 當(dāng)n= 3，c1 =c2 = 5 0，w=[10,40,40] 時(shí)，可將貨箱1 , 2裝到第一艘船上，貨箱3裝到第二艘船上。如果w= [ 2 0 , 4 0 , 4 0 ]，則無(wú)法將貨箱全部裝船。當(dāng)n ?i = 1wi＝c1+c2 時(shí)，兩艘船的裝載問(wèn)題等價(jià)于子集之和（ s u m - o f - s u b s e t）問(wèn)題，即有n 個(gè)數(shù)字，要求找到一個(gè)子集（如果存在的話）使它的和為c1。當(dāng)c1=c2 且n ?i = 1wi＝2c1 時(shí)，兩艘船的裝載問(wèn)題等價(jià)于分割問(wèn)題（ partition problem），即有n個(gè)數(shù)字ai , ( 1≤i≤n)，要求找到一個(gè)子集（若存在的話），使得子集之和為( n ?i = 1ai)/ 2。分割問(wèn)題和子集之和問(wèn)題都是N P-復(fù)雜問(wèn)題。而且即使問(wèn)題被限制為整型數(shù)字，它們?nèi)允荖 P-復(fù)雜問(wèn)題。所以不能期望在多項(xiàng)式時(shí)間內(nèi)解決兩艘船的裝載問(wèn)題。當(dāng)存在一種方法能夠裝載所有n 個(gè)貨箱時(shí)，可以驗(yàn)證以下的裝船策略可以獲得成功： 1) 盡可能地將第一艘船裝至它的重量極限； 2) 將剩余貨箱裝到第二艘船。為了盡可能地將第一艘船裝滿，需要選擇一個(gè)貨箱的子集，它們的總重量盡可能接近c(diǎn)1。這個(gè)選擇可通過(guò)求解0 / 1背包問(wèn)題來(lái)實(shí)現(xiàn)，即尋找m ax (n ?i = 1wi xi )，其中n ?i = 1wi xi≤c1，xi ?{ 0 , 1 }，1≤i≤n。當(dāng)重量是整數(shù)時(shí)，可用1 5 . 2節(jié)的動(dòng)態(tài)規(guī)劃方法確定第一艘船的最佳裝載。用元組方法所需時(shí)間為O ( m i n {c1 , 2 n }）。可以使用回溯方法設(shè)計(jì)一個(gè)復(fù)雜性為O ( 2n ) 的算法，在有些實(shí)例中，該方法比動(dòng)態(tài)規(guī)劃算法要好。
2. 第一種回溯算法
既然想要找到一個(gè)重量的子集，使子集之和盡量接近c(diǎn)1，那么可以使用一個(gè)子集空間，并將其組織成如圖1 6 - 2那樣的二叉樹(shù)。可用深度優(yōu)先的方法搜索該解空間以求得最優(yōu)解。使用限界函數(shù)去阻止不可能獲得解答的節(jié)點(diǎn)的擴(kuò)張。如果Z是樹(shù)的j+ 1層的一個(gè)節(jié)點(diǎn)，那么從根到O的路徑定義了xi（1≤i≤j）的值。使用這些值，定義c w（當(dāng)前重量）為n ?i = 1wi xi 。若c w>c1，則以O(shè)為根的子樹(shù)不能產(chǎn)生一個(gè)可行的解答。可將這個(gè)測(cè)試作為限界函數(shù)。當(dāng)且僅當(dāng)一個(gè)節(jié)點(diǎn)的c w值大于c1 時(shí)，定義它是不可行的。
例4-5 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = 1 2。解空間樹(shù)為圖1 6 - 2的樹(shù)再加上一層節(jié)點(diǎn)。搜索從根A開(kāi)始且c w= 0。若移動(dòng)到左孩子B則c w= 8，c w≤c1 = 1 2。以B為根的子樹(shù)包含一個(gè)可行的節(jié)點(diǎn)，故移動(dòng)到節(jié)點(diǎn)B。從節(jié)點(diǎn)B不能移動(dòng)到節(jié)點(diǎn)D，因?yàn)閏 w+w2 >c1。移動(dòng)到節(jié)點(diǎn)E，這個(gè)移動(dòng)未改變c w。下一步為節(jié)點(diǎn)J，c w= 1 0。J的左孩子的c w值為1 3，超出了c1，故搜索不能移動(dòng)到J的左孩子。
可移動(dòng)到J的右孩子，它是一個(gè)葉節(jié)點(diǎn)。至此，已找到了一個(gè)子集，它的c w= 1 0。xi 的值由從A到J的右孩子的路徑獲得，其值為[ 1 , 0 , 1 , 0 ]。
回溯算法接著回溯到J，然后是E。從E，再次沿著樹(shù)向下移動(dòng)到節(jié)點(diǎn)K，此時(shí)c w= 8。移動(dòng)到它的左子樹(shù)，有c w= 11。既然已到達(dá)了一個(gè)葉節(jié)點(diǎn)，就看是否c w的值大于當(dāng)前的最優(yōu)c w 值。結(jié)果確實(shí)大于最優(yōu)值，所以這個(gè)葉節(jié)點(diǎn)表示了一個(gè)比[ 1 , 0 , 1 , 0 ]更好的解決方案。到該節(jié)點(diǎn)的路徑?jīng)Q定了x 的值[ 1 , 0 , 0 , 1 ]。從該葉節(jié)點(diǎn)，回溯到節(jié)點(diǎn)K，現(xiàn)在移動(dòng)到K的右孩子，一個(gè)具有c w= 8的葉節(jié)點(diǎn)。這個(gè)葉節(jié)點(diǎn)中沒(méi)有比當(dāng)前最優(yōu)cw 值還好的cw 值，所以回溯到K , E , B直到A。從根節(jié)點(diǎn)開(kāi)始，沿樹(shù)繼續(xù)向下移動(dòng)。算法將移動(dòng)到C并搜索它的子樹(shù)。
當(dāng)使用前述的限界函數(shù)時(shí)，便產(chǎn)生了程序1 6 - 1所示的回溯算法。函數(shù)M a x L o a d i n g返回≤c的最大子集之和，但它不能找到產(chǎn)生該和的子集。后面將改進(jìn)代碼以便找到這個(gè)子集。
M a x L o a d i n g調(diào)用了一個(gè)遞歸函數(shù)m a x L o a d i n g，它是類L o a d i n g的一個(gè)成員，定義L o a d i n g類是為了減少M(fèi) a x L o a d i n g中的參數(shù)個(gè)數(shù)。maxLoading(1) 實(shí)際執(zhí)行解空間的搜索。MaxLoading(i) 搜索以i層節(jié)點(diǎn)（該節(jié)點(diǎn)已被隱式確定）為根的子樹(shù)。從根到該節(jié)點(diǎn)的路徑定義的子解答有一個(gè)重量值c w，目前最優(yōu)解答的重量為b e s t w，這些變量以及與類L o a d i n g的一個(gè)成員相關(guān)聯(lián)的其他變量，均由M a x L o a d i n g初始化。
程序16-1 第一種回溯算法
template<class T>
class Loading {
friend MaxLoading(T [], T, int);
p r i v a t e :
void maxLoading(int i);
int n; // 貨箱數(shù)目
T *w, // 貨箱重量數(shù)組
c, // 第一艘船的容量
c w, // 當(dāng)前裝載的重量
bestw; // 目前最優(yōu)裝載的重量
} ;
template<class T>
void Loading<T>::maxLoading(int i)
{// 從第i 層節(jié)點(diǎn)搜索
if (i > n) {// 位于葉節(jié)點(diǎn)
if (cw > bestw) bestw = cw;
r e t u r n ; }
// 檢查子樹(shù)
if (cw + w[i] <= c) {// 嘗試x[i] = 1
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
maxLoading(i+1);// 嘗試x[i] = 0
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最優(yōu)裝載的重量
Loading<T> X;
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// 計(jì)算最優(yōu)裝載的重量
X . m a x L o a d i n g ( 1 ) ;
return X.bestw;
}
如果i＞n，則到達(dá)了葉節(jié)點(diǎn)。被葉節(jié)點(diǎn)定義的解答有重量c w，它一定≤c，因?yàn)樗阉鞑粫?huì)移動(dòng)到不可行的節(jié)點(diǎn)。若c w > b e s t w，則目前最優(yōu)解答的值被更新。當(dāng)i≤n 時(shí)，我們處在有兩個(gè)孩子的節(jié)點(diǎn)Z上。左孩子表示x [ i ] = 1的情況，只有c w + w [ i ]≤c 時(shí)，才能移到這里。當(dāng)移動(dòng)到左孩子時(shí)， cw 被置為c w + w [ i ]，且到達(dá)一個(gè)i + 1層的節(jié)點(diǎn)。以該節(jié)點(diǎn)為根的子樹(shù)被遞歸搜索。當(dāng)搜索完成時(shí)，回到節(jié)點(diǎn)Z。為了得到Z的cw 值，需用當(dāng)前的cw 值減去w [ i ]，Z的右子樹(shù)還未搜索。既然這個(gè)子樹(shù)表示x [ i ] = 0的情況，所以無(wú)需進(jìn)行可行性檢查就可移動(dòng)到該子樹(shù)，因?yàn)橐粋€(gè)可行節(jié)點(diǎn)的右孩子總是可行的。
注意：解空間樹(shù)未被m a x L o a d i n g顯示構(gòu)造。函數(shù)m a x L o a d i n g在它到達(dá)的每一個(gè)節(jié)點(diǎn)上花費(fèi)( 1 )時(shí)間。到達(dá)的節(jié)點(diǎn)數(shù)量為O ( 2n )，所以復(fù)雜性為O ( 2n )。這個(gè)函數(shù)使用的遞歸棧空間為(n)。
3. 第二種回溯方法
通過(guò)不移動(dòng)到不可能包含比當(dāng)前最優(yōu)解還要好的解的右子樹(shù)，能提高函數(shù)m a x L o a d i n g的性能。令b e s t w為目前最優(yōu)解的重量， Z為解空間樹(shù)的第i 層的一個(gè)節(jié)點(diǎn)， c w的定義如前。以Z為根的子樹(shù)中沒(méi)有葉節(jié)點(diǎn)的重量會(huì)超過(guò)c w + r，其中r=n ?j = i + 1w[ j ] 為剩余貨箱的重量。因此，當(dāng)c w + r≤b e s t w時(shí)，沒(méi)有必要去搜索Z的右子樹(shù)。
例4-6 令n, w, c1 的值與例4 - 5中相同。用新的限界函數(shù)，搜索將像原來(lái)那樣向前進(jìn)行直至到達(dá)第一個(gè)葉節(jié)點(diǎn)J（它是J的右孩子）。bestw 被置為1 0。回溯到E，然后向下移動(dòng)到K的左孩子，此時(shí)b e s t w被更新為11。我們沒(méi)有移動(dòng)到K的右孩子，因?yàn)樵谟液⒆庸?jié)點(diǎn)c w = 8，r = 0，c w + r≤b e s t w。回溯到節(jié)點(diǎn)A。同樣，不必移動(dòng)到右孩子C，因?yàn)樵贑點(diǎn)c w = 0，r = 11且c w + r≤b e s t w。加強(qiáng)了條件的限界函數(shù)避免了對(duì)A的右子樹(shù)及K的右子樹(shù)的搜索。
當(dāng)使用加強(qiáng)了條件的限界函數(shù)時(shí)，可得到程序1 6 - 2的代碼。這個(gè)代碼將類型為T的私有變量r 加到了類L o a d i n g的定義中。新的代碼不必檢查是否一個(gè)到達(dá)的葉節(jié)點(diǎn)有比當(dāng)前最優(yōu)解還優(yōu)的重量值。這樣的檢查是不必要的，因?yàn)榧訌?qiáng)的限界函數(shù)不允許移動(dòng)到不能產(chǎn)生較好解的節(jié)點(diǎn)。因此，每到達(dá)一個(gè)新的葉節(jié)點(diǎn)就意味著找到了比當(dāng)前最優(yōu)解還優(yōu)的解。雖然新代碼的復(fù)雜性仍是O ( 2n )，但它可比程序1 6 - 1少搜索一些節(jié)點(diǎn)。
程序16-2 程序1 6 - 1的優(yōu)化
template<class T>
void Loading<T>::maxLoading(int i)
{// // 從第i 層節(jié)點(diǎn)搜索
if (i > n) {// 在葉節(jié)點(diǎn)上
bestw = cw;
r e t u r n ; }
// 檢查子樹(shù)
r -= w[i];
if (cw + w[i] <= c) {//嘗試x[i] = 1
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
if (cw + r > bestw) //嘗試x[i] = 0
m a x L o a d i n g ( i + 1 ) ;
r += w[i];
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最優(yōu)裝載的重量
Loading<T> X;
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// r的初始值為所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w[i];
// 計(jì)算最優(yōu)裝載的重量
X . m a x L o a d i n g ( 1 ) ;
return X.bestw;
}
4. 尋找最優(yōu)子集
為了確定具有最接近c(diǎn) 的重量的貨箱子集，有必要增加一些代碼來(lái)記錄當(dāng)前找到的最優(yōu)子集。為了記錄這個(gè)子集，將參數(shù)bestx 添加到Maxloading 中。bestx 是一個(gè)整數(shù)數(shù)組，其中元素可為0或1，當(dāng)且僅當(dāng)b e s t x [ i ] = 1時(shí)，貨箱i 在最優(yōu)子集中。新的代碼見(jiàn)程序1 6 - 3。
程序16-3 給出最優(yōu)裝載的代碼
template<class T>
void Loading<T>::maxLoading(int i)
{ / /從第i 層節(jié)點(diǎn)搜索
if (i > n) {// 在葉節(jié)點(diǎn)上
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw; return;}
// 檢查子樹(shù)
r -= w[i];
if (cw + w[i] <= c) {//嘗試x[i] = 1
x[i] = 1;
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
if (cw + r > bestw) {//嘗試x[i] = 0
x[i] = 0;
m a x L o a d i n g ( i + 1 ) ; }
r += w[i];
}
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最優(yōu)裝載及其值
Loading<T> X;
// 初始化X
X.x = new int [n+1];
X.w = w;
X.c = c;
X.n = n;
X.bestx = bestx;
X.bestw = 0;
X.cw = 0;
// r的初始值為所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w[i];
X . m a x L o a d i n g ( 1 ) ;
delete [] X.x;
return X.bestw;
}
這段代碼在L o a d i n g中增加了兩個(gè)私有數(shù)據(jù)成員： x 和b e s t x。這兩個(gè)私有數(shù)據(jù)成員都是整型的一維數(shù)組。數(shù)組x 用來(lái)記錄從搜索樹(shù)的根到當(dāng)前節(jié)點(diǎn)的路徑（即它保留了路徑上的xi 值），b e s t x記錄當(dāng)前最優(yōu)解。無(wú)論何時(shí)到達(dá)了一個(gè)具有較優(yōu)解的葉節(jié)點(diǎn)， bestx 被更新以表示從根到葉的路徑。為1的xi 值確定了要被裝載的貨箱。數(shù)據(jù)x 的空間由MaxLoading 分配。
因?yàn)閎estx 可以被更新O ( 2n )次，故maxLoading 的復(fù)雜性為O (n2n )。使用下列方法之一，復(fù)雜性可降為O ( 2n )：
1) 首先運(yùn)行程序1 6 - 2的代碼，以決定最優(yōu)裝載重量，令其為W。然后運(yùn)行程序1 6 - 3的一個(gè)修改版本。該版本以b e s t w = W開(kāi)始運(yùn)行，當(dāng)c w + r≥b e s t w時(shí)搜索右子樹(shù)，第一次到達(dá)一個(gè)葉節(jié)點(diǎn)時(shí)便終止（即i > n）。
2) 修改程序1 6 - 3的代碼以不斷保留從根到當(dāng)前最優(yōu)葉的路徑。尤其當(dāng)位于i 層節(jié)點(diǎn)時(shí)，則到最優(yōu)葉的路徑由x [ j ]（1≤j<i）和b e s tx [ j ]（j≤i≤n）給出。按照這種方法，算法每次回溯一級(jí)，并在b e s t x中存儲(chǔ)一個(gè)x [ i ]。由于算法回溯所需時(shí)間為O ( 2n )，因此額外開(kāi)銷為O ( 2n )。
5. 一個(gè)改進(jìn)的迭代版本
可改進(jìn)程序1 6 - 3的代碼以減少它的空間需求。因?yàn)閿?shù)組x 中記錄可在樹(shù)中移動(dòng)的所有路徑，故可以消除大小為(n)的遞歸棧空間。如例4 - 5所示，從解空間樹(shù)的任何節(jié)點(diǎn)，算法不斷向左孩子移動(dòng)，直到不能再移動(dòng)為止。如果一個(gè)葉子已被到達(dá)，則最優(yōu)解被更新。否則，它試圖移動(dòng)到右孩子。當(dāng)要么到達(dá)一個(gè)葉節(jié)點(diǎn)，要么不值得移動(dòng)到一個(gè)右孩子時(shí)，算法回溯到一個(gè)節(jié)點(diǎn)，條件是從該節(jié)點(diǎn)向其右孩子移動(dòng)有可能找到最優(yōu)解。這個(gè)節(jié)點(diǎn)有一個(gè)特性，即它是路徑中具有x [ i ] = 1的節(jié)點(diǎn)中離根節(jié)點(diǎn)最近的節(jié)點(diǎn)。如果向右孩子的移動(dòng)是有效的，那么就這么做，然后再完成一系列向左孩子的移動(dòng)。如果向右孩子的移動(dòng)是無(wú)效的，則回溯到x [ i ] = 1的下一個(gè)節(jié)點(diǎn)。
該算法遍歷樹(shù)的方式可被編碼成與程序1 6 - 4一樣的迭代（即循環(huán)）算法。不像遞歸代碼，這種代碼在檢查是否該向右孩子移動(dòng)之前就移動(dòng)到了右孩子。如果這個(gè)移動(dòng)是不可行的，則回溯。迭代代碼的時(shí)間復(fù)雜性與程序1 6 - 3一樣。
程序16-4 迭代代碼
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最佳裝載及其值
// 迭代回溯程序
// 初始化根節(jié)點(diǎn)
int i = 1; // 當(dāng)前節(jié)點(diǎn)的層次
// x[1:i-1] 是到達(dá)當(dāng)前節(jié)點(diǎn)的路徑
int *x = new int [n+1];
T bestw = 0, // 迄今最優(yōu)裝載的重量
cw = 0, // 當(dāng)前裝載的重量
r = 0; // 剩余貨箱重量的和
for (int j = 1; j <= n; j++)
r += w[j];
// 在樹(shù)中搜索
while (true) {
// 下移，盡可能向左
while (i <= n && cw + w[i] <= c) {
// 移向左孩子
r -= w[i];
cw += w[i];
x[i] = 1;
i + + ;
}
if (i > n) {// 到達(dá)葉子
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw;}
else {// 移向右孩子
r -= w[i];
x[i] = 0;
i + + ; }
// 必要時(shí)返回
while (cw + r <= bestw) {
// 本子樹(shù)沒(méi)有更好的葉子，返回
i - - ;
while (i > 0 && !x[i]) {
// 從一個(gè)右孩子返回
r += w[i];
i - - ;
}
if (i == 0) {delete [] x;
return bestw;}
// 移向右子樹(shù)
x[i] = 0;
cw -= w[i];
i + + ;
}
}
}
4.2.2 0/1背包問(wèn)題
0 / 1背包問(wèn)題是一個(gè)N P-復(fù)雜問(wèn)題，為了解決該問(wèn)題，在1 . 4節(jié)采用了貪婪算法，在3 . 2節(jié)又采用了動(dòng)態(tài)規(guī)劃算法。在本節(jié)，將用回溯算法解決該問(wèn)題。既然想選擇一個(gè)對(duì)象的子集，將它們裝入背包，以便獲得的收益最大，則解空間應(yīng)組織成子集樹(shù)的形狀（如圖1 6 - 2所示）。該回溯算法與4 . 2節(jié)的裝載問(wèn)題很類似。首先形成一個(gè)遞歸算法，去找到可獲得的最大收益。然后，對(duì)該算法加以改進(jìn)，形成代碼。改進(jìn)后的代碼可找到獲得最大收益時(shí)包含在背包中的對(duì)象的集合。
與程序1 6 - 2一樣，左孩子表示一個(gè)可行的節(jié)點(diǎn)，無(wú)論何時(shí)都要移動(dòng)到它；當(dāng)右子樹(shù)可能含有比當(dāng)前最優(yōu)解還優(yōu)的解時(shí)，移動(dòng)到它。一種決定是否要移動(dòng)到右子樹(shù)的簡(jiǎn)單方法是令r 為還未遍歷的對(duì)象的收益之和，將r 加到c p（當(dāng)前節(jié)點(diǎn)所獲收益）之上，若（ r + c p）≤b e s t p（目前最優(yōu)解的收益），則不需搜索右子樹(shù)。一種更有效的方法是按收益密度pi / wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量，當(dāng)遇到第一個(gè)不能全部放入背包的對(duì)象時(shí)，就使用它的一部分。
例4-7 考察一個(gè)背包例子： n= 4，c= 7，p= [ 9 , 1 0 , 7 , 4 ]，w= [ 3 , 5 , 2 , 1 ]。這些對(duì)象的收益密度為[ 3 , 2 , 3 . 5 , 4 ]。當(dāng)背包以密度遞減的順序被填充時(shí)，對(duì)象4首先被填充，然后是對(duì)象3、對(duì)象1。在這三個(gè)對(duì)象被裝入背包之后，剩余容量為1。這個(gè)容量可容納對(duì)象2的0 . 2倍的重量。將0 . 2倍的該對(duì)象裝入，產(chǎn)生了收益值2。被構(gòu)造的解為x= [ 1 , 0 . 2 , 1 , 1 ]，相應(yīng)的收益值為2 2。盡管該解不可行（x2 是0 . 2，而實(shí)際上它應(yīng)為0或1），但它的收益值2 2一定不少于要求的最優(yōu)解。因此，該0 / 1背包問(wèn)題沒(méi)有收益值多于2 2的解。
解空間樹(shù)為圖1 6 - 2再加上一層節(jié)點(diǎn)。當(dāng)位于解空間樹(shù)的節(jié)點(diǎn)B時(shí)，x1= 1，目前獲益為c p= 9。該節(jié)點(diǎn)所用容量為c w= 3。要獲得最好的附加收益，要以密度遞減的順序填充剩余容量c l e f t=ccw= 4。也就是說(shuō)，先放對(duì)象4，然后是對(duì)象3，然后是對(duì)象2的0 . 2倍的重量。因此，子樹(shù)A的最優(yōu)解的收益值至多為2 2。當(dāng)位于節(jié)點(diǎn)C時(shí)，c p=c w= 0，c l e f t= 7。按密度遞減順序填充剩余容量，則對(duì)象4和3被裝入。然后是對(duì)象2的0 . 8倍被裝入。這樣產(chǎn)生出收益值1 9。在子樹(shù)C中沒(méi)有節(jié)點(diǎn)可產(chǎn)生出比1 9還大的收益值。
在節(jié)點(diǎn)E，c p= 9，c w= 3，c l e f t= 4。僅剩對(duì)象3和4要被考慮。當(dāng)對(duì)象按密度遞減的順序被考慮時(shí)，對(duì)象4先被裝入，然后是對(duì)象3。所以在子樹(shù)E中無(wú)節(jié)點(diǎn)有多于c p+ 4 + 7 = 2 0的收益值。如果已經(jīng)找到了一個(gè)具有收益值2 0或更多的解，則無(wú)必要去搜索E子樹(shù)。
一種實(shí)現(xiàn)限界函數(shù)的好方法是首先將對(duì)象按密度排序。假定已經(jīng)做了這樣的排序。定義類K n a p（見(jiàn)程序1 6 - 5）來(lái)減少限界函數(shù)B o u n d（見(jiàn)程序1 6 - 6）及遞歸函數(shù)K n a p s a c k（見(jiàn)程序1 6 - 7）的參數(shù)數(shù)量，該遞歸函數(shù)用于計(jì)算最優(yōu)解的收益值。參數(shù)的減少又可引起遞歸棧空間的減少以及每一個(gè)K n a p s a c k的執(zhí)行時(shí)間的減少。注意函數(shù)K n a p s a c k和函數(shù)m a x L o a d i n g（見(jiàn)程序1 6 - 2）的相似性。同時(shí)注意僅當(dāng)向右孩子移動(dòng)時(shí)，限界函數(shù)才被計(jì)算。當(dāng)向左孩子移動(dòng)時(shí)，左孩子的限界函數(shù)的值與其父節(jié)點(diǎn)相同。
程序16-5 Knap類
template<class Tw, class Tp>
class Knap {
friend Tp Knapsack(Tp *, Tw *, Tw, int);
p r i v a t e :
Tp Bound(int i);
void Knapsack(int i);
Tw c; / /背包容量
int n; // 對(duì)象數(shù)目
Tw *w; // 對(duì)象重量的數(shù)組
Tp *p; // 對(duì)象收益的數(shù)組
Tw cw; // 當(dāng)前背包的重量
Tp cp; // 當(dāng)前背包的收益
Tp bestp; // 迄今最大的收益
} ;
程序16-6 限界函數(shù)
template<class Tw, class Tp>
Tp Knap<Tw, Tp>::Bound(int i)
{// 返回子樹(shù)中最優(yōu)葉子的上限值Return upper bound on value of
// best leaf in subtree.
Tw cleft = c - cw; // 剩余容量
Tp b = cp; // 收益的界限
// 按照收益密度的次序裝填剩余容量
while (i <= n && w[i] <= cleft) {
cleft -= w[i];
b += p[i];
i + + ;
}
// 取下一個(gè)對(duì)象的一部分
if (i <= n) b += p[i]/w[i] * cleft;
return b;
}
程序16-7 0/1背包問(wèn)題的迭代函數(shù)
template<class Tw, class Tp>
void Knap<Tw, Tp>::Knapsack(int i)
{// 從第i 層節(jié)點(diǎn)搜索
if (i > n) {// 在葉節(jié)點(diǎn)上
bestp = cp;
r e t u r n ; }
// 檢查子樹(shù)
if (cw + w[i] <= c) {//嘗試x[i] = 1
cw += w[i];
cp += p[i];
K n a p s a c k ( i + 1 ) ;
cw -= w[i];
cp -= p[i];}
if (Bound(i+1) > bestp) // 嘗試x[i] = 0
K n a p s a c k ( i + 1 ) ;
}
在執(zhí)行程序1 6 - 7的函數(shù)Kn a p s a c k之前，需要按密度對(duì)對(duì)象排序，也要確保對(duì)象的重量總和超出背包的容量。為了完成排序，定義了類O b j e c t（見(jiàn)程序1 6 - 8）。注意定義操作符< =是為了使歸并排序程序（見(jiàn)程序1 4 - 3）能按密度遞減的順序排序。
程序16-8 Object類
class Object {
friend int Knapsack(int *, int *, int, int);
p u b l i c :
int operator<=(Object a) const
{return (d >= a.d);}
p r i v a t e :
int ID; // 對(duì)象號(hào)
float d; // 收益密度
} ;
程序1 6 - 9首先驗(yàn)證重量之和超出背包容量，然后排序?qū)ο螅趫?zhí)行K n a p : : K n a p s a c k之前完成一些必要的初始化。K n a p : K n a p s a c k的復(fù)雜性是O (n2n )，因?yàn)橄藿绾瘮?shù)的復(fù)雜性為O (n)，且該函數(shù)在O ( 2n )個(gè)右孩子處被計(jì)算。
程序16-9 程序1 6 - 7的預(yù)處理代碼
template<class Tw, class Tp>
Tp Knapsack(Tp p[], Tw w[], Tw c, int n)
{// 返回最優(yōu)裝包的值
// 初始化
Tw W = 0; // 記錄重量之和
Tp P = 0; // 記錄收益之和
// 定義一個(gè)按收益密度排序的對(duì)象數(shù)組
Object *Q = new Object [n];
for (int i = 1; i <= n; i++) {
// 收益密度的數(shù)組
Q[i-1].ID = i;
Q[i-1].d = 1.0*p[i]/w[i];
P += p[i];
W += w[i];
}
if (W <= c) return P; // 可容納所有對(duì)象
MergeSort(Q,n); // 按密度排序
// 創(chuàng)建K n a p的成員
K n a p < Tw, Tp> K;
K.p = new Tp [n+1];
K.w = new Tw [n+1];
for (i = 1; i <= n; i++) {
K.p[i] = p[Q[i-1].ID];
K.w[i] = w[Q[i-1].ID];
}
K.cp = 0;
K.cw = 0;
K.c = c;
K.n = n;
K.bestp = 0;
// 尋找最優(yōu)收益
K . K n a p s a c k ( 1 ) ;
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
4.2.3 最大完備子圖
令U為無(wú)向圖G的頂點(diǎn)的子集，當(dāng)且僅當(dāng)對(duì)于U中的任意點(diǎn)u 和v，(u , v)是圖G的一條邊時(shí)，U定義了一個(gè)完全子圖（complete subgraph）。子圖的尺寸為圖中頂點(diǎn)的數(shù)量。當(dāng)且僅當(dāng)一個(gè)完全子圖不被包含在G的一個(gè)更大的完全子圖中時(shí)，它是圖G的一個(gè)完備子圖。最大的完備子圖是具有最大尺寸的完備子圖。
例4-8 在圖16-7a 中，子集{ 1 , 2 }定義了一個(gè)尺寸為2的完全子圖。這個(gè)子圖不是一個(gè)完備子圖，因?yàn)樗话谝粋€(gè)更大的完全子圖{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }定義了該圖的一個(gè)最大的完備子圖。點(diǎn)集{ 1 , 4 , 5 }和{ 2 , 3 , 5 }定義了其他的最大的完備子圖。
當(dāng)且僅當(dāng)對(duì)于U中任意點(diǎn)u 和v，(u , v) 不是G的一條邊時(shí)，U定義了一個(gè)空子圖。當(dāng)且僅當(dāng)一個(gè)子集不被包含在一個(gè)更大的點(diǎn)集中時(shí)，該點(diǎn)集是圖G的一個(gè)獨(dú)立集（independent set），同時(shí)它也定義了圖G的空子圖。最大獨(dú)立集是具有最大尺寸的獨(dú)立集。對(duì)于任意圖G，它的補(bǔ)圖（c o m p l e m e n t） 是有同樣點(diǎn)集的圖，且當(dāng)且僅當(dāng)（ u,v）不是G的一條邊時(shí)，它是的一條邊。
例4-9 圖16-7b 是圖16-7a 的補(bǔ)圖，反之亦然。{ 2 , 4 }定義了16-7a 的一個(gè)空子圖，它也是該圖的一個(gè)最大獨(dú)立集。雖然{ 1 , 2 }定義了圖16-7b 的一個(gè)空子圖，它不是一個(gè)獨(dú)立集，因?yàn)樗话诳兆訄D{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }是圖16-7b 中的一個(gè)最大獨(dú)立集。
如果U定義了G的一個(gè)完全子圖，則它也定義了的一個(gè)空子圖，反之亦然。所以在G的完備子圖與的獨(dú)立集之間有對(duì)應(yīng)關(guān)系。特別的， G的一個(gè)最大完備子圖定義了的一個(gè)最大獨(dú)立集。
最大完備子圖問(wèn)題是指尋找圖G的一個(gè)最大完備子圖。類似地，最大獨(dú)立集問(wèn)題是指尋找圖G的一個(gè)最大獨(dú)立集。這兩個(gè)問(wèn)題都是N P-復(fù)雜問(wèn)題。當(dāng)用算法解決其中一個(gè)問(wèn)題時(shí)，也就解決了另一個(gè)問(wèn)題。例如，如果有一個(gè)求解最大完備子圖問(wèn)題的算法，則也能解決最大獨(dú)立集問(wèn)題，方法是首先計(jì)算所給圖的補(bǔ)圖，然后尋找補(bǔ)圖的最大完備子圖。
例4-10 假定有一個(gè)n 個(gè)動(dòng)物構(gòu)成的集合。可以定義一個(gè)有n 個(gè)頂點(diǎn)的相容圖（c o m p a t i b i l i t yg r a p h）G。當(dāng)且僅當(dāng)動(dòng)物u 和v 相容時(shí)，（u,v）是G的一條邊。G的一個(gè)最大完備子圖定義了相互間相容的動(dòng)物構(gòu)成的最大子集。
3 . 2節(jié)考察了如何找到一個(gè)具有最大尺寸的互不交叉的網(wǎng)組的集合問(wèn)題。可以把這個(gè)問(wèn)題看作是一個(gè)最大獨(dú)立集問(wèn)題。定義一個(gè)圖，圖中每個(gè)頂點(diǎn)表示一個(gè)網(wǎng)組。當(dāng)且僅當(dāng)兩個(gè)頂點(diǎn)對(duì)應(yīng)的網(wǎng)組交叉時(shí)，它們之間有一條邊。所以該圖的一個(gè)最大獨(dú)立集對(duì)應(yīng)于非交叉網(wǎng)組的一個(gè)最大尺寸的子集。當(dāng)網(wǎng)組有一個(gè)端點(diǎn)在路徑頂端，而另一個(gè)在底端時(shí)，非交叉網(wǎng)組的最大尺寸的子集能在多項(xiàng)式時(shí)間（實(shí)際上是(n2 )）內(nèi)用動(dòng)態(tài)規(guī)劃算法得到。當(dāng)一個(gè)網(wǎng)組的端點(diǎn)可能在平面中的任意地方時(shí)，不可能有在多項(xiàng)式時(shí)間內(nèi)找到非交叉網(wǎng)組的最大尺寸子集的算法。最大完備子圖問(wèn)題和最大獨(dú)立集問(wèn)題可由回溯算法在O (n2n )時(shí)間內(nèi)解決。兩個(gè)問(wèn)題都可使用子集解空間樹(shù)（如圖1 6 - 2所示）。考察最大完備子圖問(wèn)題，該遞歸回溯算法與程序1 6 - 3非常類似。當(dāng)試圖移動(dòng)到空間樹(shù)的i 層節(jié)點(diǎn)Z的左孩子時(shí)，需要證明從頂點(diǎn)i 到每一個(gè)其他的頂點(diǎn)j（xj = 1且j 在從根到Z的路徑上）有一條邊。當(dāng)試圖移動(dòng)到Z的右孩子時(shí)，需要證明還有足夠多的頂點(diǎn)未被搜索，以便在右子樹(shù)有可能找到一個(gè)較大的完備子圖。
回溯算法可作為類A d j a c e n c y G r a p h（見(jiàn)程序1 2 - 4）的一個(gè)成員來(lái)實(shí)現(xiàn)，為此首先要在該類
中加入私有靜態(tài)成員x（整型數(shù)組，用于存儲(chǔ)到當(dāng)前節(jié)點(diǎn)的路徑），b e s t x（整型數(shù)組，保存目
前的最優(yōu)解），b e s t n（b e s t x中點(diǎn)的數(shù)量），c n（x 中點(diǎn)的數(shù)量）。所以類A d j a c e c y G r a p h的所有實(shí)
例都能共享這些變量。
函數(shù)m a x C l i q u e（見(jiàn)程序1 6 - 1 0）是類A d j a c e n c y G r a p h的一個(gè)私有成員，而M a x C l i q u e是一個(gè)
共享成員。函數(shù)m a x C l i q u e對(duì)解空間樹(shù)進(jìn)行搜索，而M a x C i q u e初始化必要的變量。M a x c l i q u e ( v )
的執(zhí)行返回最大完備子圖的尺寸，同時(shí)它也設(shè)置整型數(shù)組v，當(dāng)且僅當(dāng)頂點(diǎn)i 不是所找到的最大
完備子圖的一個(gè)成員時(shí)，v [ i ] = 0。
程序16-10 最大完備子圖
void AdjacencyGraph::maxClique(int i)
{// 計(jì)算最大完備子圖的回溯代碼
if (i > n) {// 在葉子上
// 找到一個(gè)更大的完備子圖，更新
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestn = cn;
r e t u r n ; }
// 在當(dāng)前完備子圖中檢查頂點(diǎn)i是否與其它頂點(diǎn)相連
int OK = 1;
for (int j = 1; j < i; j++)
if (x[j] && a[i][j] == NoEdge) {
// i 不與j 相連
OK = 0;
b r e a k ; }
if (OK) {// 嘗試x[i] = 1
x[i] = 1; // 把i 加入完備子圖
c n + + ;
m a x C l i q u e ( i + 1 ) ;
x[i] = 0;
c n - - ; }
if (cn + n - i > bestn) {// 嘗試x[i] = 0
x[i] = 0;
m a x C l i q u e ( i + 1 ) ; }
}
int AdjacencyGraph::MaxClique(int v[])
{// 返回最大完備子圖的大小
// 完備子圖的頂點(diǎn)放入v [ 1 : n ]
// 初始化
x = new int [n+1];
cn = 0;
bestn = 0;
bestx = v;
// 尋找最大完備子圖
m a x C l i q u e ( 1 ) ;
delete [] x;
return bestn;
}
4.2.4 旅行商問(wèn)題
旅行商問(wèn)題（例4 . 3）的解空間是一個(gè)排列樹(shù)。這樣的樹(shù)可用函數(shù)P e r m (見(jiàn)程序1 - 1 0 )搜索，并可生成元素表的所有排列。如果以x=[1, 2, ., n] 開(kāi)始，那么通過(guò)產(chǎn)生從x2 到xn 的所
有排列，可生成n 頂點(diǎn)旅行商問(wèn)題的解空間。由于P e r m產(chǎn)生具有相同前綴的所有排列，因此可以容易地改造P e r m，使其不能產(chǎn)生具有不可行前綴（即該前綴沒(méi)有定義路徑）或不可能比當(dāng)前最優(yōu)旅行還優(yōu)的前綴的排列。注意在一個(gè)排列空間樹(shù)中，由任意子樹(shù)中的葉節(jié)點(diǎn)定
義的排列有相同的前綴（如圖1 6 - 5所示）。因此，考察時(shí)刪除特定的前綴等價(jià)于搜索期間不
進(jìn)入相應(yīng)的子樹(shù)。旅行商問(wèn)題的回溯算法可作為類A d j a c e n c y W D i g r a p h（見(jiàn)程序1 2 - 1）的一個(gè)成員。在其他例子中，有兩個(gè)成員函數(shù)： t S P和T S P。前者是一個(gè)保護(hù)或私有成員，后者是一個(gè)共享成員。函數(shù)G . T S P ( v )返回最少耗費(fèi)旅行的花費(fèi)，旅行自身由整型數(shù)組v 返回。若網(wǎng)絡(luò)中無(wú)旅行，則返回N o E d g e。t S P在排列空間樹(shù)中進(jìn)行遞歸回溯搜索， T S P是其一個(gè)必要的預(yù)處理過(guò)程。T S P假定x（用來(lái)保存到當(dāng)前節(jié)點(diǎn)的路徑的整型數(shù)組），b e s t x（保存目前發(fā)現(xiàn)的最優(yōu)旅行的整型數(shù)組），
c c（類型為T的變量，保存當(dāng)前節(jié)點(diǎn)的局部旅行的耗費(fèi)），b e s t c（類型為T的變量，保存目前最優(yōu)解的耗費(fèi)）已被定義為A d j a c e n c y W D i g r a p h中的靜態(tài)數(shù)據(jù)成員。T S P見(jiàn)程序1 6 - 11。t S P ( 2 )搜索一棵包含x [ 2 : n ]的所有排列的樹(shù)。
程序1 6 - 11 旅行商回溯算法的預(yù)處理程序
template<class T>
T AdjacencyWDigraph<T>::TSP(int v[])
{// 用回溯算法解決旅行商問(wèn)題
// 返回最優(yōu)旅游路徑的耗費(fèi)，最優(yōu)路徑存入v [ 1 : n ]
/ /初始化
x = new int [n+1];
// x 是排列
for (int i = 1; i <= n; i++)
x[i] = i;
bestc = NoEdge;
bestx = v; // 使用數(shù)組v來(lái)存儲(chǔ)最優(yōu)路徑
cc = 0;
// 搜索x [ 2 : n ]的各種排列
t S P ( 2 ) ;
delete [] x;
return bestc;
}
函數(shù)t S P見(jiàn)程序1 6 - 1 2。它的結(jié)構(gòu)與函數(shù)P e r m相同。當(dāng)i=n 時(shí)，處在排列樹(shù)的葉節(jié)點(diǎn)的父節(jié)點(diǎn)上，并且需要驗(yàn)證從x[n-1] 到x[n] 有一條邊，從x[n] 到起點(diǎn)x[1] 也有一條邊。若兩條邊都存在，則發(fā)現(xiàn)了一個(gè)新旅行。在本例中，需要驗(yàn)證是否該旅行是目前發(fā)現(xiàn)的最優(yōu)旅行。若是，則將旅行和它的耗費(fèi)分別存入b e s t x與b e s t c中。
當(dāng)i＜n 時(shí)，檢查當(dāng)前i-1 層節(jié)點(diǎn)的孩子節(jié)點(diǎn)，并且僅當(dāng)以下情況出現(xiàn)時(shí)，移動(dòng)到孩子節(jié)點(diǎn)之一：1) 有從x[i-1] 到x[i] 的一條邊（如果是這樣的話， x [ 1 : i ]定義了網(wǎng)絡(luò)中的一條路徑）；2 )路徑x[1:i] 的耗費(fèi)小于當(dāng)前最優(yōu)解的耗費(fèi)。變量cc 保存目前所構(gòu)造的路徑的耗費(fèi)。
每次找到一個(gè)更好的旅行時(shí)，除了更新bestx 的耗費(fèi)外， tS P需耗時(shí)O ( (n- 1 ) ! )。因?yàn)樾璋l(fā)生O ( (n-1)!) 次更新且每一次更新的耗費(fèi)為(n) 時(shí)間，因此更新所需時(shí)間為O (n* (n- 1 ) ! )。通過(guò)使用加強(qiáng)的條件（練習(xí)1 6），能減少由tS P搜索的樹(shù)節(jié)點(diǎn)的數(shù)量。
程序16-12 旅行商問(wèn)題的迭代回溯算法
void AdjacencyWDigraph<T>::tSP(int i)
{// 旅行商問(wèn)題的回溯算法
if (i == n) {// 位于一個(gè)葉子的父節(jié)點(diǎn)
// 通過(guò)增加兩條邊來(lái)完成旅行
if (a[x[n-1]][x[n]] != NoEdge &&
a[x[n]][1] != NoEdge &&
(cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc ||
bestc == NoEdge)) {// 找到更優(yōu)的旅行路徑
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];}
}
else {// 嘗試子樹(shù)
for (int j = i; j <= n; j++)
/ /能移動(dòng)到子樹(shù)x [ j ]嗎?
if (a[x[i-1]][x[j]] != NoEdge &&
(cc + a[x[i-1]][x[i]] < bestc ||
bestc == NoEdge)) {//能
// 搜索該子樹(shù)
Swap(x[i], x[j]);
cc += a[x[i-1]][x[i]];
t S P ( i + 1 ) ;
cc -= a[x[i-1]][x[i]];
Swap(x[i], x[j]);}
}
}
4.2.5 電路板排列
在大規(guī)模電子系統(tǒng)的設(shè)計(jì)中存在著電路板排列問(wèn)題。這個(gè)問(wèn)題的經(jīng)典形式為將
n個(gè)電路板放置到一個(gè)機(jī)箱的許多插槽中，（如圖1 6 - 8所示）。n個(gè)電路板的每一種排
列定義了一種放置方法。令B= {b1 , ., bn }表示這n個(gè)電路板。m個(gè)網(wǎng)組集合L= {N1,
., Nm }由電路板定義，Ni 是B的子集，子集中的元素需要連接起來(lái)。實(shí)際中用電線
將插有這些電路板的插槽連接起來(lái)。
例4 - 11 令n=8, m= 5。集合B和L如下：
B= {b1, b2, b3, b4, b5, b6, b7, b8 }
L= {N1, N2, N3, N4, N5 }
N1 = {b4, b5, b6 }
N2 = {b2, b3 }
N3 = {b1, b3 }
N4 = {b3, b6 }
N5 = {b7, b8 }
令x 為電路板的一個(gè)排列。電路板xi 被放置到機(jī)箱的插槽i 中。d e n s i t y(x) 為機(jī)箱中任意一對(duì)相鄰插槽間所連電線數(shù)目中的最大值。對(duì)于圖1 6 - 9中的排列，d e n s i t y為2。有兩根電線連接了插槽2和3，插槽4和5，插槽5和6。插槽6和7之間無(wú)電線，余下的相鄰插槽都只有一根電線。板式機(jī)箱被設(shè)計(jì)成具有相同的相鄰插槽間距，因此這個(gè)間距決定了機(jī)箱的大小。該間距必須保證足夠大以便容納相鄰插槽間的連線。因此這個(gè)距離（繼而機(jī)箱的大小）由d e n s i t y(x)決定。
電路板排列問(wèn)題的目標(biāo)是找到一種電路板的排列方式，使其有最小的d e n s i t y。既然該問(wèn)題是一個(gè)N P-復(fù)雜問(wèn)題，故它不可能由一個(gè)多項(xiàng)式時(shí)間的算法來(lái)解決，而象回溯這樣的搜索方法則是解決該問(wèn)題的一種較好方法。回溯算法為了找到最優(yōu)的電路板排列方式，將搜索一個(gè)排列空間。
用一個(gè)n×m 的整型數(shù)組B表示輸入，當(dāng)且僅當(dāng)Nj 中包含電路板bi 時(shí)，B [ i ] [ j ] = 1。令t o t a l [ j ]為Nj 中電路板的數(shù)量。對(duì)于任意部分的電路板排列x [ 1 : i ]，令n o w [ j ]為既在x [ 1 : i ]中又被包含在Nj 中的電路板的數(shù)量。當(dāng)且僅當(dāng)n o w [ j ] > 0且n o w [ j ]≠t o t a l [ j ]時(shí)，Nj 在插槽i 和i + 1之間有連線。插槽i 和i + 1間的線密度可利用該測(cè)試方法計(jì)算出來(lái)。在插槽k和k + 1 ( 1≤k≤i ) 間的線密度的最大值給出了局部排列的密度。
為了實(shí)現(xiàn)電路板排列問(wèn)題的回溯算法，使用了類B o a r d（見(jiàn)程序1 6 - 1 3）。程序1 6 - 1 4給出了私有方法B e s t O r d e r，程序1 6 - 1 5給出了函數(shù)A r r a n g e B o a r d s。ArrangeBoards 返回最優(yōu)的電路板排列密度，最優(yōu)的排列由數(shù)組bestx 返回。ArrangeBoards 創(chuàng)建類Board 的一個(gè)成員x 并初始化與之相關(guān)的變量。尤其是total 被初始化以使total[j] 等于Nj 中電路板的數(shù)量。now[1:n] 被置為0，與一個(gè)空的局部排列相對(duì)應(yīng)。調(diào)用x .BestOrder(1,0) 搜索x[1:n] 的排列樹(shù)，以從密度為0的空排列中找到一個(gè)最優(yōu)的排列。通常，x.BestOrder(i,cd) 尋找最優(yōu)的局部排列x [ 1 : i - 1 ]，該局部排列密度為c d。函數(shù)B e s t O r d e r（見(jiàn)程序1 6 - 1 4）和程序1 6 - 1 2有同樣的結(jié)構(gòu)，它也搜索一個(gè)排列空間。當(dāng)i=n 時(shí)，表示所有的電路板已被放置且cd 為排列的密度。既然這個(gè)算法只尋找那些比當(dāng)前最優(yōu)排列還優(yōu)的排列，所以不必驗(yàn)證cd 是否比beste 要小。當(dāng)i<n 時(shí)，排列還未被完成。x[1:i-1] 定義了當(dāng)前節(jié)點(diǎn)的局部排列，而cd 是它的密度。這個(gè)節(jié)點(diǎn)的每一個(gè)孩子通過(guò)在當(dāng)前排列的末端增加一個(gè)電路板而擴(kuò)充了這個(gè)局部排列。對(duì)于每一個(gè)這樣的擴(kuò)充，新的密度l d被計(jì)算，且只有l(wèi)d<bestd 的節(jié)點(diǎn)被搜索，其他的節(jié)點(diǎn)和它們的子樹(shù)不被搜索。在排列樹(shù)的每一個(gè)節(jié)點(diǎn)處，函數(shù)B e s t O r d e r花費(fèi)(m)的時(shí)間計(jì)算每一個(gè)孩子節(jié)點(diǎn)的密度。所以計(jì)算密度的總時(shí)間為O (m n! )。此外，產(chǎn)生排列的時(shí)間為O (n!) 且更新最優(yōu)排列的時(shí)間為O (m n)。
注意每一個(gè)更新至少將b e s t d的值減少1，且最終b e s t d≥0。所以更新的次數(shù)是O (m)。B e s t O r d e r的整體復(fù)雜性為O (m n! )。
程序16-13 Board的類定義
class Board {
friend ArrangeBoards(int**, int, int, int []);
p r i v a t e :
void BestOrder(int i, int cd);
int *x, // 到達(dá)當(dāng)前節(jié)點(diǎn)的路徑
* b e s t x , // 目前的最優(yōu)排列
* t o t a l , // total[j] = 帶插槽j的板的數(shù)目
* n o w, // now[j] = 在含插槽j的部分排列中的板的數(shù)目
b e s t d , // bestx的密度
n , / /板的數(shù)目
m , // 插槽的數(shù)目
* * B ; // 板的二維數(shù)組
} ;
程序16-14 搜索排列樹(shù)
void Board::BestOrder(int i, int cd)
{// 按回溯算法搜索排列樹(shù)
if (i == n) {
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestd = cd;}
else // 嘗試子樹(shù)
for (int j = i; j <= n; j++) {
// 用x[j] 作為下一塊電路板對(duì)孩子進(jìn)行嘗試
// 在最后一個(gè)插槽更新并計(jì)算密度
int ld = 0;
for (int k = 1; k <= m; k++) {
now[k] += B[x[j]][k];
if (now[k] > 0 && total[k] != now[k])
l d + + ;
}
// 更新ld 為局部排列的總密度
if (cd > ld) ld = cd;
// 僅當(dāng)子樹(shù)中包含一個(gè)更優(yōu)的排列時(shí)，搜索該子樹(shù)
if (ld < bestd) {// 移動(dòng)到孩子
Swap(x[i], x[j]);
BestOrder(i+1, ld);
Swap(x[i], x[j]);}
// 重置
for (k = 1; k <= m; k++)
now[k] -= B[x[j]][k];
}
}
程序16-15 BestOrder(程序1 6 - 1 4)的預(yù)處理代碼
int ArrangeBoards(int **B, int n, int m, int bestx[ ])
{// 返回最優(yōu)密度
// 在b e s t x中返回最優(yōu)排列
Board X;
// 初始化X
X.x = new int [n+1];
X.total = new int [m+1];
X.now = new int [m+1];
X.B = B;
X.n = n;
X.m = m;
X.bestx = bestx;
X.bestd = m + 1;
// 初始化t o t a l和n o w
for (int i = 1; i <= m; i++) {
X.total[i] = 0;
X.now[i] = 0;
}
// 初始化x并計(jì)算t o t a l
for (i = 1; i <= n; i++) {
X.x[i] = i;
for (int j = 1; j <= m; j++)
X.total[j] += B[i][j];
}
// 尋找最優(yōu)排列
X . B e s t O r d e r ( 1 , 0 ) ;
delete [] X.x;
delete [] X.total;
delete [] X.now;
return X.bestd;