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