【正文】 絡(luò)的樹。因此，樹中葉的數(shù)目為(n 1 )！。它的耗費(fèi)是5 9。這樣構(gòu)造出了旅行1 , 2 , 4 , 3 , 1，它的耗費(fèi)是6 6。從N點(diǎn)，搜索回溯到H，然后是D。所以對(duì)有n 個(gè)對(duì)象的0 / 1背包問題來說，它的解空間樹就是一個(gè)子集樹。這樣的樹有n! 個(gè)葉節(jié)點(diǎn)，所以每一個(gè)遍歷樹中所有節(jié)點(diǎn)的算法都必須耗時(shí)W (n! )。在例1 6 2中，可使用如下限界函數(shù)：殺死代表不可行解決方案的節(jié)點(diǎn)；對(duì)于旅行商問題，可使用如下限界函數(shù)：如果目前建立的部分旅行的耗費(fèi)不少于當(dāng)前最佳路徑的耗費(fèi)，則殺死當(dāng)前節(jié)點(diǎn)。2) 用適于搜索的方式組織該空間。因此，回溯算法的空間需求為O（從開始節(jié)點(diǎn)起最長(zhǎng)路徑的長(zhǎng)度）。1) 畫出該0 / 1背包問題的解空間樹。2) 在該樹上，運(yùn)用回溯算法（使用圖1 6 6的例子）。她們每人都有一個(gè)裝有1 2 0個(gè)球的籃子。描述如何用旅行商問題幫助Mary 和Joe 決定她們拾球的順序以便她們能走最少的路徑?，F(xiàn)在對(duì)該問題做一些改動(dòng)。我們希望確定是否有一種可將所有n 個(gè)貨箱全部裝船的方法。當(dāng)n 229。i = 1ai)/ 2。當(dāng)存在一種方法能夠裝載所有n 個(gè)貨箱時(shí)，可以驗(yàn)證以下的裝船策略可以獲得成功： 1) 盡可能地將第一艘船裝至它的重量極限； 2) 將剩余貨箱裝到第二艘船。i = 1wi xi≤c1，xi 206?？梢允褂没厮莘椒ㄔO(shè)計(jì)一個(gè)復(fù)雜性為O ( 2n ) 的算法，在有些實(shí)例中，該方法比動(dòng)態(tài)規(guī)劃算法要好。如果Z是樹的j+ 1層的一個(gè)節(jié)點(diǎn)，那么從根到O的路徑定義了xi（1≤i≤j）的值?？蓪⑦@個(gè)測(cè)試作為限界函數(shù)。搜索從根A開始且c w= 0。移動(dòng)到節(jié)點(diǎn)E，這個(gè)移動(dòng)未改變c w。至此，已找到了一個(gè)子集，它的c w= 1 0。移動(dòng)到它的左子樹，有c w= 11。從該葉節(jié)點(diǎn)，回溯到節(jié)點(diǎn)K，現(xiàn)在移動(dòng)到K的右孩子，一個(gè)具有c w= 8的葉節(jié)點(diǎn)。當(dāng)使用前述的限界函數(shù)時(shí)，便產(chǎn)生了程序1 6 1所示的回溯算法。maxLoading(1) 實(shí)際執(zhí)行解空間的搜索。p r i v a t e :void maxLoading(int i)。templateclass Tvoid LoadingT::maxLoading(int i){// 從第i 層節(jié)點(diǎn)搜索if (i n) {// 位于葉節(jié)點(diǎn)if (cw bestw) bestw = cw。cw = w[i]。 = c。// 計(jì)算最優(yōu)裝載的重量X . m a x L o a d i n g ( 1 ) 。若c w b e s t w，則目前最優(yōu)解答的值被更新。以該節(jié)點(diǎn)為根的子樹被遞歸搜索。注意：解空間樹未被m a x L o a d i n g顯示構(gòu)造。3. 第二種回溯方法通過不移動(dòng)到不可能包含比當(dāng)前最優(yōu)解還要好的解的右子樹，能提高函數(shù)m a x L o a d i n g的性能。因此，當(dāng)c w + r≤b e s t w時(shí)，沒有必要去搜索Z的右子樹。回溯到E，然后向下移動(dòng)到K的左孩子，此時(shí)b e s t w被更新為11。加強(qiáng)了條件的限界函數(shù)避免了對(duì)A的右子樹及K的右子樹的搜索。這樣的檢查是不必要的，因?yàn)榧訌?qiáng)的限界函數(shù)不允許移動(dòng)到不能產(chǎn)生較好解的節(jié)點(diǎn)。r e t u r n 。cw = w[i]。// 初始化X = w。 = 0。 i++) += w[i]。為了記錄這個(gè)子集，將參數(shù)bestx 添加到Maxloading 中。 j = n。}// 檢查子樹r = w[i]。cw = w[i]。}templateclass TT MaxLoading(T w[], T c, int n, int bestx[]){// 返回最優(yōu)裝載及其值LoadingT X。 = n。// r的初始值為所有重量之和 = 0。X . m a x L o a d i n g ( 1 ) 。這兩個(gè)私有數(shù)據(jù)成員都是整型的一維數(shù)組。數(shù)據(jù)x 的空間由MaxLoading 分配。該版本以b e s t w = W開始運(yùn)行，當(dāng)c w + r≥b e s t w時(shí)搜索右子樹，第一次到達(dá)一個(gè)葉節(jié)點(diǎn)時(shí)便終止（即i n）。由于算法回溯所需時(shí)間為O ( 2n )，因此額外開銷為O ( 2n )。如果一個(gè)葉子已被到達(dá)，則最優(yōu)解被更新。如果向右孩子的移動(dòng)是有效的，那么就這么做，然后再完成一系列向左孩子的移動(dòng)。如果這個(gè)移動(dòng)是不可行的，則回溯。T bestw = 0, // 迄今最優(yōu)裝載的重量cw = 0, // 當(dāng)前裝載的重量r = 0。// 在樹中搜索while (true) {// 下移，盡可能向左while (i = n amp。x[i] = 1。 j++)bestx[j] = x[j]。i + + 。 !x[i]) {// 從一個(gè)右孩子返回r += w[i]。}// 移向右子樹x[i] = 0。在本節(jié)，將用回溯算法解決該問題。然后，對(duì)該算法加以改進(jìn)，形成代碼。一種更有效的方法是按收益密度pi / wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量，當(dāng)遇到第一個(gè)不能全部放入背包的對(duì)象時(shí)，就使用它的一部分。在這三個(gè)對(duì)象被裝入背包之后，剩余容量為1。盡管該解不可行（x2 是0 . 2，而實(shí)際上它應(yīng)為0或1），但它的收益值2 2一定不少于要求的最優(yōu)解。該節(jié)點(diǎn)所用容量為c w= 3。當(dāng)位于節(jié)點(diǎn)C時(shí)，c p=c w= 0，c l e f t= 7。在子樹C中沒有節(jié)點(diǎn)可產(chǎn)生出比1 9還大的收益值。所以在子樹E中無節(jié)點(diǎn)有多于c p+ 4 + 7 = 2 0的收益值。定義類K n a p（見程序1 6 5）來減少限界函數(shù)B o u n d（見程序1 6 6）及遞歸函數(shù)K n a p s a c k（見程序1 6 7）的參數(shù)數(shù)量，該遞歸函數(shù)用于計(jì)算最優(yōu)解的收益值。當(dāng)向左孩子移動(dòng)時(shí)，左孩子的限界函數(shù)的值與其父節(jié)點(diǎn)相同。Tw c。 // 對(duì)象收益的數(shù)組Tw cw。程序166 限界函數(shù)templateclass Tw, class TpTp KnapTw, Tp::Bound(int i){// 返回子樹中最優(yōu)葉子的上限值Return upper bound on value of// best leaf in subtree.Tw cleft = c cw。 w[i] = cleft) {cleft = w[i]。return b。cp += p[i]。}if (Bound(i+1) bestp) // 嘗試x[i] = 0K n a p s a c k ( i + 1 ) 。程序168 Object類class Object {friend int Knapsack(int *, int *, int, int)。 // 收益密度} 。 // 記錄重量之和Tp P = 0。 i++) {// 收益密度的數(shù)組Q[i1].ID = i。}if (W = c) return P。 = new Tw [n+1]。[i] = w[Q[i1].ID]。 = n。delete [] 。子圖的尺寸為圖中頂點(diǎn)的數(shù)量。這個(gè)子圖不是一個(gè)完備子圖，因?yàn)樗话谝粋€(gè)更大的完全子圖{ 1 , 2 , 5 }中。當(dāng)且僅當(dāng)一個(gè)子集不被包含在一個(gè)更大的點(diǎn)集中時(shí)，該點(diǎn)集是圖G的一個(gè)獨(dú)立集（independent set），同時(shí)它也定義了圖G的空子圖。{ 2 , 4 }定義了167a 的一個(gè)空子圖，它也是該圖的一個(gè)最大獨(dú)立集。所以在G的完備子圖與的獨(dú)立集之間有對(duì)應(yīng)關(guān)系。這兩個(gè)問題都是N P復(fù)雜問題?？梢远x一個(gè)有n 個(gè)頂點(diǎn)的相容圖（c o m p a t i b i l i t yg r a p h）G?？梢园堰@個(gè)問題看作是一個(gè)最大獨(dú)立集問題。當(dāng)網(wǎng)組有一個(gè)端點(diǎn)在路徑頂端，而另一個(gè)在底端時(shí)，非交叉網(wǎng)組的最大尺寸的子集能在多項(xiàng)式時(shí)間（實(shí)際上是(n2 )）內(nèi)用動(dòng)態(tài)規(guī)劃算法得到?？疾熳畲笸陚渥訄D問題，該遞歸回溯算法與程序1 6 3非常類似。所以類A d j a c e c y G r a p h的所有實(shí)例都能共享這些變量。程序1610 最大完備子圖void AdjacencyGraph::maxClique(int i){// 計(jì)算最大完備子圖的回溯代碼if (i n) {// 在葉子上// 找到一個(gè)更大的完備子圖，更新for (int j = 1。r e t u r n 。 j++)if (x[j] amp。 }if (OK) {// 嘗試x[i] = 1x[i] = 1。c n 。 = 0。delete [] x。如果以x=[1, 2, ., n] 開始，那么通過產(chǎn)生從x2 到xn 的所有排列，可生成n 頂點(diǎn)旅行商問題的解空間。旅行商問題的回溯算法可作為類A d j a c e n c y W D i g r a p h（見程序1 2 1）的一個(gè)成員。若網(wǎng)絡(luò)中無旅行，則返回N o E d g e。t S P ( 2 )搜索一棵包含x [ 2 : n ]的所有排列的樹。 i++)x[i] = i。// 搜索x [ 2 : n ]的各種排列t S P ( 2 ) 。它的結(jié)構(gòu)與函數(shù)P e r m相同。若是，則將旅行和它的耗費(fèi)分別存入b e s t x與b e s t c中。因?yàn)樾璋l(fā)生O ( (n1)!) 次更新且每一次更新的耗費(fèi)為(n) 時(shí)間，因此更新所需時(shí)間為O (n* (n 1 ) ! )。a[x[n]][1] != NoEdge amp。 j++)bestx[j] = x[j]。 j++)/ /能移動(dòng)到子樹x [ j ]嗎?if (a[x[i1]][x[j]] != NoEdge amp。t S P ( i + 1 ) 。這個(gè)問題的經(jīng)典形式為將n個(gè)電路板放置到一個(gè)機(jī)箱的許多插槽中，（如圖1 6 8所示）。實(shí)際中用電線將插有這些電路板的插槽連接起來。d e n s i t y(x) 為機(jī)箱中任意一對(duì)相鄰插槽間所連電線數(shù)目中的最大值。板式機(jī)箱被設(shè)計(jì)成具有相同的相鄰插槽間距，因此這個(gè)間距決定了機(jī)箱的大小。既然該問題是一個(gè)N P復(fù)雜問題，故它不可能由一個(gè)多項(xiàng)式時(shí)間的算法來解決，而象回溯這樣的搜索方法則是解決該問題的一種較好方法。對(duì)于任意部分的電路板排列x [ 1 : i ]，令n o w [ j ]為既在x [ 1 : i ]中又被包含在Nj 中的電路板的數(shù)量。為了實(shí)現(xiàn)電路板排列問題的回溯算法，使用了類B o a r d（見程序1 6 1 3）。尤其是total 被初始化以使total[j] 等于Nj 中電路板的數(shù)量。函數(shù)B e s t O r d e r（見程序1 6 1 4）和程序1 6 1 2有同樣的結(jié)構(gòu)，它也搜索一個(gè)排列空間。x[1:i1] 定義了當(dāng)前節(jié)點(diǎn)的局部排列，而cd 是它的密度。所以計(jì)算密度的總時(shí)間為O (m n! )。B e s t O r d e r的整體復(fù)雜性為O (m n! )。 // 板的二維數(shù)組} 。bestd = cd。for (int k = 1。amp。BestOrder(i+1, ld)。 k++)now[k] = B[x[j]][k]。 = new int [m+1]。 = bestx。 i++) {[i] = 0。 i++) {[i] = i。}// 尋找最優(yōu)排列X . B e s t O r d e r ( 1 , 0 ) 。return 。7. 運(yùn)用1 6 . 2 . 1節(jié)中第4小節(jié)的方法2) 來修改程序1 6 3，使其運(yùn)行時(shí)間減少至O ( 2n )。代碼不應(yīng)使用像程序1 6 3中的數(shù)組x。該算法與程序1 6 4類似。你認(rèn)為該版本比程序1 6 1 0好嗎？13. 編寫一個(gè)求解最大獨(dú)立集問題的回溯算法。i =1M a xi + 1的耗費(fèi)。j =2A(xj 1, xj )+n 229。(cc + a [x [i1] ] [x [i] ] bestc | |bestc == NoEdge) )來決定何時(shí)移動(dòng)到一個(gè)孩子節(jié)點(diǎn)。與程序1 6 1 2比較，它訪問了排列樹的多少節(jié)點(diǎn)？17. 考察電路板排列問題。Ni 最大值為3。當(dāng)且僅當(dāng)對(duì)于G中的每一條邊(u , v)，u 或v 或u , v 在U中時(shí)，G的頂點(diǎn)子集U是一個(gè)頂點(diǎn)覆蓋（vertex cover）。算法的復(fù)雜性是多少？19. [簡(jiǎn)易最大切割] 令G是一個(gè)無向圖。編寫一個(gè)回溯算法，尋找最大切割的大小和相應(yīng)的U。算法的復(fù)雜性是多少？21. [網(wǎng)絡(luò)設(shè)計(jì)] 一個(gè)汽油傳送網(wǎng)絡(luò)可由加權(quán)的有向無環(huán)圖G表示。通過網(wǎng)絡(luò)輸送汽油時(shí)，壓力的損失是所走距離的函數(shù)。令d為汽油在壓力由Pm a x 降為Pm i n 時(shí)所走的距離。當(dāng)且僅當(dāng)兩個(gè)皇后在相同的排、列、對(duì)角線或反對(duì)角線上時(shí)，她們之間將發(fā)生沖突。如果任意兩個(gè)皇后不沖突，則[c1 , ., ]是[1, 2, ., n]的一個(gè)排列。*23. 編寫一個(gè)函數(shù)，使用回溯算法來搜索一個(gè)子集空間樹，該樹為一個(gè)二叉樹。*25. 編寫一個(gè)函數(shù)，用回溯法搜索一個(gè)解