【正文】 , Tp K。 = new Tw [n+1]。 i = n。[i] = w[Q[i1].ID]。 = 0。 = n。// 尋找最優(yōu)收益K . K n a p s a c k ( 1 ) 。delete [] 。return 。子圖的尺寸為圖中頂點(diǎn)的數(shù)量。最大的完備子圖是具有最大尺寸的完備子圖。這個子圖不是一個完備子圖，因為它被包含在一個更大的完全子圖{ 1 , 2 , 5 }中。點(diǎn)集{ 1 , 4 , 5 }和{ 2 , 3 , 5 }定義了其他的最大的完備子圖。當(dāng)且僅當(dāng)一個子集不被包含在一個更大的點(diǎn)集中時，該點(diǎn)集是圖G的一個獨(dú)立集（independent set），同時它也定義了圖G的空子圖。對于任意圖G，它的補(bǔ)圖（c o m p l e m e n t） 是有同樣點(diǎn)集的圖，且當(dāng)且僅當(dāng)（ u,v）不是G的一條邊時，它是的一條邊。{ 2 , 4 }定義了167a 的一個空子圖，它也是該圖的一個最大獨(dú)立集。{ 1 , 2 , 5 }是圖167b 中的一個最大獨(dú)立集。所以在G的完備子圖與的獨(dú)立集之間有對應(yīng)關(guān)系。最大完備子圖問題是指尋找圖G的一個最大完備子圖。這兩個問題都是N P復(fù)雜問題。例如，如果有一個求解最大完備子圖問題的算法，則也能解決最大獨(dú)立集問題，方法是首先計算所給圖的補(bǔ)圖，然后尋找補(bǔ)圖的最大完備子圖?？梢远x一個有n 個頂點(diǎn)的相容圖（c o m p a t i b i l i t yg r a p h）G。G的一個最大完備子圖定義了相互間相容的動物構(gòu)成的最大子集?？梢园堰@個問題看作是一個最大獨(dú)立集問題。當(dāng)且僅當(dāng)兩個頂點(diǎn)對應(yīng)的網(wǎng)組交叉時，它們之間有一條邊。當(dāng)網(wǎng)組有一個端點(diǎn)在路徑頂端，而另一個在底端時，非交叉網(wǎng)組的最大尺寸的子集能在多項式時間（實際上是(n2 )）內(nèi)用動態(tài)規(guī)劃算法得到。最大完備子圖問題和最大獨(dú)立集問題可由回溯算法在O (n2n )時間內(nèi)解決?？疾熳畲笸陚渥訄D問題，該遞歸回溯算法與程序1 6 3非常類似。當(dāng)試圖移動到Z的右孩子時，需要證明還有足夠多的頂點(diǎn)未被搜索，以便在右子樹有可能找到一個較大的完備子圖。所以類A d j a c e c y G r a p h的所有實例都能共享這些變量。函數(shù)m a x C l i q u e對解空間樹進(jìn)行搜索，而M a x C i q u e初始化必要的變量。程序1610 最大完備子圖void AdjacencyGraph::maxClique(int i){// 計算最大完備子圖的回溯代碼if (i n) {// 在葉子上// 找到一個更大的完備子圖，更新for (int j = 1。 j++)bestx[j] = x[j]。r e t u r n 。for (int j = 1。 j++)if (x[j] amp。 a[i][j] == NoEdge) {// i 不與j 相連OK = 0。 }if (OK) {// 嘗試x[i] = 1x[i] = 1。m a x C l i q u e ( i + 1 ) 。c n 。m a x C l i q u e ( i + 1 ) 。 = 0。bestx = v。delete [] x。} 旅行商問題旅行商問題（例4 . 3）的解空間是一個排列樹。如果以x=[1, 2, ., n] 開始，那么通過產(chǎn)生從x2 到xn 的所有排列，可生成n 頂點(diǎn)旅行商問題的解空間。注意在一個排列空間樹中，由任意子樹中的葉節(jié)點(diǎn)定義的排列有相同的前綴（如圖1 6 5所示）。旅行商問題的回溯算法可作為類A d j a c e n c y W D i g r a p h（見程序1 2 1）的一個成員。前者是一個保護(hù)或私有成員，后者是一個共享成員。若網(wǎng)絡(luò)中無旅行，則返回N o E d g e。T S P假定x（用來保存到當(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 ( 2 )搜索一棵包含x [ 2 : n ]的所有排列的樹。// x 是排列for (int i = 1。 i++)x[i] = i。bestx = v。// 搜索x [ 2 : n ]的各種排列t S P ( 2 ) 。return bestc。它的結(jié)構(gòu)與函數(shù)P e r m相同。若兩條邊都存在，則發(fā)現(xiàn)了一個新旅行。若是，則將旅行和它的耗費(fèi)分別存入b e s t x與b e s t c中。變量cc 保存目前所構(gòu)造的路徑的耗費(fèi)。因為需發(fā)生O ( (n1)!) 次更新且每一次更新的耗費(fèi)為(n) 時間，因此更新所需時間為O (n* (n 1 ) ! )。程序1612 旅行商問題的迭代回溯算法void AdjacencyWDigraphT::tSP(int i){// 旅行商問題的回溯算法if (i == n) {// 位于一個葉子的父節(jié)點(diǎn)// 通過增加兩條邊來完成旅行if (a[x[n1]][x[n]] != NoEdge amp。a[x[n]][1] != NoEdge amp。(cc + a[x[n1]][x[n]] + a[x[n]][1] bestc ||bestc == NoEdge)) {// 找到更優(yōu)的旅行路徑for (int j = 1。 j++)bestx[j] = x[j]。}}else {// 嘗試子樹for (int j = i。 j++)/ /能移動到子樹x [ j ]嗎?if (a[x[i1]][x[j]] != NoEdge amp。(cc + a[x[i1]][x[i]] bestc ||bestc == NoEdge)) {//能// 搜索該子樹Swap(x[i], x[j])。t S P ( i + 1 ) 。Swap(x[i], x[j])。這個問題的經(jīng)典形式為將n個電路板放置到一個機(jī)箱的許多插槽中，（如圖1 6 8所示）。令B= {b1 , ., bn }表示這n個電路板。實際中用電線將插有這些電路板的插槽連接起來。集合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 為電路板的一個排列。d e n s i t y(x) 為機(jī)箱中任意一對相鄰插槽間所連電線數(shù)目中的最大值。有兩根電線連接了插槽2和3，插槽4和5，插槽5和6。板式機(jī)箱被設(shè)計成具有相同的相鄰插槽間距，因此這個間距決定了機(jī)箱的大小。因此這個距離（繼而機(jī)箱的大?。┯蒬 e n s i t y(x)決定。既然該問題是一個N P復(fù)雜問題，故它不可能由一個多項式時間的算法來解決，而象回溯這樣的搜索方法則是解決該問題的一種較好方法。用一個nm 的整型數(shù)組B表示輸入，當(dāng)且僅當(dāng)Nj 中包含電路板bi 時，B [ i ] [ j ] = 1。對于任意部分的電路板排列x [ 1 : i ]，令n o w [ j ]為既在x [ 1 : i ]中又被包含在Nj 中的電路板的數(shù)量。插槽i 和i + 1間的線密度可利用該測試方法計算出來。為了實現(xiàn)電路板排列問題的回溯算法，使用了類B o a r d（見程序1 6 1 3）。ArrangeBoards 返回最優(yōu)的電路板排列密度，最優(yōu)的排列由數(shù)組bestx 返回。尤其是total 被初始化以使total[j] 等于Nj 中電路板的數(shù)量。調(diào)用x .BestOrder(1,0) 搜索x[1:n] 的排列樹，以從密度為0的空排列中找到一個最優(yōu)的排列。函數(shù)B e s t O r d e r（見程序1 6 1 4）和程序1 6 1 2有同樣的結(jié)構(gòu)，它也搜索一個排列空間。既然這個算法只尋找那些比當(dāng)前最優(yōu)排列還優(yōu)的排列，所以不必驗證cd 是否比beste 要小。x[1:i1] 定義了當(dāng)前節(jié)點(diǎn)的局部排列，而cd 是它的密度。對于每一個這樣的擴(kuò)充，新的密度l d被計算，且只有l(wèi)dbestd 的節(jié)點(diǎn)被搜索，其他的節(jié)點(diǎn)和它們的子樹不被搜索。所以計算密度的總時間為O (m n! )。注意每一個更新至少將b e s t d的值減少1，且最終b e s t d≥0。B e s t O r d e r的整體復(fù)雜性為O (m n! )。p r i v a t e :void BestOrder(int i, int cd)。 // 板的二維數(shù)組} 。 j = n。bestd = cd。 j = n。for (int k = 1。 k++) {now[k] += B[x[j]][k]。amp。}// 更新ld 為局部排列的總密度if (cd ld) ld = cd。BestOrder(i+1, ld)。}// 重置for (k = 1。 k++)now[k] = B[x[j]][k]。// 初始化X = new int [n+1]。 = new int [m+1]。 = n。 = bestx。// 初始化t o t a l和n o wfor (int i = 1。 i++) {[i] = 0。}// 初始化x并計算t o t a lfor (i = 1。 i++) {[i] = i。 j = m。}// 尋找最優(yōu)排列X . B e s t O r d e r ( 1 , 0 ) 。delete [] 。return 。5. 運(yùn)行程序1 6 3和1 6 4的代碼，測試它們的相對運(yùn)行時間。7. 運(yùn)用1 6 . 2 . 1節(jié)中第4小節(jié)的方法2) 來修改程序1 6 3，使其運(yùn)行時間減少至O ( 2n )。注意，只要找到一個子集，其和為c1，則可終止程序運(yùn)行。代碼不應(yīng)使用像程序1 6 3中的數(shù)組x。9. 優(yōu)化程序1 6 7和1 6 9以便能產(chǎn)生出與背包問題最優(yōu)解相對應(yīng)的一個0 / 1數(shù)組x。該算法與程序1 6 4類似。11. 編寫程序1 6 1 0（與程序1 6 4相對應(yīng)）的迭代版本并比較這兩個版本。你認(rèn)為該版本比程序1 6 1 0好嗎？13. 編寫一個求解最大獨(dú)立集問題的回溯算法。對于類ADjacencyGraph, AdjacencyWGraph, LinkedGraph和L i n k e d W G r a p h（見1 2 . 7節(jié)）的成員，該代碼同樣有效。i =1M a xi + 1的耗費(fèi)。重寫T S P和t S P，盡可能簡化它們。j =2A(xj 1, xj )+n 229。2) 在程序1 6 1 2中，使用if (a [x [i1] ] [x [j] ] ! = NoEdge amp。(cc + a [x [i1] ] [x [i] ] bestc | |bestc == NoEdge) )來決定何時移動到一個孩子節(jié)點(diǎn)。第一個和可根據(jù)cc 計算出來，通過用一個新變量r 保留不在當(dāng)前路徑中的頂點(diǎn)的M i n O u t [ i ]的和，可以很容易地計算出第二個和。與程序1 6 1 2比較，它訪問了排列樹的多少節(jié)點(diǎn)？17. 考察電路板排列問題。N4 中第一個電路板在插槽3中，最后一個電路板在插槽6中，則N4 的長度為3。Ni 最大值為3。試測試代碼的正確性。當(dāng)且僅當(dāng)對于G中的每一條邊(u , v)，u 或v 或u , v 在U中時，G的頂點(diǎn)子集U是一個頂點(diǎn)覆蓋（vertex cover）。在圖1 6 7 a中，{ 1 , 2 , 5 }是大小為3的一個頂點(diǎn)覆蓋。算法的復(fù)雜性是多少？19. [簡易最大切割] 令G是一個無向圖。V是G余下的點(diǎn)的集合。編寫一個回溯算法，尋找最大切割的大小和相應(yīng)的U。令wi j 是從投資者j 那里得到的零件i 的重量，ci j 則為該零件的耗費(fèi)。算法的復(fù)雜性是多少？21. [網(wǎng)絡(luò)設(shè)計] 一個汽油傳送網(wǎng)絡(luò)可由加權(quán)的有向無環(huán)圖G表示。從S出發(fā)，汽油被輸送到圖中的其他頂點(diǎn)。通過網(wǎng)絡(luò)輸送汽油時，壓力的損失是所走距離的函數(shù)。為了維持這個最小壓力，可將壓力放大器放在網(wǎng)絡(luò)中的一些或全部頂點(diǎn)。令d為汽油在壓力由Pm a x 降為Pm i n 時所走的距離。編寫一個回溯算法來求解該問題。當(dāng)且僅當(dāng)兩個皇后在相同的排、列、對角線或反對角線上時，她們之間將發(fā)生沖突。所以只對決定每一個皇后所在的列感興趣。如果任意兩個皇后不沖突，則[c1 , ., ]是[1, 2, ., n]的一個排列。1) 將n 皇后的解空間組織成一棵樹。*23. 編寫一個函數(shù)，使用回溯算法來搜索一個子集空間樹，該樹為一個二叉樹。用0 / 1背包問題來測試程序。*25. 編寫一個函數(shù)，用回溯法搜索一個解空間。用0 / 1背包問題來測試