【正文】 ，也就解決了另一個問題。定義一個圖，圖中每個頂點表示一個網(wǎng)組。當試圖移動到空間樹的i 層節(jié)點Z的左孩子時，需要證明從頂點i 到每一個其他的頂點j（xj = 1且j 在從根到Z的路徑上）有一條邊。 j = n。amp。 }if ( + n i bestn) {// 嘗試x[i] = 0x[i] = 0。return bestn。在其他例子中，有兩個成員函數(shù)： t S P和T S P。程序1 6 11 旅行商回溯算法的預處理程序templateclass TT AdjacencyWDigraphT::TSP(int v[]){// 用回溯算法解決旅行商問題// 返回最優(yōu)旅游路徑的耗費，最優(yōu)路徑存入v [ 1 : n ]/ /初始化x = new int [n+1]。delete [] x。當i＜n 時，檢查當前i1 層節(jié)點的孩子節(jié)點，并且僅當以下情況出現(xiàn)時，移動到孩子節(jié)點之一：1) 有從x[i1] 到x[i] 的一條邊（如果是這樣的話， x [ 1 : i ]定義了網(wǎng)絡中的一條路徑）；2 )路徑x[1:i] 的耗費小于當前最優(yōu)解的耗費。amp。amp。n個電路板的每一種排列定義了一種放置方法。對于圖1 6 9中的排列，d e n s i t y為2?；厮菟惴榱苏业阶顑?yōu)的電路板排列方式，將搜索一個排列空間。程序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。當i=n 時，表示所有的電路板已被放置且cd 為排列的密度。此外，產(chǎn)生排列的時間為O (n!) 且更新最優(yōu)排列的時間為O (m n)。程序1614 搜索排列樹void Board::BestOrder(int i, int cd){// 按回溯算法搜索排列樹if (i == n) {for (int j = 1。 k = m。Swap(x[i], x[j])。 = B。[i] = 0。delete [] 。8. 為子集之和問題寫一個遞歸回溯算法?？梢孕薷腒 n a p : : B o u n d，使其返回被裝入背包的最后一個對象i，這樣可避免根據(jù)B o u n d重新向左移動而可直接移動到最左節(jié)點（原先由B o u n d確定）。2) 使用上述界限作為b e s t c的初始值。要求使用1) 的結(jié)果得到一個更強的條件。編寫一個回溯算法以找到具有最小的最大長度的板排列。U是G中頂點的任意子集。G中有一個稱為原點的頂點S。在設(shè)置信號放大器問題中，需要放置最少數(shù)量的放大器，以便在遇到一個放大器之前汽油所走的距離不超過d。n 皇后問題的解空間因此被限制到[1, 2, ., n]的所有排列中。函數(shù)中的參數(shù)應包括下列函數(shù)：產(chǎn)生節(jié)點的下一個孩子的函數(shù)，決定下一個孩子是否是可行的函數(shù)，計算該節(jié)點界限的函數(shù)，決定該界限值是否優(yōu)于另一個值的函數(shù)等。*24. 使用排列空間樹來完成練習2 3。令ci 為皇后i 所處的列。壓力放大器可將壓力恢復至最大可允許的量級Pm a x。編寫一個回溯算法，找出耗費不超過c的機器構(gòu)成方案，使其重量最少。編寫一個回溯算法尋找具有最小尺寸的頂點覆蓋。N2 的長度為2。amp。15. 令G為一個n 頂點的有向圖，M a xi 為從頂點i 出發(fā)的具有最大耗費的邊的耗費1) 證明旅行商的每一個旅行有一個小于n 229。10. 用迭代回溯算法求解0 / 1背包問題。6. 運用1 6 . 2 . 1節(jié)中第4小節(jié)的方法1) 來更新程序1 6 3，使其能得到時間復雜性O(shè) ( 2n )。 j++)[j] += B[i][j]。 i = m。 = new int [m+1]。// 僅當子樹中包含一個更優(yōu)的排列時，搜索該子樹if (ld bestd) {// 移動到孩子Swap(x[i], x[j])。 j++) {// 用x[j] 作為下一塊電路板對孩子進行嘗試// 在最后一個插槽更新并計算密度int ld = 0。int *x, // 到達當前節(jié)點的路徑* 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 。在排列樹的每一個節(jié)點處，函數(shù)B e s t O r d e r花費(m)的時間計算每一個孩子節(jié)點的密度。通常，(i,cd) 尋找最優(yōu)的局部排列x [ 1 : i 1 ]，該局部排列密度為c d。在插槽k和k + 1 ( 1≤k≤i ) 間的線密度的最大值給出了局部排列的密度。電路板排列問題的目標是找到一種電路板的排列方式，使其有最小的d e n s i t y。電路板xi 被放置到機箱的插槽i 中。}}} 電路板排列在大規(guī)模電子系統(tǒng)的設(shè)計中存在著電路板排列問題。 j = n。amp。在本例中，需要驗證是否該旅行是目前發(fā)現(xiàn)的最優(yōu)旅行。 // 使用數(shù)組v來存儲最優(yōu)路徑cc = 0。T S P見程序1 6 11。因此，考察時刪除特定的前綴等價于搜索期間不進入相應的子樹。// 尋找最大完備子圖m a x C l i q u e ( 1 ) 。x[i] = 0。 j i。M a x c l i q u e ( v )的執(zhí)行返回最大完備子圖的尺寸，同時它也設(shè)置整型數(shù)組v，當且僅當頂點i 不是所找到的最大完備子圖的一個成員時，v [ i ] = 0。兩個問題都可使用子集解空間樹（如圖1 6 2所示）。3 . 2節(jié)考察了如何找到一個具有最大尺寸的互不交叉的網(wǎng)組的集合問題。類似地，最大獨立集問題是指尋找圖G的一個最大獨立集。例49 圖167b 是圖167a 的補圖，反之亦然。例48 在圖167a 中，子集{ 1 , 2 }定義了一個尺寸為2的完全子圖。delete [] Q。 i++) {[i] = p[Q[i1].ID]。W += w[i]。程序169 程序1 6 7的預處理代碼templateclass Tw, class TpTp Knapsack(Tp p[], Tw w[], Tw c, int n){// 返回最優(yōu)裝包的值// 初始化Tw W = 0。注意定義操作符 =是為了使歸并排序程序（見程序1 4 3）能按密度遞減的順序排序。 }// 檢查子樹if (cw + w[i] = c) {//嘗試x[i] = 1cw += w[i]。amp。 // 對象重量的數(shù)組Tp *p。同時注意僅當向右孩子移動時，限界函數(shù)才被計算。當對象按密度遞減的順序被考慮時，對象4先被裝入，然后是對象3。因此，子樹A的最優(yōu)解的收益值至多為2 2。被構(gòu)造的解為x= [ 1 , 0 . 2 , 1 , 1 ]，相應的收益值為2 2。一種決定是否要移動到右子樹的簡單方法是令r 為還未遍歷的對象的收益之和，將r 加到c p（當前節(jié)點所獲收益）之上，若（ r + c p）≤b e s t p（目前最優(yōu)解的收益），則不需搜索右子樹。}}} 0/1背包問題0 / 1背包問題是一個N P復雜問題，為了解決該問題，在1 . 4節(jié)采用了貪婪算法，在3 . 2節(jié)又采用了動態(tài)規(guī)劃算法。amp。 j = n。 j++)r += w[j]。不像遞歸代碼，這種代碼在檢查是否該向右孩子移動之前就移動到了右孩子。如例4 5所示，從解空間樹的任何節(jié)點，算法不斷向左孩子移動，直到不能再移動為止。然后運行程序1 6 3的一個修改版本。}這段代碼在L o a d i n g中增加了兩個私有數(shù)據(jù)成員： x 和b e s t x。 = 0。 }r += w[i]。 return。}4. 尋找最優(yōu)子集為了確定具有最接近c 的重量的貨箱子集，有必要增加一些代碼來記錄當前找到的最優(yōu)子集。 = 0。m a x L o a d i n g ( i + 1 ) 。新的代碼不必檢查是否一個到達的葉節(jié)點有比當前最優(yōu)解還優(yōu)的重量值。bestw 被置為1 0。這個函數(shù)使用的遞歸?？臻g為(n)。當移動到左孩子時， cw 被置為c w + w [ i ]，且到達一個i + 1層的節(jié)點。 = 0。m a x L o a d i n g ( i + 1 ) 。程序161 第一種回溯算法templateclass Tclass Loading {friend MaxLoading(T [], T, int)。算法將移動到C并搜索它的子樹。從E，再次沿著樹向下移動到節(jié)點K，此時c w= 8。從節(jié)點B不能移動到節(jié)點D，因為c w+w2 c1。若c wc1，則以O(shè)為根的子樹不能產(chǎn)生一個可行的解答。用元組方法所需時間為O ( m i n {c1 , 2 n }）。所以不能期望在多項式時間內(nèi)解決兩艘船的裝載問題。如果w= [ 2 0 , 4 0 , 4 0 ]，則無法將貨箱全部裝船。 貨箱裝船1. 問題在1 . 3節(jié)中，考察了用最大數(shù)量的貨箱裝船的問題。3. 每周六， Mary 和Joe 都在一起打乒乓球。練習1. 考察如下0 / 1背包問題：n= 4，w= [ 2 0 , 2 5 , 1 5 , 3 5 ]，p= [ 4 0 , 4 9 , 2 5 , 6 0 ]，c= 6 2。小結(jié)回溯方法的步驟如下：1) 定義一個解空間，它包含問題的解。當要求解的問題需要根據(jù)一個n 元素的排列來優(yōu)化某些函數(shù)時，解空間樹被稱作排列樹（permutation tree）。這個旅行1 , 3 , 2 , 4 , 1的耗費是2 5，比當前的最佳旅行好，把它作為當前的最好旅行。在L點，旅行1 , 2 , 3 , 4 , 1作為當前最好的旅行被記錄下來?？赡艿穆眯锌捎靡粋€樹來描述，其中每一個從根到葉的路徑定義了一個旅行。在下一個循環(huán)中，又采用了同樣的生產(chǎn)順序。這些孔由一個機器鉆頭來鉆，它從起始位置開始，移動到每一個鉆孔位置鉆孔，然后回到起始位置。故1 , 3 , 2 , 4 , 1是該網(wǎng)絡中最小耗費的旅行。例43 [旅行商問題] 在這個問題中，給出一個n 頂點網(wǎng)絡（有向或無向），要求找出一個包含所有n 個頂點的具有最小耗費的環(huán)路。在F，r= 1 5，c p= 2 5。這個路徑（ A , B , E , K）也是此時的活節(jié)點序列。E變成新的E節(jié)點。從根節(jié)點開始搜索圖1 6 2中的樹。在這個位置也沒有可行的移動，故這個節(jié)點也死亡了。迷宮當前狀態(tài)如圖163b 所示。我們將利用圖1 6 1給出的解空間圖來搜索迷宮。一旦定義了解空間的組織方法，這個空間即可按深度優(yōu)先的方法從開始節(jié)點進行搜索。下一步是組織解空間以便它能被容易地搜索。因此，這些方法通常能夠用來求解規(guī)模很大的問題。理論上，當候選解數(shù)量有限并且通過檢查所有或部分候選解能夠得到所需解時，上述方法是可行的。1 算法思想從( 1 , 1 )點到( 3 , 3 )點的每一條路徑都定義了33迷宮解空間中的一個元素，但由于障礙的設(shè)置，有些路徑是不可行的。從E節(jié)點可移動到一個新節(jié)點。搜索從點( 1 , 1 )開始，該點是目前唯一的活節(jié)點，它也是一個E節(jié)點。在圖1 6 1中從當前E節(jié)點開始有3個可能的移動，其中兩個是不可行的，因為迷宮在這些位置上的值為1。現(xiàn)在活節(jié)點為( 1 , 1 )，( 2 , 1 )。B是當前E節(jié)點。從E，有兩種可能移動（到J 和K），到J 的移動是不可行的，而到K的移動是可行的。它可被進一步擴充，到達節(jié)點C。此時r= 0，c p= 5 0。圖1 6 4給出了一個四頂點網(wǎng)絡。邊的耗費給出了在兩個城市旅行所需的時間（或花費）。然而，鉆頭移動時間是鉆頭移動距離的函數(shù)。雖然生產(chǎn)產(chǎn)品的花費獨立于產(chǎn)品生產(chǎn)順序，但循環(huán)中從生產(chǎn)一個產(chǎn)品轉(zhuǎn)變到生產(chǎn)另一個產(chǎn)品的花費卻與順序有關(guān)。例如，到節(jié)點L的路徑表示了旅行1 , 2 , 3 , 4 , 1，而到節(jié)點O的路徑表示了旅行1 , 3 , 4 , 2 , 1。由于F沒有未被檢查的孩子，所以它成為死節(jié)點，回溯到C點。如此繼續(xù)下去，可搜索完整個樹，得出1 , 3 , 2 , 4 , 1是最少耗費的旅行。通過確定一個新近到達的節(jié)點能否導致一個比當前最優(yōu)解還要好的解，可加速對最優(yōu)解的搜索?；厮菟惴ǖ囊粋€有趣的特性是在搜索執(zhí)行的同時產(chǎn)生解空間。確定回溯算法未遍歷的節(jié)點。然后她們需要從球桌周圍拾起2 4 0個球，放入各自的籃子。第一艘船的載重量是c1，第二艘船的載重量是c2，wi 是貨箱i 的重量且n 229。當c1=c2 且n 229。這個選擇可通過求解0 / 1背包問題來實現(xiàn)，即尋找m ax (n 229。可用深度優(yōu)先的方法搜索該解空間以求得最優(yōu)解。例45 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = 1 2。J的左孩子的c w值為1 3，超出了c1，故搜索不能移動到J的左孩子。結(jié)果確實大于最優(yōu)值，所以這個葉節(jié)點表