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