【正文】 ., vn , 1來描述，v2 , ., vn 是(2, 3, ., n) 的一個排列。在一個循環(huán)中，所有n 個產(chǎn)品被順序生產(chǎn)出來，然后再開始下一個循環(huán)?？椎奈恢靡阎Ｂ眯? , 2 , 4 , 3 , 1的耗費為6 6；而1 , 3 , 2 , 4 , 1的耗費為2 5；1 , 4 , 3 , 2 , 1為5 9。在搜索期間發(fā)現(xiàn)的最優(yōu)解即為最后的解。F變?yōu)樾碌腅節(jié)點并且活節(jié)點為A, C,F。x 的值由從根到K的路徑來決定。到E的移動是可行的，因為在這個移動中沒有占用任何容量。例42 [0/1背包問題] 考察如下背包問題：n= 3，w= [ 2 0 , 1 5 , 1 5 ]，p= [ 4 0 , 2 5 , 2 5 ]且c= 3 0。所以E節(jié)點( 1 , 3 )死亡，回溯到最近被檢查的活節(jié)點( 1 , 2 )。假定選擇移動到( 1 , 2 )，m a z e( 1 , 2 )被置為1以避免再次經(jīng)過該點。例41 [迷宮老鼠] 考察圖163a 的矩陣中給出的33的“迷宮老鼠”問題。根據(jù)w 和c 的值，從根到葉的路徑中的一些解或全部解可能是不可行的。當(dāng)n= 3時，解空間為{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 , 0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 , 1 ) }。事實上，這些方法可以使我們避免對很大的候選解集合進(jìn)行檢查，同時能夠保證算法運(yùn)行結(jié)束時可以找到所需要的解。不過，在實際應(yīng)用中，很少使用這種方法，因為候選解的數(shù)量通常都非常大（比如指數(shù)級，甚至是大數(shù)階乘），即便采用最快的計算機(jī)也只能解決規(guī)模很小的問題?；厮荩╞ a c k t r a c k i n g）是一種系統(tǒng)地搜索問題解答的方法。圖1 6 2用樹形結(jié)構(gòu)給出了含三個對象的0 / 1背包問題的解空間。如果能從當(dāng)前的E節(jié)點移動到一個新節(jié)點，那么這個新節(jié)點將變成一個活節(jié)點和新的E節(jié)點，舊的E節(jié)點仍是一個活節(jié)點。為避免再次走過這個位置，置m a z e( 1 , 1 )為1。唯一可行的移動是( 1 , 3 )。繼續(xù)下去，能到達(dá)點( 3 , 3 )。在節(jié)點B，剩下的容量r 為1 0，而收益c p 為4 0。節(jié)點K變成了新的E節(jié)點。此時r= 3 0，c p= 0。既然L是一個葉節(jié)點，它表示了一個比目前找到的最優(yōu)解（即節(jié)點K）更好的可行解，我們把這個解作為最優(yōu)解。在這個網(wǎng)絡(luò)中，一些旅行如下： 1 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 1和1 , 4 , 3 , 2 , 1。旅行表示當(dāng)旅行商游覽了所有城市再回到出發(fā)點時所走的路線。因此，希望找到最短的移動路徑。為了使耗費最小化，可以定義一個有向圖，圖中的頂點表示產(chǎn)品，邊＜(i , j)＞上的耗費值為生產(chǎn)過程中從產(chǎn)品i 轉(zhuǎn)變到產(chǎn)品j 所需的耗費。網(wǎng)絡(luò)中的每一個旅行都由樹中的一條從根到葉的確定路徑來表示。C變?yōu)镋節(jié)點，向前移動到G，然后是M。當(dāng)要求解的問題需要根據(jù)n 個元素的一個子集來優(yōu)化某些函數(shù)時，解空間樹被稱作子集樹（subset tree）。如果不能，則移動到該節(jié)點的任何一個子樹都是無意義的，這個節(jié)點可被立即殺死，用來殺死活節(jié)點的策略稱為限界函數(shù)（ bounding function）。在搜索期間的任何時刻，僅保留從開始節(jié)點到當(dāng)前E節(jié)點的路徑。2. 1) 當(dāng)n= 5時，畫出旅行商問題的解空間樹。Mary 只拾她這邊的球，而Joe 拾剩下的球。i = 1wi≤c1+c2。i = 1wi＝2c1 時，兩艘船的裝載問題等價于分割問題（ partition problem），即有n個數(shù)字ai , ( 1≤i≤n)，要求找到一個子集（若存在的話），使得子集之和為( n 229。i = 1wi xi )，其中n 229。使用限界函數(shù)去阻止不可能獲得解答的節(jié)點的擴(kuò)張。解空間樹為圖1 6 2的樹再加上一層節(jié)點?？梢苿拥絁的右孩子，它是一個葉節(jié)點。到該節(jié)點的路徑?jīng)Q定了x 的值[ 1 , 0 , 0 , 1 ]。M a x L o a d i n g調(diào)用了一個遞歸函數(shù)m a x L o a d i n g，它是類L o a d i n g的一個成員，定義L o a d i n g類是為了減少M a x L o a d i n g中的參數(shù)個數(shù)。 // 目前最優(yōu)裝載的重量} 。// 初始化X = w。被葉節(jié)點定義的解答有重量c w，它一定≤c，因為搜索不會移動到不可行的節(jié)點。既然這個子樹表示x [ i ] = 0的情況，所以無需進(jìn)行可行性檢查就可移動到該子樹，因為一個可行節(jié)點的右孩子總是可行的。j = i + 1w[ j ] 為剩余貨箱的重量。同樣，不必移動到右孩子C，因為在C點c w = 0，r = 11且c w + r≤b e s t w。程序162 程序1 6 1的優(yōu)化templateclass Tvoid LoadingT::maxLoading(int i){// // 從第i 層節(jié)點搜索if (i n) {// 在葉節(jié)點上bestw = cw。}templateclass TT MaxLoading(T w[], T c, int n){// 返回最優(yōu)裝載的重量LoadingT X。 i = n。程序163 給出最優(yōu)裝載的代碼templateclass Tvoid LoadingT::maxLoading(int i){ / /從第i 層節(jié)點搜索if (i n) {// 在葉節(jié)點上for (int j = 1。m a x L o a d i n g ( i + 1 ) 。 = c。 i++) += w[i]。為1的xi 值確定了要被裝載的貨箱。按照這種方法，算法每次回溯一級，并在b e s t x中存儲一個x [ i ]。這個節(jié)點有一個特性，即它是路徑中具有x [ i ] = 1的節(jié)點中離根節(jié)點最近的節(jié)點。 // 當(dāng)前節(jié)點的層次// x[1:i1] 是到達(dá)當(dāng)前節(jié)點的路徑int *x = new int [n+1]。cw += w[i]。x[i] = 0。return bestw。首先形成一個遞歸算法，去找到可獲得的最大收益。當(dāng)背包以密度遞減的順序被填充時，對象4首先被填充，然后是對象對象1。當(dāng)位于解空間樹的節(jié)點B時，x1= 1，目前獲益為c p= 9。這樣產(chǎn)生出收益值1 9。假定已經(jīng)做了這樣的排序。void Knapsack(int i)。 // 迄今最大的收益} 。}// 取下一個對象的一部分if (i = n) b += p[i]/w[i] * cleft。cp = p[i]。 // 對象號float d。 i = n。 = new Tp [n+1]。 = c。} 最大完備子圖令U為無向圖G的頂點的子集，當(dāng)且僅當(dāng)對于U中的任意點u 和v，(u , v)是圖G的一條邊時，U定義了一個完全子圖（plete subgraph）。當(dāng)且僅當(dāng)對于U中任意點u 和v，(u , v) 不是G的一條邊時，U定義了一個空子圖。如果U定義了G的一個完全子圖，則它也定義了的一個空子圖，反之亦然。例410 假定有一個n 個動物構(gòu)成的集合。所以該圖的一個最大獨立集對應(yīng)于非交叉網(wǎng)組的一個最大尺寸的子集?；厮菟惴勺鳛轭怉 d j a c e n c y G r a p h（見程序1 2 4）的一個成員來實現(xiàn)，為此首先要在該類中加入私有靜態(tài)成員x（整型數(shù)組，用于存儲到當(dāng)前節(jié)點的路徑），b e s t x（整型數(shù)組，保存目前的最優(yōu)解），b e s t n（b e s t x中點的數(shù)量），c n（x 中點的數(shù)量）。bestn = 。b r e a k 。 }}int AdjacencyGraph::MaxClique(int v[]){// 返回最大完備子圖的大小// 完備子圖的頂點放入v [ 1 : n ]// 初始化x = new int [n+1]。這樣的樹可用函數(shù)P e r m (見程序1 1 0 )搜索，并可生成元素表的所有排列。函數(shù)G . T S P ( v )返回最少耗費旅行的花費，旅行自身由整型數(shù)組v 返回。 i = n。}函數(shù)t S P見程序1 6 1 2。每次找到一個更好的旅行時，除了更新bestx 的耗費外， tS P需耗時O ( (n 1 ) ! )。 j = n。cc += a[x[i1]][x[i]]。m個網(wǎng)組集合L= {N1,., Nm }由電路板定義，Ni 是B的子集，子集中的元素需要連接起來。插槽6和7之間無電線，余下的相鄰插槽都只有一根電線。令t o t a l [ j ]為Nj 中電路板的數(shù)量。ArrangeBoards 創(chuàng)建類Board 的一個成員x 并初始化與之相關(guān)的變量。當(dāng)in 時，排列還未被完成。所以更新的次數(shù)是O (m)。 j++)bestx[j] = x[j]。if (now[k] 0 amp。 k = m。 = m。 i = n。delete [] 。沒有必要記住目前的最優(yōu)解。12. 改寫程序1 6 1 0，使其首先按度的遞減次序來排列各頂點。16. 令G為具有n 個頂點的有向圖， M i n O u ti 為從頂點i 出發(fā)的具有最小耗費的邊的耗費1) 證明具有前綴x1 到xi 的旅行商的所有旅行耗費至少為i 229。3) 測試t S P的新版本。18. [頂點覆蓋] 令G為一個無向圖。一個端點在U中，另一個端點在V中的邊的數(shù)量是U所定義的切割（ c u t）的大小。S的入度為0，每一條邊上的權(quán)給出了它所連接的兩點間的距離。算法的復(fù)雜性是多少？22. [n 皇后問題] 在n 皇后問題中，我們希望在nn 的棋盤上找到一個n 皇后的放置方法以便任意兩個皇后之間不沖突。2) 編寫一個回溯算法，搜索n 皇后問題的可行排列。22。函數(shù)中的參數(shù)應(yīng)包含如下函數(shù)：確定一個節(jié)點是否可行的函數(shù)，計算該節(jié)點的界限值的函數(shù)，決定界限是否優(yōu)于另一個值的函數(shù)等。假定在任何可行的解決方案中，皇后i 被放置在棋盤的第i 排。為了保證網(wǎng)絡(luò)的正常運(yùn)轉(zhuǎn)，在網(wǎng)絡(luò)傳輸中必須保證最小壓力Pm i n 。算法的復(fù)雜性是多少？20. [機(jī)器設(shè)計] 某機(jī)器由n 個部件組成，每一個部件可從3個投資者那里獲得。U中頂點的數(shù)量是覆蓋的大小。Ni 的長度為Ni 中第一塊和最后一塊電路板間的距離。y=iM i n O u txj 其中A(u,v)是邊(u,v)的耗費。14. 重寫最大完備子圖代碼（見程序1 6 1 0），把它作為類U N e t w o r k的成員。在找到和為c1的子集之后展開遞歸，可以重構(gòu)出最優(yōu)解。練習(xí)4. 證明在兩船裝載問題中，只要存在一種方法能裝載所有貨箱，則通過盡可能裝滿第一艘船就可找到一種可行的裝載方法。for (int j = 1。 = m + 1。}}程序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。 total[k] != now[k])l d + + 。}else // 嘗試子樹for (int j = i。程序1613 Board的類定義class Board {friend ArrangeBoards(int**, int, int, int [])。這個節(jié)點的每一個孩子通過在當(dāng)前排列的末端增加一個電路板而擴(kuò)充了這個局部排列。now[1:n] 被置為0，與一個空的局部排列相對應(yīng)。當(dāng)且僅當(dāng)n o w [ j ] 0且n o w [ j ]≠t o t a l [ j ]時，Nj 在插槽i 和i + 1之間有連線。該間距必須保證足夠大以便容納相鄰插槽間的連線。例4 11 令n=8, m= 5。cc = a[x[i1]][x[i]]。bestc = cc + a[x[n1]][x[n]] + a[x[n]][1]。通過使用加強(qiáng)的條件（練習(xí)1 6），能減少由tS P搜索的樹節(jié)點的數(shù)量。當(dāng)i=n 時，處在排列樹的葉節(jié)點的父節(jié)點上，并且需要驗證從x[n1] 到x[n] 有一條邊，從x[n] 到起點x[1] 也有一條邊。bestc = NoEdge。t S P在排列空間樹中進(jìn)行遞歸回溯搜索， T S P是其一個必要的預(yù)處理過程。由于P e r m產(chǎn)生具有相同前綴的所有排列，因此可以容易地改造P e r m，使其不能產(chǎn)生具有不可行前綴（即該前綴沒有定義路徑）或不可能比當(dāng)前最優(yōu)旅行還優(yōu)的前綴的排列。bestn = 0。 // 把i 加入完備子圖c n + + 。 }// 在當(dāng)前完備子圖中檢查頂點i是否與其它頂點相連int OK = 1。函數(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的一個私有成