【正文】 ] = c) {//嘗試x[i] = 1cw += w[i]。cp = p[i]。注意定義操作符 =是為了使歸并排序程序（見程序1 4 3）能按密度遞減的順序排序。 // 對象號(hào)float d。程序169 程序1 6 7的預(yù)處理代碼templateclass Tw, class TpTp Knapsack(Tp p[], Tw w[], Tw c, int n){// 返回最優(yōu)裝包的值// 初始化Tw W = 0。 i = n。W += w[i]。 = new Tp [n+1]。 i++) {[i] = p[Q[i1].ID]。 = c。delete [] Q。} 最大完備子圖令U為無向圖G的頂點(diǎn)的子集，當(dāng)且僅當(dāng)對于U中的任意點(diǎn)u 和v，(u , v)是圖G的一條邊時(shí)，U定義了一個(gè)完全子圖（plete subgraph）。例48 在圖167a 中，子集{ 1 , 2 }定義了一個(gè)尺寸為2的完全子圖。當(dāng)且僅當(dāng)對于U中任意點(diǎn)u 和v，(u , v) 不是G的一條邊時(shí)，U定義了一個(gè)空子圖。例49 圖167b 是圖167a 的補(bǔ)圖，反之亦然。如果U定義了G的一個(gè)完全子圖，則它也定義了的一個(gè)空子圖，反之亦然。類似地，最大獨(dú)立集問題是指尋找圖G的一個(gè)最大獨(dú)立集。例410 假定有一個(gè)n 個(gè)動(dòng)物構(gòu)成的集合。3 . 2節(jié)考察了如何找到一個(gè)具有最大尺寸的互不交叉的網(wǎng)組的集合問題。所以該圖的一個(gè)最大獨(dú)立集對應(yīng)于非交叉網(wǎng)組的一個(gè)最大尺寸的子集。兩個(gè)問題都可使用子集解空間樹（如圖1 6 2所示）?；厮菟惴勺鳛轭怉 d j a c e n c y G r a p h（見程序1 2 4）的一個(gè)成員來實(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ù)量）。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。bestn = 。 j i。b r e a k 。x[i] = 0。 }}int AdjacencyGraph::MaxClique(int v[]){// 返回最大完備子圖的大小// 完備子圖的頂點(diǎn)放入v [ 1 : n ]// 初始化x = new int [n+1]。// 尋找最大完備子圖m a x C l i q u e ( 1 ) 。這樣的樹可用函數(shù)P e r m (見程序1 1 0 )搜索，并可生成元素表的所有排列。因此，考察時(shí)刪除特定的前綴等價(jià)于搜索期間不進(jìn)入相應(yīng)的子樹。函數(shù)G . T S P ( v )返回最少耗費(fèi)旅行的花費(fèi)，旅行自身由整型數(shù)組v 返回。T S P見程序1 6 11。 i = n。 // 使用數(shù)組v來存儲(chǔ)最優(yōu)路徑cc = 0。}函數(shù)t S P見程序1 6 1 2。在本例中，需要驗(yàn)證是否該旅行是目前發(fā)現(xiàn)的最優(yōu)旅行。每次找到一個(gè)更好的旅行時(shí)，除了更新bestx 的耗費(fèi)外， tS P需耗時(shí)O ( (n 1 ) ! )。amp。 j = n。 j = n。cc += a[x[i1]][x[i]]。}}} 電路板排列在大規(guī)模電子系統(tǒng)的設(shè)計(jì)中存在著電路板排列問題。m個(gè)網(wǎng)組集合L= {N1,., Nm }由電路板定義，Ni 是B的子集，子集中的元素需要連接起來。電路板xi 被放置到機(jī)箱的插槽i 中。插槽6和7之間無電線，余下的相鄰插槽都只有一根電線。電路板排列問題的目標(biāo)是找到一種電路板的排列方式，使其有最小的d e n s i t y。令t o t a l [ j ]為Nj 中電路板的數(shù)量。在插槽k和k + 1 ( 1≤k≤i ) 間的線密度的最大值給出了局部排列的密度。ArrangeBoards 創(chuàng)建類Board 的一個(gè)成員x 并初始化與之相關(guān)的變量。通常，(i,cd) 尋找最優(yōu)的局部排列x [ 1 : i 1 ]，該局部排列密度為c d。當(dāng)in 時(shí)，排列還未被完成。在排列樹的每一個(gè)節(jié)點(diǎn)處，函數(shù)B e s t O r d e r花費(fèi)(m)的時(shí)間計(jì)算每一個(gè)孩子節(jié)點(diǎn)的密度。所以更新的次數(shù)是O (m)。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 。 j++)bestx[j] = x[j]。 j++) {// 用x[j] 作為下一塊電路板對孩子進(jìn)行嘗試// 在最后一個(gè)插槽更新并計(jì)算密度int ld = 0。if (now[k] 0 amp。// 僅當(dāng)子樹中包含一個(gè)更優(yōu)的排列時(shí)，搜索該子樹if (ld bestd) {// 移動(dòng)到孩子Swap(x[i], x[j])。 k = m。 = new int [m+1]。 = m。 i = m。 i = n。 j++)[j] += B[i][j]。delete [] 。6. 運(yùn)用1 6 . 2 . 1節(jié)中第4小節(jié)的方法1) 來更新程序1 6 3，使其能得到時(shí)間復(fù)雜性O(shè) ( 2n )。沒有必要記住目前的最優(yōu)解。10. 用迭代回溯算法求解0 / 1背包問題。12. 改寫程序1 6 1 0，使其首先按度的遞減次序來排列各頂點(diǎn)。15. 令G為一個(gè)n 頂點(diǎn)的有向圖，M a xi 為從頂點(diǎn)i 出發(fā)的具有最大耗費(fèi)的邊的耗費(fèi)1) 證明旅行商的每一個(gè)旅行有一個(gè)小于n 229。16. 令G為具有n 個(gè)頂點(diǎn)的有向圖， M i n O u ti 為從頂點(diǎn)i 出發(fā)的具有最小耗費(fèi)的邊的耗費(fèi)1) 證明具有前綴x1 到xi 的旅行商的所有旅行耗費(fèi)至少為i 229。amp。3) 測試t S P的新版本。N2 的長度為2。18. [頂點(diǎn)覆蓋] 令G為一個(gè)無向圖。編寫一個(gè)回溯算法尋找具有最小尺寸的頂點(diǎn)覆蓋。一個(gè)端點(diǎn)在U中，另一個(gè)端點(diǎn)在V中的邊的數(shù)量是U所定義的切割（ c u t）的大小。編寫一個(gè)回溯算法，找出耗費(fèi)不超過c的機(jī)器構(gòu)成方案，使其重量最少。S的入度為0，每一條邊上的權(quán)給出了它所連接的兩點(diǎn)間的距離。壓力放大器可將壓力恢復(fù)至最大可允許的量級(jí)Pm a x。算法的復(fù)雜性是多少？22. [n 皇后問題] 在n 皇后問題中，我們希望在nn 的棋盤上找到一個(gè)n 皇后的放置方法以便任意兩個(gè)皇后之間不沖突。令ci 為皇后i 所處的列。2) 編寫一個(gè)回溯算法，搜索n 皇后問題的可行排列。*24. 使用排列空間樹來完成練習(xí)2 3。22。函數(shù)中的參數(shù)應(yīng)包括下列函數(shù)：產(chǎn)生節(jié)點(diǎn)的下一個(gè)孩子的函數(shù)，決定下一個(gè)孩子是否是可行的函數(shù)，計(jì)算該節(jié)點(diǎn)界限的函數(shù)，決定該界限值是否優(yōu)于另一個(gè)值的函數(shù)等。函數(shù)中的參數(shù)應(yīng)包含如下函數(shù)：確定一個(gè)節(jié)點(diǎn)是否可行的函數(shù)，計(jì)算該節(jié)點(diǎn)的界限值的函數(shù)，決定界限是否優(yōu)于另一個(gè)值的函數(shù)等。n 皇后問題的解空間因此被限制到[1, 2, ., n]的所有排列中。假定在任何可行的解決方案中，皇后i 被放置在棋盤的第i 排。在設(shè)置信號(hào)放大器問題中，需要放置最少數(shù)量的放大器，以便在遇到一個(gè)放大器之前汽油所走的距離不超過d。為了保證網(wǎng)絡(luò)的正常運(yùn)轉(zhuǎn)，在網(wǎng)絡(luò)傳輸中必須保證最小壓力Pm i n 。G中有一個(gè)稱為原點(diǎn)的頂點(diǎn)S。算法的復(fù)雜性是多少？20. [機(jī)器設(shè)計(jì)] 某機(jī)器由n 個(gè)部件組成，每一個(gè)部件可從3個(gè)投資者那里獲得。U是G中頂點(diǎn)的任意子集。U中頂點(diǎn)的數(shù)量是覆蓋的大小。編寫一個(gè)回溯算法以找到具有最小的最大長度的板排列。Ni 的長度為Ni 中第一塊和最后一塊電路板間的距離。要求使用1) 的結(jié)果得到一個(gè)更強(qiáng)的條件。y=iM i n O u txj 其中A(u,v)是邊(u,v)的耗費(fèi)。2) 使用上述界限作為b e s t c的初始值。14. 重寫最大完備子圖代碼（見程序1 6 1 0），把它作為類U N e t w o r k的成員?？梢孕薷腒 n a p : : B o u n d，使其返回被裝入背包的最后一個(gè)對象i，這樣可避免根據(jù)B o u n d重新向左移動(dòng)而可直接移動(dòng)到最左節(jié)點(diǎn)（原先由B o u n d確定）。在找到和為c1的子集之后展開遞歸，可以重構(gòu)出最優(yōu)解。8. 為子集之和問題寫一個(gè)遞歸回溯算法。練習(xí)4. 證明在兩船裝載問題中，只要存在一種方法能裝載所有貨箱，則通過盡可能裝滿第一艘船就可找到一種可行的裝載方法。delete [] 。for (int j = 1。[i] = 0。 = m + 1。 = B。}}程序1615 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。Swap(x[i], x[j])。 total[k] != now[k])l d + + 。 k = m。}else // 嘗試子樹for (int j = i。程序1614 搜索排列樹void Board::BestOrder(int i, int cd){// 按回溯算法搜索排列樹if (i == n) {for (int j = 1。程序1613 Board的類定義class Board {friend ArrangeBoards(int**, int, int, int [])。此外，產(chǎn)生排列的時(shí)間為O (n!) 且更新最優(yōu)排列的時(shí)間為O (m n)。這個(gè)節(jié)點(diǎn)的每一個(gè)孩子通過在當(dāng)前排列的末端增加一個(gè)電路板而擴(kuò)充了這個(gè)局部排列。當(dāng)i=n 時(shí)，表示所有的電路板已被放置且cd 為排列的密度。now[1:n] 被置為0，與一個(gè)空的局部排列相對應(yīng)。程序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。當(dāng)且僅當(dāng)n o w [ j ] 0且n o w [ j ]≠t o t a l [ j ]時(shí)，Nj 在插槽i 和i + 1之間有連線?；厮菟惴榱苏业阶顑?yōu)的電路板排列方式，將搜索一個(gè)排列空間。該間距必須保證足夠大以便容納相鄰插槽間的連線。對于圖1 6 9中的排列，d e n s i t y為2。例4 11 令n=8, m= 5。n個(gè)電路板的每一種排列定義了一種放置方法。cc = a[x[i1]][x[i]]。amp。bestc = cc + a[x[n1]][x[n]] + a[x[n]][1]。amp。通過使用加強(qiáng)的條件（練習(xí)1 6），能減少由tS P搜索的樹節(jié)點(diǎn)的數(shù)量。當(dāng)i＜n 時(shí)，檢查當(dāng)前i1 層節(jié)點(diǎn)的孩子節(jié)點(diǎn)，并且僅當(dāng)以下情況出現(xiàn)時(shí)，移動(dòng)到孩子節(jié)點(diǎn)之一：1) 有從x[i1] 到x[i] 的一條邊（如果是這樣的話， x [ 1 : i ]定義了網(wǎng)絡(luò)中的一條路徑）；2 )路徑x[1:i] 的耗費(fèi)小于當(dāng)前最優(yōu)解的耗費(fèi)。當(dāng)i=n 時(shí)，處在排列樹的葉節(jié)點(diǎn)的父節(jié)點(diǎn)上，并且需要驗(yàn)證從x[n1] 到x[n] 有一條邊，從x[n] 到起點(diǎn)x[1] 也有一條邊。delete [] x。bestc = NoEdge。程序1 6 11 旅行商回溯算法的預(yù)處理程序templateclass TT AdjacencyWDigraphT::TSP(int v[]){// 用回溯算法解決旅行商問題// 返回最優(yōu)旅游路徑的耗費(fèi)，最優(yōu)路徑存入v [ 1 : n ]/ /初始化x = new int [n+1]。t S P在排列空間樹中進(jìn)行遞歸回溯搜索， T S P是其一個(gè)必要的預(yù)處理過程。在其他例子中，有兩個(gè)成員函數(shù)： t S P和T S P。由于P e r m產(chǎn)生具有相同前綴的所有排列，因此可以容易地改造P e r m，使其不能產(chǎn)生具有不可行前綴（即該前綴沒有定義路徑）或不可能比當(dāng)前最優(yōu)旅行還優(yōu)的前綴的排列。return bestn。bestn = 0。 }if ( + n i bestn) {// 嘗試x[i] = 0x[i] = 0。 // 把i 加入完備子圖c n + + 。amp。 }// 在當(dāng)前完備子圖中檢查頂點(diǎn)i是否與其它頂點(diǎn)相連int OK = 1。 j = n。函數(shù)m a x C l i q u e（見程序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è)共享成員。當(dāng)試圖移動(dòng)到空間樹的i 層節(jié)點(diǎn)Z的左孩子時(shí)，需要證明從頂點(diǎn)i 到每一個(gè)其他的頂點(diǎn)j（xj = 1且j 在從根到Z的路徑上）有一條邊。當(dāng)