尋找問題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個，在檢查完所有或部分候選解后，即可找到所需要的解。理論上，當候選解數量有限并且通過檢查所有或部分候選解能夠得到所需解時，上述方法是可行的。不過，在實際應用中，很少使用這種方法，因為候選解的數量通常都非常大（比如指數級，甚至是大數階乘），即便采用最快的計算機也只能解決規模很小的問題。對候選解進行系統檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方法。按照這兩種方法對候選解進行系統檢查通常會使問題的求解時間大大減少（無論對于最壞情形還是對于一般情形）。事實上，這些方法可以使我們避免對很大的候選解集合進行檢查，同時能夠保證算法運行結束時可以找到所需要的解。因此，這些方法通常能夠用來求解規模很大的問題。
本章集中闡述回溯方法，這種方法被用來設計貨箱裝船、背包、最大完備子圖、旅行商和電路板排列問題的求解算法。
4.1 算法思想
回溯（b a c k t r a c k i n g）是一種系統地搜索問題解答的方法。為了實現回溯，首先需要為問題定義一個解空間（ solution space），這個空間必須至少包含問題的一個解（可能是最優的）。在迷宮老鼠問題中，我們可以定義一個包含從入口到出口的所有路徑的解空間；在具有n 個對象的0 / 1背包問題中（見1 . 4節和2 . 2節），解空間的一個合理選擇是2n 個長度為n 的0 / 1向量的集合，這個集合表示了將0或1分配給x的所有可能方法。當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 ) }。
下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖或樹。圖1 6 - 1用圖的形式給出了一個3×3迷宮的解空間。從( 1 , 1 )點到( 3 , 3 )點的每一條路徑都定義了3×3迷宮解空間中的一個元素，但由于障礙的設置，有些路徑是不可行的。
圖1 6 - 2用樹形結構給出了含三個對象的0 / 1背包問題的解空間。從i 層節點到i+ 1層節點的一條邊上的數字給出了向量x 中第i個分量的值xi ，從根節點到葉節點的每一條路徑定義了解空間中的一個元素。從根節點A到葉節點H的路徑定義了解x= [ 1 , 1 , 1 ]。根據w 和c 的值，從根到葉的路徑中的一些解或全部解可能是不可行的。
一旦定義了解空間的組織方法，這個空間即可按深度優先的方法從開始節點進行搜索。在迷宮老鼠問題中，開始節點為入口節點( 1 , 1 )；在0 / 1背包問題中，開始節點為根節點A。開始節點既是一個活節點又是一個E-節點（expansion node）。從E-節點可移動到一個新節點。如果能從當前的E-節點移動到一個新節點，那么這個新節點將變成一個活節點和新的E-節點，舊的E-節點仍是一個活節點。如果不能移到一個新節點，當前的E-節點就“死”了（即不再是一個活節點），那么便只能返回到最近被考察的活節點（回溯），這個活節點變成了新的E-節點。當我們已經找到了答案或者回溯盡了所有的活節點時，搜索過程結束。
例4-1 [迷宮老鼠] 考察圖16-3a 的矩陣中給出的3×3的“迷宮老鼠”問題。我們將利用圖1 6 -1給出的解空間圖來搜索迷宮。
從迷宮的入口到出口的每一條路徑都與圖1 6 - 1中從( 1 , 1 )到( 3 , 3 )的一條路徑相對應。然而，圖1 6 - 1中有些從( 1 , 1 )到( 3 , 3 )的路徑卻不是迷宮中從入口到出口的路徑。搜索從點( 1 , 1 )開始，該點是目前唯一的活節點，它也是一個E-節點。為避免再次走過這個位置，置m a z e( 1 , 1 )為1。從這個位置，能移動到( 1 , 2 )或( 2 , 1 )兩個位置。對于本例，兩種移動都是可行的，因為在每一個位置都有一個值0。假定選擇移動到( 1 , 2 )，m a z e( 1 , 2 )被置為1以避免再次經過該點。迷宮當前狀態如圖16-3b 所示。這時有兩個活節點(1,1) (1,2)。( 1 , 2 )成為E-節點。
在圖1 6 - 1中從當前E-節點開始有3個可能的移動，其中兩個是不可行的，因為迷宮在這些位置上的值為1。唯一可行的移動是( 1 , 3 )。移動到這個位置，并置m a z e( 1 , 3 )為1以避免再次經過該點，此時迷宮狀態為1 6 - 3 c。圖1 6 - 1中，從( 1 , 3 )出發有兩個可能的移動，但沒有一個是可行的。所以E-節點( 1 , 3 )死亡，回溯到最近被檢查的活節點( 1 , 2 )。在這個位置也沒有可行的移動，故這個節點也死亡了。唯一留下的活節點是( 1 , 1 )。這個節點再次變為E-節點，它可移動到( 2 , 1 )。現在活節點為( 1 , 1 )，( 2 , 1 )。繼續下去，能到達點( 3 , 3 )。此時，活節點表為( 1 , 1 )，( 2 , 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，這即是到達出口的路徑。
程序5 - 1 3是一個在迷宮中尋找路徑的回溯算法。
例4-2 [0/1背包問題] 考察如下背包問題：n= 3，w= [ 2 0 , 1 5 , 1 5 ]，p= [ 4 0 , 2 5 , 2 5 ]且c= 3 0。從根節點開始搜索圖1 6 - 2中的樹。根節點是當前唯一的活節點，也是E-節點，從這里能夠移動到B或C點。假設移動到B，則活節點為A和B。B是當前E-節點。在節點B，剩下的容量r 為1 0，而收益c p 為4 0。從B點，能移動到D或E。移到D是不可行的，因為移到D所需的容量w2 為1 5。到E的移動是可行的，因為在這個移動中沒有占用任何容量。E變成新的E-節點。這時活節點為A , B , E。在節點E，r= 1 0，c p= 4 0。從E，有兩種可能移動（到J 和K），到J 的移動是不可行的，而到K的移動是可行的。節點K變成了新的E-節點。因為K是一個葉子，所以得到一個可行的解。這個解的收益為c p= 4 0。x 的值由從根到K的路徑來決定。這個路徑（ A , B , E , K）也是此時的活節點序列。既然不能進一步擴充K，K節點死亡，回溯到E，而E也不能進一步擴充，它也死亡了。接著，回溯到B，它也死亡了，A再次變為E-節點。它可被進一步擴充，到達節點C。此時r= 3 0，c p= 0。從C點能夠移動到F或G。假定移動到F。F變為新的E-節點并且活節點為A, C,F。在F，r= 1 5，c p= 2 5。從F點，能移動到L或M。假定移動到L。此時r= 0，c p= 5 0。既然L是一個葉節點，它表示了一個比目前找到的最優解（即節點K）更好的可行解，我們把這個解作為最優解。節點L死亡，回溯到節點F。繼續下去，搜索整棵樹。在搜索期間發現的最優解即為最后的解。
例4-3 [旅行商問題] 在這個問題中，給出一個n 頂點網絡（有向或無向），要求找出一個包含所有n 個頂點的具有最小耗費的環路。任何一個包含網絡中所有n 個頂點的環路被稱作一個旅行（t o u r）。在旅行商問題中，要設法找到一條最小耗費的旅行。
圖1 6 - 4給出了一個四頂點網絡。在這個網絡中，一些旅行如下： 1 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 1和1 , 4 , 3 , 2 , 1。旅行2 , 4 , 3 , 1 , 2；4 , 3 , 1 , 2 , 4和3 , 1 , 2 , 4 , 3和旅行1 , 2 , 4 , 3 , 1一樣。而旅行1 , 3 , 4 , 2 , 1是旅行1 , 2 , 4 , 3 , 1的“逆”。旅行1 , 2 , 4 , 3 , 1的耗費為6 6；而1 , 3 , 2 , 4 , 1的耗費為2 5；1 , 4 , 3 , 2 , 1為5 9。故1 , 3 , 2 , 4 , 1是該網絡中最小耗費的旅行。
顧名思義，旅行商問題可被用來模擬現實生活中旅行商所要旅行的地區問題。頂點表示旅行
商所要旅行的城市（包括起點）。邊的耗費給出了在兩個城市旅行所需的時間（或花費）。旅行表示當旅行商游覽了所有城市再回到出發點時所走的路線。
旅行商問題還可用來模擬其他問題。假定要在一個金屬薄片或印刷電路板上鉆許多孔。孔的位置已知。這些孔由一個機器鉆頭來鉆，它從起始位置開始，移動到每一個鉆孔位置鉆孔，然后回到起始位置。總共花的時間是鉆所有孔的時間與鉆頭移動的時間。鉆所有孔所需的時間獨立于鉆孔順序。然而，鉆頭移動時間是鉆頭移動距離的函數。因此，希望找到最短的移動路徑。
另有一個例子，考察一個批量生產的環境，其中有一個特殊的機器可用來生產n 個不同的產品。利用一個生產循環不斷地生產這些產品。在一個循環中，所有n 個產品被順序生產出來，然后再開始下一個循環。在下一個循環中，又采用了同樣的生產順序。例如，如果這臺機器被用來順序為小汽車噴紅、白、藍漆，那么在為藍色小汽車噴漆之后，我們又開始了新一輪循環，為紅色小汽車噴漆，然后是白色小汽車、藍色小汽車、紅色小汽車，..，如此下去。一個循環的花費包括生產一個循環中的產品所需的花費以及循環中從一個產品轉變到另一個產品的花費。雖然生產產品的花費獨立于產品生產順序，但循環中從生產一個產品轉變到生產另一個產品的花費卻與順序有關。為了使耗費最小化，可以定義一個有向圖，圖中的頂點表示產品，邊＜(i , j)＞上的耗費值為生產過程中從產品i 轉變到產品j 所需的耗費。一個最小耗費的旅行定義了一個最小耗費的生產循環。
既然旅行是包含所有頂點的一個循環，故可以把任意一個點作為起點（因此也是終點）。
針對圖1 6 - 4，任意選取點1作為起點和終點，則每一個旅行可用頂點序列1, v2 ,., vn , 1來描述，
v2 , ., vn 是(2, 3, ., n) 的一個排列。可能的旅行可用一個樹來描述，其中每一個從根到葉的路
徑定義了一個旅行。圖1 6 - 5給出了一棵表示四頂點網絡的樹。從根到葉的路徑中各邊的標號定義了一個旅行（還要附加1作為終點）。例如，到節點L的路徑表示了旅行1 , 2 , 3 , 4 , 1，而到節點O的路徑表示了旅行1 , 3 , 4 , 2 , 1。網絡中的每一個旅行都由樹中的一條從根到葉的確定路徑來表示。因此，樹中葉的數目為(n- 1 )！。
回溯算法將用深度優先方式從根節點開始，通過搜索解空間樹發現一個最小耗費的旅行。對圖1 6 - 4的網絡，利用圖1 6 - 5的解空間樹，一個可能的搜索為A B C F L。在L點，旅行1 , 2 , 3 , 4 , 1作為當前最好的旅行被記錄下來。它的耗費是5 9。從L點回溯到活節點F。由于F沒有未被檢查的孩子，所以它成為死節點，回溯到C點。C變為E-節點，向前移動到G，然后是M。這樣構造出了旅行1 , 2 , 4 , 3 , 1，它的耗費是6 6。既然它不比當前的最佳旅行好，拋棄它并回溯到G，然后是C , B。從B點，搜索向前移動到D，然后是H , N。這個旅行1 , 3 , 2 , 4 , 1的耗費是2 5，比當前的最佳旅行好，把它作為當前的最好旅行。從N點，搜索回溯到H，然后是D。在D點，再次向前移動，到達O點。如此繼續下去，可搜索完整個樹，得出1 , 3 , 2 , 4 , 1是最少耗費的旅行。
當要求解的問題需要根據n 個元素的一個子集來優化某些函數時，解空間樹被稱作子集樹（subset tree）。所以對有n 個對象的0 / 1背包問題來說，它的解空間樹就是一個子集樹。這樣一棵樹有2n 個葉節點，全部節點有2n+ 1－1個。因此，每一個對樹中所有節點進行遍歷的算法都必須耗時W ( 2n )。當要求解的問題需要根據一個n 元素的排列來優化某些函數時，解空間樹被稱作排列樹（permutation tree）。這樣的樹有n! 個葉節點，所以每一個遍歷樹中所有節點的算法都必須耗時W (n! )。圖1 6 - 5中的樹是頂點{ 2 , 3 , 4 }的最佳排列的解空間樹，頂點1是旅行的起點和終點。
通過確定一個新近到達的節點能否導致一個比當前最優解還要好的解，可加速對最優解的搜索。如果不能，則移動到該節點的任何一個子樹都是無意義的，這個節點可被立即殺死，用來殺死活節點的策略稱為限界函數（ bounding function）。在例1 6 - 2中，可使用如下限界函數：殺死代表不可行解決方案的節點；對于旅行商問題，可使用如下限界函數：如果目前建立的部分旅行的耗費不少于當前最佳路徑的耗費，則殺死當前節點。如果在圖1 6 - 4的例子中使用該限界函數，那么當到達節點I時，已經找到了具有耗費2 5的1 , 3 , 2 , 4 , 1的旅行。在節點I，部分旅行1 , 3 , 4的耗費為2 6，若旅行通過該節點，那么不能找到一個耗費小于2 5的旅行，故搜索以I為根節點的子樹毫無意義。
小結
回溯方法的步驟如下：
1) 定義一個解空間，它包含問題的解。
2) 用適于搜索的方式組織該空間。
3) 用深度優先法搜索該空間，利用限界函數避免移動到不可能產生解的子空間。
回溯算法的一個有趣的特性是在搜索執行的同時產生解空間。在搜索期間的任何時刻，僅保留從開始節點到當前E-節點的路徑。因此，回溯算法的空間需求為O（從開始節點起最長路徑的長度）。這個特性非常重要，因為解空間的大小通常是最長路徑長度的指數或階乘。所以如果要存儲全部解空間的話，再多的空間也不夠用。
練習
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。
1) 畫出該0 / 1背包問題的解空間樹。
2) 對該樹運用回溯算法（利用給出的p s , w s , c值），依回溯算法遍歷節點的順序標記節點。確定回溯算法未遍歷的節點。
2. 1) 當n= 5時，畫出旅行商問題的解空間樹。
2) 在該樹上，運用回溯算法（使用圖1 6 - 6的例子）。依回溯算法遍歷節點的順序標記節點。確定未被遍歷的節點。
3. 每周六， Mary 和Joe 都在一起打乒乓球。她們每人都有一個裝有1 2 0個球的籃子。
這樣一直打下去，直到兩個籃子為空。然后她們需要從球桌周圍拾起2 4 0個球，放入各自
的籃子。Mary 只拾她這邊的球，而Joe 拾剩下的球。描述如何用旅行商問題幫助Mary 和
Joe 決定她們拾球的順序以便她們能走最少的路徑。
4.2 應用
4.2.1 貨箱裝船
1. 問題
在1 . 3節中，考察了用最大數量的貨箱裝船的問題。現在對該問題做一些改動。在新問題中，有兩艘船， n 個貨箱。第一艘船的載重量是c1，第二艘船的載重量是c2，wi 是貨箱i 的重量且
n ?i = 1wi≤c1+c2。我們希望確定是否有一種可將所有n 個貨箱全部裝船的方法。若有的話，找出該方法。
例4-4 當n= 3，c1 =c2 = 5 0，w=[10,40,40] 時，可將貨箱1 , 2裝到第一艘船上，貨箱3裝到第二艘船上。如果w= [ 2 0 , 4 0 , 4 0 ]，則無法將貨箱全部裝船。當n ?i = 1wi＝c1+c2 時，兩艘船的裝載問題等價于子集之和（ s u m - o f - s u b s e t）問題，即有n 個數字，要求找到一個子集（如果存在的話）使它的和為c1。當c1=c2 且n ?i = 1wi＝2c1 時，兩艘船的裝載問題等價于分割問題（ partition problem），即有n個數字ai , ( 1≤i≤n)，要求找到一個子集（若存在的話），使得子集之和為( n ?i = 1ai)/ 2。分割問題和子集之和問題都是N P-復雜問題。而且即使問題被限制為整型數字，它們仍是N P-復雜問題。所以不能期望在多項式時間內解決兩艘船的裝載問題。當存在一種方法能夠裝載所有n 個貨箱時，可以驗證以下的裝船策略可以獲得成功： 1) 盡可能地將第一艘船裝至它的重量極限； 2) 將剩余貨箱裝到第二艘船。為了盡可能地將第一艘船裝滿，需要選擇一個貨箱的子集，它們的總重量盡可能接近c1。這個選擇可通過求解0 / 1背包問題來實現，即尋找m ax (n ?i = 1wi xi )，其中n ?i = 1wi xi≤c1，xi ?{ 0 , 1 }，1≤i≤n。當重量是整數時，可用1 5 . 2節的動態規劃方法確定第一艘船的最佳裝載。用元組方法所需時間為O ( m i n {c1 , 2 n }）。可以使用回溯方法設計一個復雜性為O ( 2n ) 的算法，在有些實例中，該方法比動態規劃算法要好。
2. 第一種回溯算法
既然想要找到一個重量的子集，使子集之和盡量接近c1，那么可以使用一個子集空間，并將其組織成如圖1 6 - 2那樣的二叉樹。可用深度優先的方法搜索該解空間以求得最優解。使用限界函數去阻止不可能獲得解答的節點的擴張。如果Z是樹的j+ 1層的一個節點，那么從根到O的路徑定義了xi（1≤i≤j）的值。使用這些值，定義c w（當前重量）為n ?i = 1wi xi 。若c w>c1，則以O為根的子樹不能產生一個可行的解答。可將這個測試作為限界函數。當且僅當一個節點的c w值大于c1 時，定義它是不可行的。
例4-5 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = 1 2。解空間樹為圖1 6 - 2的樹再加上一層節點。搜索從根A開始且c w= 0。若移動到左孩子B則c w= 8，c w≤c1 = 1 2。以B為根的子樹包含一個可行的節點，故移動到節點B。從節點B不能移動到節點D，因為c w+w2 >c1。移動到節點E，這個移動未改變c w。下一步為節點J，c w= 1 0。J的左孩子的c w值為1 3，超出了c1，故搜索不能移動到J的左孩子。
可移動到J的右孩子，它是一個葉節點。至此，已找到了一個子集，它的c w= 1 0。xi 的值由從A到J的右孩子的路徑獲得，其值為[ 1 , 0 , 1 , 0 ]。
回溯算法接著回溯到J，然后是E。從E，再次沿著樹向下移動到節點K，此時c w= 8。移動到它的左子樹，有c w= 11。既然已到達了一個葉節點，就看是否c w的值大于當前的最優c w 值。結果確實大于最優值，所以這個葉節點表示了一個比[ 1 , 0 , 1 , 0 ]更好的解決方案。到該節點的路徑決定了x 的值[ 1 , 0 , 0 , 1 ]。從該葉節點，回溯到節點K，現在移動到K的右孩子，一個具有c w= 8的葉節點。這個葉節點中沒有比當前最優cw 值還好的cw 值，所以回溯到K , E , B直到A。從根節點開始，沿樹繼續向下移動。算法將移動到C并搜索它的子樹。
當使用前述的限界函數時，便產生了程序1 6 - 1所示的回溯算法。函數M a x L o a d i n g返回≤c的最大子集之和，但它不能找到產生該和的子集。后面將改進代碼以便找到這個子集。
M a x L o a d i n g調用了一個遞歸函數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中的參數個數。maxLoading(1) 實際執行解空間的搜索。MaxLoading(i) 搜索以i層節點（該節點已被隱式確定）為根的子樹。從根到該節點的路徑定義的子解答有一個重量值c w，目前最優解答的重量為b e s t w，這些變量以及與類L o a d i n g的一個成員相關聯的其他變量，均由M a x L o a d i n g初始化。
程序16-1 第一種回溯算法
template<class T>
class Loading {
friend MaxLoading(T [], T, int);
p r i v a t e :
void maxLoading(int i);
int n; // 貨箱數目
T *w, // 貨箱重量數組
c, // 第一艘船的容量
c w, // 當前裝載的重量
bestw; // 目前最優裝載的重量
} ;
template<class T>
void Loading<T>::maxLoading(int i)
{// 從第i 層節點搜索
if (i > n) {// 位于葉節點
if (cw > bestw) bestw = cw;
r e t u r n ; }
// 檢查子樹
if (cw + w[i] <= c) {// 嘗試x[i] = 1
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
maxLoading(i+1);// 嘗試x[i] = 0
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最優裝載的重量
Loading<T> X;
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// 計算最優裝載的重量
X . m a x L o a d i n g ( 1 ) ;
return X.bestw;
}
如果i＞n，則到達了葉節點。被葉節點定義的解答有重量c w，它一定≤c，因為搜索不會移動到不可行的節點。若c w > b e s t w，則目前最優解答的值被更新。當i≤n 時，我們處在有兩個孩子的節點Z上。左孩子表示x [ i ] = 1的情況，只有c w + w [ i ]≤c 時，才能移到這里。當移動到左孩子時， cw 被置為c w + w [ i ]，且到達一個i + 1層的節點。以該節點為根的子樹被遞歸搜索。當搜索完成時，回到節點Z。為了得到Z的cw 值，需用當前的cw 值減去w [ i ]，Z的右子樹還未搜索。既然這個子樹表示x [ i ] = 0的情況，所以無需進行可行性檢查就可移動到該子樹，因為一個可行節點的右孩子總是可行的。
注意：解空間樹未被m a x L o a d i n g顯示構造。函數m a x L o a d i n g在它到達的每一個節點上花費( 1 )時間。到達的節點數量為O ( 2n )，所以復雜性為O ( 2n )。這個函數使用的遞歸棧空間為(n)。
3. 第二種回溯方法
通過不移動到不可能包含比當前最優解還要好的解的右子樹，能提高函數m a x L o a d i n g的性能。令b e s t w為目前最優解的重量， Z為解空間樹的第i 層的一個節點， c w的定義如前。以Z為根的子樹中沒有葉節點的重量會超過c w + r，其中r=n ?j = i + 1w[ j ] 為剩余貨箱的重量。因此，當c w + r≤b e s t w時，沒有必要去搜索Z的右子樹。
例4-6 令n, w, c1 的值與例4 - 5中相同。用新的限界函數，搜索將像原來那樣向前進行直至到達第一個葉節點J（它是J的右孩子）。bestw 被置為1 0。回溯到E，然后向下移動到K的左孩子，此時b e s t w被更新為11。我們沒有移動到K的右孩子，因為在右孩子節點c w = 8，r = 0，c w + r≤b e s t w。回溯到節點A。同樣，不必移動到右孩子C，因為在C點c w = 0，r = 11且c w + r≤b e s t w。加強了條件的限界函數避免了對A的右子樹及K的右子樹的搜索。
當使用加強了條件的限界函數時，可得到程序1 6 - 2的代碼。這個代碼將類型為T的私有變量r 加到了類L o a d i n g的定義中。新的代碼不必檢查是否一個到達的葉節點有比當前最優解還優的重量值。這樣的檢查是不必要的，因為加強的限界函數不允許移動到不能產生較好解的節點。因此，每到達一個新的葉節點就意味著找到了比當前最優解還優的解。雖然新代碼的復雜性仍是O ( 2n )，但它可比程序1 6 - 1少搜索一些節點。
程序16-2 程序1 6 - 1的優化
template<class T>
void Loading<T>::maxLoading(int i)
{// // 從第i 層節點搜索
if (i > n) {// 在葉節點上
bestw = cw;
r e t u r n ; }
// 檢查子樹
r -= w[i];
if (cw + w[i] <= c) {//嘗試x[i] = 1
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
if (cw + r > bestw) //嘗試x[i] = 0
m a x L o a d i n g ( i + 1 ) ;
r += w[i];
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最優裝載的重量
Loading<T> X;
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// r的初始值為所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w[i];
// 計算最優裝載的重量
X . m a x L o a d i n g ( 1 ) ;
return X.bestw;
}
4. 尋找最優子集
為了確定具有最接近c 的重量的貨箱子集，有必要增加一些代碼來記錄當前找到的最優子集。為了記錄這個子集，將參數bestx 添加到Maxloading 中。bestx 是一個整數數組，其中元素可為0或1，當且僅當b e s t x [ i ] = 1時，貨箱i 在最優子集中。新的代碼見程序1 6 - 3。
程序16-3 給出最優裝載的代碼
template<class T>
void Loading<T>::maxLoading(int i)
{ / /從第i 層節點搜索
if (i > n) {// 在葉節點上
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw; return;}
// 檢查子樹
r -= w[i];
if (cw + w[i] <= c) {//嘗試x[i] = 1
x[i] = 1;
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
if (cw + r > bestw) {//嘗試x[i] = 0
x[i] = 0;
m a x L o a d i n g ( i + 1 ) ; }
r += w[i];
}
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最優裝載及其值
Loading<T> X;
// 初始化X
X.x = new int [n+1];
X.w = w;
X.c = c;
X.n = n;
X.bestx = bestx;
X.bestw = 0;
X.cw = 0;
// r的初始值為所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w[i];
X . m a x L o a d i n g ( 1 ) ;
delete [] X.x;
return X.bestw;
}
這段代碼在L o a d i n g中增加了兩個私有數據成員： x 和b e s t x。這兩個私有數據成員都是整型的一維數組。數組x 用來記錄從搜索樹的根到當前節點的路徑（即它保留了路徑上的xi 值），b e s t x記錄當前最優解。無論何時到達了一個具有較優解的葉節點， bestx 被更新以表示從根到葉的路徑。為1的xi 值確定了要被裝載的貨箱。數據x 的空間由MaxLoading 分配。
因為bestx 可以被更新O ( 2n )次，故maxLoading 的復雜性為O (n2n )。使用下列方法之一，復雜性可降為O ( 2n )：
1) 首先運行程序1 6 - 2的代碼，以決定最優裝載重量，令其為W。然后運行程序1 6 - 3的一個修改版本。該版本以b e s t w = W開始運行，當c w + r≥b e s t w時搜索右子樹，第一次到達一個葉節點時便終止（即i > n）。
2) 修改程序1 6 - 3的代碼以不斷保留從根到當前最優葉的路徑。尤其當位于i 層節點時，則到最優葉的路徑由x [ j ]（1≤j<i）和b e s tx [ j ]（j≤i≤n）給出。按照這種方法，算法每次回溯一級，并在b e s t x中存儲一個x [ i ]。由于算法回溯所需時間為O ( 2n )，因此額外開銷為O ( 2n )。
5. 一個改進的迭代版本
可改進程序1 6 - 3的代碼以減少它的空間需求。因為數組x 中記錄可在樹中移動的所有路徑，故可以消除大小為(n)的遞歸棧空間。如例4 - 5所示，從解空間樹的任何節點，算法不斷向左孩子移動，直到不能再移動為止。如果一個葉子已被到達，則最優解被更新。否則，它試圖移動到右孩子。當要么到達一個葉節點，要么不值得移動到一個右孩子時，算法回溯到一個節點，條件是從該節點向其右孩子移動有可能找到最優解。這個節點有一個特性，即它是路徑中具有x [ i ] = 1的節點中離根節點最近的節點。如果向右孩子的移動是有效的，那么就這么做，然后再完成一系列向左孩子的移動。如果向右孩子的移動是無效的，則回溯到x [ i ] = 1的下一個節點。
該算法遍歷樹的方式可被編碼成與程序1 6 - 4一樣的迭代（即循環）算法。不像遞歸代碼，這種代碼在檢查是否該向右孩子移動之前就移動到了右孩子。如果這個移動是不可行的，則回溯。迭代代碼的時間復雜性與程序1 6 - 3一樣。
程序16-4 迭代代碼
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最佳裝載及其值
// 迭代回溯程序
// 初始化根節點
int i = 1; // 當前節點的層次
// x[1:i-1] 是到達當前節點的路徑
int *x = new int [n+1];
T bestw = 0, // 迄今最優裝載的重量
cw = 0, // 當前裝載的重量
r = 0; // 剩余貨箱重量的和
for (int j = 1; j <= n; j++)
r += w[j];
// 在樹中搜索
while (true) {
// 下移，盡可能向左
while (i <= n && cw + w[i] <= c) {
// 移向左孩子
r -= w[i];
cw += w[i];
x[i] = 1;
i + + ;
}
if (i > n) {// 到達葉子
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw;}
else {// 移向右孩子
r -= w[i];
x[i] = 0;
i + + ; }
// 必要時返回
while (cw + r <= bestw) {
// 本子樹沒有更好的葉子，返回
i - - ;
while (i > 0 && !x[i]) {
// 從一個右孩子返回
r += w[i];
i - - ;
}
if (i == 0) {delete [] x;
return bestw;}
// 移向右子樹
x[i] = 0;
cw -= w[i];
i + + ;
}
}
}
4.2.2 0/1背包問題
0 / 1背包問題是一個N P-復雜問題，為了解決該問題，在1 . 4節采用了貪婪算法，在3 . 2節又采用了動態規劃算法。在本節，將用回溯算法解決該問題。既然想選擇一個對象的子集，將它們裝入背包，以便獲得的收益最大，則解空間應組織成子集樹的形狀（如圖1 6 - 2所示）。該回溯算法與4 . 2節的裝載問題很類似。首先形成一個遞歸算法，去找到可獲得的最大收益。然后，對該算法加以改進，形成代碼。改進后的代碼可找到獲得最大收益時包含在背包中的對象的集合。
與程序1 6 - 2一樣，左孩子表示一個可行的節點，無論何時都要移動到它；當右子樹可能含有比當前最優解還優的解時，移動到它。一種決定是否要移動到右子樹的簡單方法是令r 為還未遍歷的對象的收益之和，將r 加到c p（當前節點所獲收益）之上，若（ r + c p）≤b e s t p（目前最優解的收益），則不需搜索右子樹。一種更有效的方法是按收益密度pi / wi 對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量，當遇到第一個不能全部放入背包的對象時，就使用它的一部分。
例4-7 考察一個背包例子： n= 4，c= 7，p= [ 9 , 1 0 , 7 , 4 ]，w= [ 3 , 5 , 2 , 1 ]。這些對象的收益密度為[ 3 , 2 , 3 . 5 , 4 ]。當背包以密度遞減的順序被填充時，對象4首先被填充，然后是對象3、對象1。在這三個對象被裝入背包之后，剩余容量為1。這個容量可容納對象2的0 . 2倍的重量。將0 . 2倍的該對象裝入，產生了收益值2。被構造的解為x= [ 1 , 0 . 2 , 1 , 1 ]，相應的收益值為2 2。盡管該解不可行（x2 是0 . 2，而實際上它應為0或1），但它的收益值2 2一定不少于要求的最優解。因此，該0 / 1背包問題沒有收益值多于2 2的解。
解空間樹為圖1 6 - 2再加上一層節點。當位于解空間樹的節點B時，x1= 1，目前獲益為c p= 9。該節點所用容量為c w= 3。要獲得最好的附加收益，要以密度遞減的順序填充剩余容量c l e f t=ccw= 4。也就是說，先放對象4，然后是對象3，然后是對象2的0 . 2倍的重量。因此，子樹A的最優解的收益值至多為2 2。當位于節點C時，c p=c w= 0，c l e f t= 7。按密度遞減順序填充剩余容量，則對象4和3被裝入。然后是對象2的0 . 8倍被裝入。這樣產生出收益值1 9。在子樹C中沒有節點可產生出比1 9還大的收益值。
在節點E，c p= 9，c w= 3，c l e f t= 4。僅剩對象3和4要被考慮。當對象按密度遞減的順序被考慮時，對象4先被裝入，然后是對象3。所以在子樹E中無節點有多于c p+ 4 + 7 = 2 0的收益值。如果已經找到了一個具有收益值2 0或更多的解，則無必要去搜索E子樹。
一種實現限界函數的好方法是首先將對象按密度排序。假定已經做了這樣的排序。定義類K n a p（見程序1 6 - 5）來減少限界函數B o u n d（見程序1 6 - 6）及遞歸函數K n a p s a c k（見程序1 6 - 7）的參數數量，該遞歸函數用于計算最優解的收益值。參數的減少又可引起遞歸棧空間的減少以及每一個K n a p s a c k的執行時間的減少。注意函數K n a p s a c k和函數m a x L o a d i n g（見程序1 6 - 2）的相似性。同時注意僅當向右孩子移動時，限界函數才被計算。當向左孩子移動時，左孩子的限界函數的值與其父節點相同。
程序16-5 Knap類
template<class Tw, class Tp>
class Knap {
friend Tp Knapsack(Tp *, Tw *, Tw, int);
p r i v a t e :
Tp Bound(int i);
void Knapsack(int i);
Tw c; / /背包容量
int n; // 對象數目
Tw *w; // 對象重量的數組
Tp *p; // 對象收益的數組
Tw cw; // 當前背包的重量
Tp cp; // 當前背包的收益
Tp bestp; // 迄今最大的收益
} ;
程序16-6 限界函數
template<class Tw, class Tp>
Tp Knap<Tw, Tp>::Bound(int i)
{// 返回子樹中最優葉子的上限值Return upper bound on value of
// best leaf in subtree.
Tw cleft = c - cw; // 剩余容量
Tp b = cp; // 收益的界限
// 按照收益密度的次序裝填剩余容量
while (i <= n && w[i] <= cleft) {
cleft -= w[i];
b += p[i];
i + + ;
}
// 取下一個對象的一部分
if (i <= n) b += p[i]/w[i] * cleft;
return b;
}
程序16-7 0/1背包問題的迭代函數
template<class Tw, class Tp>
void Knap<Tw, Tp>::Knapsack(int i)
{// 從第i 層節點搜索
if (i > n) {// 在葉節點上
bestp = cp;
r e t u r n ; }
// 檢查子樹
if (cw + w[i] <= c) {//嘗試x[i] = 1
cw += w[i];
cp += p[i];
K n a p s a c k ( i + 1 ) ;
cw -= w[i];
cp -= p[i];}
if (Bound(i+1) > bestp) // 嘗試x[i] = 0
K n a p s a c k ( i + 1 ) ;
}
在執行程序1 6 - 7的函數Kn a p s a c k之前，需要按密度對對象排序，也要確保對象的重量總和超出背包的容量。為了完成排序，定義了類O b j e c t（見程序1 6 - 8）。注意定義操作符< =是為了使歸并排序程序（見程序1 4 - 3）能按密度遞減的順序排序。
程序16-8 Object類
class Object {
friend int Knapsack(int *, int *, int, int);
p u b l i c :
int operator<=(Object a) const
{return (d >= a.d);}
p r i v a t e :
int ID; // 對象號
float d; // 收益密度
} ;
程序1 6 - 9首先驗證重量之和超出背包容量，然后排序對象，在執行K n a p : : K n a p s a c k之前完成一些必要的初始化。K n a p : K n a p s a c k的復雜性是O (n2n )，因為限界函數的復雜性為O (n)，且該函數在O ( 2n )個右孩子處被計算。
程序16-9 程序1 6 - 7的預處理代碼
template<class Tw, class Tp>
Tp Knapsack(Tp p[], Tw w[], Tw c, int n)
{// 返回最優裝包的值
// 初始化
Tw W = 0; // 記錄重量之和
Tp P = 0; // 記錄收益之和
// 定義一個按收益密度排序的對象數組
Object *Q = new Object [n];
for (int i = 1; i <= n; i++) {
// 收益密度的數組
Q[i-1].ID = i;
Q[i-1].d = 1.0*p[i]/w[i];
P += p[i];
W += w[i];
}
if (W <= c) return P; // 可容納所有對象
MergeSort(Q,n); // 按密度排序
// 創建K n a p的成員
K n a p < Tw, Tp> K;
K.p = new Tp [n+1];
K.w = new Tw [n+1];
for (i = 1; i <= n; i++) {
K.p[i] = p[Q[i-1].ID];
K.w[i] = w[Q[i-1].ID];
}
K.cp = 0;
K.cw = 0;
K.c = c;
K.n = n;
K.bestp = 0;
// 尋找最優收益
K . K n a p s a c k ( 1 ) ;
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
4.2.3 最大完備子圖
令U為無向圖G的頂點的子集，當且僅當對于U中的任意點u 和v，(u , v)是圖G的一條邊時，U定義了一個完全子圖（complete subgraph）。子圖的尺寸為圖中頂點的數量。當且僅當一個完全子圖不被包含在G的一個更大的完全子圖中時，它是圖G的一個完備子圖。最大的完備子圖是具有最大尺寸的完備子圖。
例4-8 在圖16-7a 中，子集{ 1 , 2 }定義了一個尺寸為2的完全子圖。這個子圖不是一個完備子圖，因為它被包含在一個更大的完全子圖{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }定義了該圖的一個最大的完備子圖。點集{ 1 , 4 , 5 }和{ 2 , 3 , 5 }定義了其他的最大的完備子圖。
當且僅當對于U中任意點u 和v，(u , v) 不是G的一條邊時，U定義了一個空子圖。當且僅當一個子集不被包含在一個更大的點集中時，該點集是圖G的一個獨立集（independent set），同時它也定義了圖G的空子圖。最大獨立集是具有最大尺寸的獨立集。對于任意圖G，它的補圖（c o m p l e m e n t） 是有同樣點集的圖，且當且僅當（ u,v）不是G的一條邊時，它是的一條邊。
例4-9 圖16-7b 是圖16-7a 的補圖，反之亦然。{ 2 , 4 }定義了16-7a 的一個空子圖，它也是該圖的一個最大獨立集。雖然{ 1 , 2 }定義了圖16-7b 的一個空子圖，它不是一個獨立集，因為它被包含在空子圖{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }是圖16-7b 中的一個最大獨立集。
如果U定義了G的一個完全子圖，則它也定義了的一個空子圖，反之亦然。所以在G的完備子圖與的獨立集之間有對應關系。特別的， G的一個最大完備子圖定義了的一個最大獨立集。
最大完備子圖問題是指尋找圖G的一個最大完備子圖。類似地，最大獨立集問題是指尋找圖G的一個最大獨立集。這兩個問題都是N P-復雜問題。當用算法解決其中一個問題時，也就解決了另一個問題。例如，如果有一個求解最大完備子圖問題的算法，則也能解決最大獨立集問題，方法是首先計算所給圖的補圖，然后尋找補圖的最大完備子圖。
例4-10 假定有一個n 個動物構成的集合。可以定義一個有n 個頂點的相容圖（c o m p a t i b i l i t yg r a p h）G。當且僅當動物u 和v 相容時，（u,v）是G的一條邊。G的一個最大完備子圖定義了相互間相容的動物構成的最大子集。
3 . 2節考察了如何找到一個具有最大尺寸的互不交叉的網組的集合問題。可以把這個問題看作是一個最大獨立集問題。定義一個圖，圖中每個頂點表示一個網組。當且僅當兩個頂點對應的網組交叉時，它們之間有一條邊。所以該圖的一個最大獨立集對應于非交叉網組的一個最大尺寸的子集。當網組有一個端點在路徑頂端，而另一個在底端時，非交叉網組的最大尺寸的子集能在多項式時間（實際上是(n2 )）內用動態規劃算法得到。當一個網組的端點可能在平面中的任意地方時，不可能有在多項式時間內找到非交叉網組的最大尺寸子集的算法。最大完備子圖問題和最大獨立集問題可由回溯算法在O (n2n )時間內解決。兩個問題都可使用子集解空間樹（如圖1 6 - 2所示）。考察最大完備子圖問題，該遞歸回溯算法與程序1 6 - 3非常類似。當試圖移動到空間樹的i 層節點Z的左孩子時，需要證明從頂點i 到每一個其他的頂點j（xj = 1且j 在從根到Z的路徑上）有一條邊。當試圖移動到Z的右孩子時，需要證明還有足夠多的頂點未被搜索，以便在右子樹有可能找到一個較大的完備子圖。
回溯算法可作為類A d j a c e n c y G r a p h（見程序1 2 - 4）的一個成員來實現，為此首先要在該類
中加入私有靜態成員x（整型數組，用于存儲到當前節點的路徑），b e s t x（整型數組，保存目
前的最優解），b e s t n（b e s t x中點的數量），c n（x 中點的數量）。所以類A d j a c e c y G r a p h的所有實
例都能共享這些變量。
函數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的一個私有成員，而M a x C l i q u e是一個
共享成員。函數m a x C l i q u e對解空間樹進行搜索，而M a x C i q u e初始化必要的變量。M a x c l i q u e ( v )
的執行返回最大完備子圖的尺寸，同時它也設置整型數組v，當且僅當頂點i 不是所找到的最大
完備子圖的一個成員時，v [ i ] = 0。
程序16-10 最大完備子圖
void AdjacencyGraph::maxClique(int i)
{// 計算最大完備子圖的回溯代碼
if (i > n) {// 在葉子上
// 找到一個更大的完備子圖，更新
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestn = cn;
r e t u r n ; }
// 在當前完備子圖中檢查頂點i是否與其它頂點相連
int OK = 1;
for (int j = 1; j < i; j++)
if (x[j] && a[i][j] == NoEdge) {
// i 不與j 相連
OK = 0;
b r e a k ; }
if (OK) {// 嘗試x[i] = 1
x[i] = 1; // 把i 加入完備子圖
c n + + ;
m a x C l i q u e ( i + 1 ) ;
x[i] = 0;
c n - - ; }
if (cn + n - i > bestn) {// 嘗試x[i] = 0
x[i] = 0;
m a x C l i q u e ( i + 1 ) ; }
}
int AdjacencyGraph::MaxClique(int v[])
{// 返回最大完備子圖的大小
// 完備子圖的頂點放入v [ 1 : n ]
// 初始化
x = new int [n+1];
cn = 0;
bestn = 0;
bestx = v;
// 尋找最大完備子圖
m a x C l i q u e ( 1 ) ;
delete [] x;
return bestn;
}
4.2.4 旅行商問題
旅行商問題（例4 . 3）的解空間是一個排列樹。這樣的樹可用函數P e r m (見程序1 - 1 0 )搜索，并可生成元素表的所有排列。如果以x=[1, 2, ., n] 開始，那么通過產生從x2 到xn 的所
有排列，可生成n 頂點旅行商問題的解空間。由于P e r m產生具有相同前綴的所有排列，因此可以容易地改造P e r m，使其不能產生具有不可行前綴（即該前綴沒有定義路徑）或不可能比當前最優旅行還優的前綴的排列。注意在一個排列空間樹中，由任意子樹中的葉節點定
義的排列有相同的前綴（如圖1 6 - 5所示）。因此，考察時刪除特定的前綴等價于搜索期間不
進入相應的子樹。旅行商問題的回溯算法可作為類A d j a c e n c y W D i g r a p h（見程序1 2 - 1）的一個成員。在其他例子中，有兩個成員函數： t S P和T S P。前者是一個保護或私有成員，后者是一個共享成員。函數G . T S P ( v )返回最少耗費旅行的花費，旅行自身由整型數組v 返回。若網絡中無旅行，則返回N o E d g e。t S P在排列空間樹中進行遞歸回溯搜索， T S P是其一個必要的預處理過程。T S P假定x（用來保存到當前節點的路徑的整型數組），b e s t x（保存目前發現的最優旅行的整型數組），
c c（類型為T的變量，保存當前節點的局部旅行的耗費），b e s t c（類型為T的變量，保存目前最優解的耗費）已被定義為A d j a c e n c y W D i g r a p h中的靜態數據成員。T S P見程序1 6 - 11。t S P ( 2 )搜索一棵包含x [ 2 : n ]的所有排列的樹。
程序1 6 - 11 旅行商回溯算法的預處理程序
template<class T>
T AdjacencyWDigraph<T>::TSP(int v[])
{// 用回溯算法解決旅行商問題
// 返回最優旅游路徑的耗費，最優路徑存入v [ 1 : n ]
/ /初始化
x = new int [n+1];
// x 是排列
for (int i = 1; i <= n; i++)
x[i] = i;
bestc = NoEdge;
bestx = v; // 使用數組v來存儲最優路徑
cc = 0;
// 搜索x [ 2 : n ]的各種排列
t S P ( 2 ) ;
delete [] x;
return bestc;
}
函數t S P見程序1 6 - 1 2。它的結構與函數P e r m相同。當i=n 時，處在排列樹的葉節點的父節點上，并且需要驗證從x[n-1] 到x[n] 有一條邊，從x[n] 到起點x[1] 也有一條邊。若兩條邊都存在，則發現了一個新旅行。在本例中，需要驗證是否該旅行是目前發現的最優旅行。若是，則將旅行和它的耗費分別存入b e s t x與b e s t c中。
當i＜n 時，檢查當前i-1 層節點的孩子節點，并且僅當以下情況出現時，移動到孩子節點之一：1) 有從x[i-1] 到x[i] 的一條邊（如果是這樣的話， x [ 1 : i ]定義了網絡中的一條路徑）；2 )路徑x[1:i] 的耗費小于當前最優解的耗費。變量cc 保存目前所構造的路徑的耗費。
每次找到一個更好的旅行時，除了更新bestx 的耗費外， tS P需耗時O ( (n- 1 ) ! )。因為需發生O ( (n-1)!) 次更新且每一次更新的耗費為(n) 時間，因此更新所需時間為O (n* (n- 1 ) ! )。通過使用加強的條件（練習1 6），能減少由tS P搜索的樹節點的數量。
程序16-12 旅行商問題的迭代回溯算法
void AdjacencyWDigraph<T>::tSP(int i)
{// 旅行商問題的回溯算法
if (i == n) {// 位于一個葉子的父節點
// 通過增加兩條邊來完成旅行
if (a[x[n-1]][x[n]] != NoEdge &&
a[x[n]][1] != NoEdge &&
(cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc ||
bestc == NoEdge)) {// 找到更優的旅行路徑
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];}
}
else {// 嘗試子樹
for (int j = i; j <= n; j++)
/ /能移動到子樹x [ j ]嗎?
if (a[x[i-1]][x[j]] != NoEdge &&
(cc + a[x[i-1]][x[i]] < bestc ||
bestc == NoEdge)) {//能
// 搜索該子樹
Swap(x[i], x[j]);
cc += a[x[i-1]][x[i]];
t S P ( i + 1 ) ;
cc -= a[x[i-1]][x[i]];
Swap(x[i], x[j]);}
}
}
4.2.5 電路板排列
在大規模電子系統的設計中存在著電路板排列問題。這個問題的經典形式為將
n個電路板放置到一個機箱的許多插槽中，（如圖1 6 - 8所示）。n個電路板的每一種排
列定義了一種放置方法。令B= {b1 , ., bn }表示這n個電路板。m個網組集合L= {N1,
., Nm }由電路板定義，Ni 是B的子集，子集中的元素需要連接起來。實際中用電線
將插有這些電路板的插槽連接起來。
例4 - 11 令n=8, m= 5。集合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 為電路板的一個排列。電路板xi 被放置到機箱的插槽i 中。d e n s i t y(x) 為機箱中任意一對相鄰插槽間所連電線數目中的最大值。對于圖1 6 - 9中的排列，d e n s i t y為2。有兩根電線連接了插槽2和3，插槽4和5，插槽5和6。插槽6和7之間無電線，余下的相鄰插槽都只有一根電線。板式機箱被設計成具有相同的相鄰插槽間距，因此這個間距決定了機箱的大小。該間距必須保證足夠大以便容納相鄰插槽間的連線。因此這個距離（繼而機箱的大小）由d e n s i t y(x)決定。
電路板排列問題的目標是找到一種電路板的排列方式，使其有最小的d e n s i t y。既然該問題是一個N P-復雜問題，故它不可能由一個多項式時間的算法來解決，而象回溯這樣的搜索方法則是解決該問題的一種較好方法。回溯算法為了找到最優的電路板排列方式，將搜索一個排列空間。
用一個n×m 的整型數組B表示輸入，當且僅當Nj 中包含電路板bi 時，B [ i ] [ j ] = 1。令t o t a l [ j ]為Nj 中電路板的數量。對于任意部分的電路板排列x [ 1 : i ]，令n o w [ j ]為既在x [ 1 : i ]中又被包含在Nj 中的電路板的數量。當且僅當n o w [ j ] > 0且n o w [ j ]≠t o t a l [ j ]時，Nj 在插槽i 和i + 1之間有連線。插槽i 和i + 1間的線密度可利用該測試方法計算出來。在插槽k和k + 1 ( 1≤k≤i ) 間的線密度的最大值給出了局部排列的密度。
為了實現電路板排列問題的回溯算法，使用了類B o a r d（見程序1 6 - 1 3）。程序1 6 - 1 4給出了私有方法B e s t O r d e r，程序1 6 - 1 5給出了函數A r r a n g e B o a r d s。ArrangeBoards 返回最優的電路板排列密度，最優的排列由數組bestx 返回。ArrangeBoards 創建類Board 的一個成員x 并初始化與之相關的變量。尤其是total 被初始化以使total[j] 等于Nj 中電路板的數量。now[1:n] 被置為0，與一個空的局部排列相對應。調用x .BestOrder(1,0) 搜索x[1:n] 的排列樹，以從密度為0的空排列中找到一個最優的排列。通常，x.BestOrder(i,cd) 尋找最優的局部排列x [ 1 : i - 1 ]，該局部排列密度為c d。函數B e s t O r d e r（見程序1 6 - 1 4）和程序1 6 - 1 2有同樣的結構，它也搜索一個排列空間。當i=n 時，表示所有的電路板已被放置且cd 為排列的密度。既然這個算法只尋找那些比當前最優排列還優的排列，所以不必驗證cd 是否比beste 要小。當i<n 時，排列還未被完成。x[1:i-1] 定義了當前節點的局部排列，而cd 是它的密度。這個節點的每一個孩子通過在當前排列的末端增加一個電路板而擴充了這個局部排列。對于每一個這樣的擴充，新的密度l d被計算，且只有ld<bestd 的節點被搜索，其他的節點和它們的子樹不被搜索。在排列樹的每一個節點處，函數B e s t O r d e r花費(m)的時間計算每一個孩子節點的密度。所以計算密度的總時間為O (m n! )。此外，產生排列的時間為O (n!) 且更新最優排列的時間為O (m n)。
注意每一個更新至少將b e s t d的值減少1，且最終b e s t d≥0。所以更新的次數是O (m)。B e s t O r d e r的整體復雜性為O (m n! )。
程序16-13 Board的類定義
class Board {
friend ArrangeBoards(int**, int, int, int []);
p r i v a t e :
void BestOrder(int i, int cd);
int *x, // 到達當前節點的路徑
* b e s t x , // 目前的最優排列
* t o t a l , // total[j] = 帶插槽j的板的數目
* n o w, // now[j] = 在含插槽j的部分排列中的板的數目
b e s t d , // bestx的密度
n , / /板的數目
m , // 插槽的數目
* * B ; // 板的二維數組
} ;
程序16-14 搜索排列樹
void Board::BestOrder(int i, int cd)
{// 按回溯算法搜索排列樹
if (i == n) {
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestd = cd;}
else // 嘗試子樹
for (int j = i; j <= n; j++) {
// 用x[j] 作為下一塊電路板對孩子進行嘗試
// 在最后一個插槽更新并計算密度
int ld = 0;
for (int k = 1; k <= m; k++) {
now[k] += B[x[j]][k];
if (now[k] > 0 && total[k] != now[k])
l d + + ;
}
// 更新ld 為局部排列的總密度
if (cd > ld) ld = cd;
// 僅當子樹中包含一個更優的排列時，搜索該子樹
if (ld < bestd) {// 移動到孩子
Swap(x[i], x[j]);
BestOrder(i+1, ld);
Swap(x[i], x[j]);}
// 重置
for (k = 1; k <= m; k++)
now[k] -= B[x[j]][k];
}
}
程序16-15 BestOrder(程序1 6 - 1 4)的預處理代碼
int ArrangeBoards(int **B, int n, int m, int bestx[ ])
{// 返回最優密度
// 在b e s t x中返回最優排列
Board X;
// 初始化X
X.x = new int [n+1];
X.total = new int [m+1];
X.now = new int [m+1];
X.B = B;
X.n = n;
X.m = m;
X.bestx = bestx;
X.bestd = m + 1;
// 初始化t o t a l和n o w
for (int i = 1; i <= m; i++) {
X.total[i] = 0;
X.now[i] = 0;
}
// 初始化x并計算t o t a l
for (i = 1; i <= n; i++) {
X.x[i] = i;
for (int j = 1; j <= m; j++)
X.total[j] += B[i][j];
}
// 尋找最優排列
X . B e s t O r d e r ( 1 , 0 ) ;
delete [] X.x;
delete [] X.total;
delete [] X.now;
return X.bestd;