【正文】 一個網(wǎng)組的端點(diǎn)可能在平面中的任意地方時，不可能有在多項(xiàng)式時間內(nèi)找到非交叉網(wǎng)組的最大尺寸子集的算法。定義一個圖，圖中每個頂點(diǎn)表示一個網(wǎng)組。當(dāng)且僅當(dāng)動物u 和v 相容時，（u,v）是G的一條邊。當(dāng)用算法解決其中一個問題時，也就解決了另一個問題。特別的， G的一個最大完備子圖定義了的一個最大獨(dú)立集。雖然{ 1 , 2 }定義了圖167b 的一個空子圖，它不是一個獨(dú)立集，因?yàn)樗话诳兆訄D{ 1 , 2 , 5 }中。最大獨(dú)立集是具有最大尺寸的獨(dú)立集。{ 1 , 2 , 5 }定義了該圖的一個最大的完備子圖。當(dāng)且僅當(dāng)一個完全子圖不被包含在G的一個更大的完全子圖中時，它是圖G的一個完備子圖。delete [] 。 = 0。} = 0。for (i = 1。 // 可容納所有對象MergeSort(Q,n)。Q[i1].d = *p[i]/w[i]。 // 記錄收益之和// 定義一個按收益密度排序的對象數(shù)組Object *Q = new Object [n]。程序1 6 9首先驗(yàn)證重量之和超出背包容量，然后排序?qū)ο螅趫?zhí)行K n a p : : K n a p s a c k之前完成一些必要的初始化。p u b l i c :int operator=(Object a) const{return (d = )。}在執(zhí)行程序1 6 7的函數(shù)Kn a p s a c k之前，需要按密度對對象排序，也要確保對象的重量總和超出背包的容量。K n a p s a c k ( i + 1 ) 。}程序167 0/1背包問題的迭代函數(shù)templateclass Tw, class Tpvoid KnapTw, Tp::Knapsack(int i){// 從第i 層節(jié)點(diǎn)搜索if (i n) {// 在葉節(jié)點(diǎn)上bestp = cp。b += p[i]。 // 剩余容量Tp b = cp。 // 當(dāng)前背包的重量Tp cp。 / /背包容量int n。程序165 Knap類templateclass Tw, class Tpclass Knap {friend Tp Knapsack(Tp *, Tw *, Tw, int)。參數(shù)的減少又可引起遞歸?？臻g的減少以及每一個K n a p s a c k的執(zhí)行時間的減少。如果已經(jīng)找到了一個具有收益值2 0或更多的解，則無必要去搜索E子樹。在節(jié)點(diǎn)E，c p= 9，c w= 3，c l e f t= 4。按密度遞減順序填充剩余容量，則對象4和3被裝入。要獲得最好的附加收益，要以密度遞減的順序填充剩余容量c l e f t=ccw= 4。因此，該0 / 1背包問題沒有收益值多于2 2的解。這個容量可容納對象2的0 . 2倍的重量。例47 考察一個背包例子： n= 4，c= 7，p= [ 9 , 1 0 , 7 , 4 ]，w= [ 3 , 5 , 2 , 1 ]。改進(jìn)后的代碼可找到獲得最大收益時包含在背包中的對象的集合。既然想選擇一個對象的子集，將它們裝入背包，以便獲得的收益最大，則解空間應(yīng)組織成子集樹的形狀（如圖1 6 2所示）。cw = w[i]。i 。 }// 必要時返回while (cw + r = bestw) {// 本子樹沒有更好的葉子，返回i 。bestw = cw。i + + 。amp。 // 剩余貨箱重量的和for (int j = 1。迭代代碼的時間復(fù)雜性與程序1 6 3一樣。如果向右孩子的移動是無效的，則回溯到x [ i ] = 1的下一個節(jié)點(diǎn)。否則，它試圖移動到右孩子。5. 一個改進(jìn)的迭代版本可改進(jìn)程序1 6 3的代碼以減少它的空間需求。2) 修改程序1 6 3的代碼以不斷保留從根到當(dāng)前最優(yōu)葉的路徑。因?yàn)閎estx 可以被更新O ( 2n )次，故maxLoading 的復(fù)雜性為O (n2n )。數(shù)組x 用來記錄從搜索樹的根到當(dāng)前節(jié)點(diǎn)的路徑（即它保留了路徑上的xi 值），b e s t x記錄當(dāng)前最優(yōu)解。delete [] 。for (int i = 1。 = bestx。// 初始化X = new int [n+1]。}if (cw + r bestw) {//嘗試x[i] = 0x[i] = 0。if (cw + w[i] = c) {//嘗試x[i] = 1x[i] = 1。 j++)bestx[j] = x[j]。bestx 是一個整數(shù)數(shù)組，其中元素可為0或1，當(dāng)且僅當(dāng)b e s t x [ i ] = 1時，貨箱i 在最優(yōu)子集中。// 計(jì)算最優(yōu)裝載的重量X . m a x L o a d i n g ( 1 ) 。// r的初始值為所有重量之和 = 0。 = c。}if (cw + r bestw) //嘗試x[i] = 0m a x L o a d i n g ( i + 1 ) 。 }// 檢查子樹r = w[i]。因此，每到達(dá)一個新的葉節(jié)點(diǎn)就意味著找到了比當(dāng)前最優(yōu)解還優(yōu)的解。當(dāng)使用加強(qiáng)了條件的限界函數(shù)時，可得到程序1 6 2的代碼。我們沒有移動到K的右孩子，因?yàn)樵谟液⒆庸?jié)點(diǎn)c w = 8，r = 0，c w + r≤b e s t w。例46 令n, w, c1 的值與例4 5中相同。令b e s t w為目前最優(yōu)解的重量， Z為解空間樹的第i 層的一個節(jié)點(diǎn)， c w的定義如前。函數(shù)m a x L o a d i n g在它到達(dá)的每一個節(jié)點(diǎn)上花費(fèi)( 1 )時間。當(dāng)搜索完成時，回到節(jié)點(diǎn)Z。當(dāng)i≤n 時，我們處在有兩個孩子的節(jié)點(diǎn)Z上。return 。 = n。}maxLoading(i+1)。r e t u r n 。int n。MaxLoading(i) 搜索以i層節(jié)點(diǎn)（該節(jié)點(diǎn)已被隱式確定）為根的子樹。函數(shù)M a x L o a d i n g返回≤c的最大子集之和，但它不能找到產(chǎn)生該和的子集。這個葉節(jié)點(diǎn)中沒有比當(dāng)前最優(yōu)cw 值還好的cw 值，所以回溯到K , E , B直到A。既然已到達(dá)了一個葉節(jié)點(diǎn)，就看是否c w的值大于當(dāng)前的最優(yōu)c w 值。xi 的值由從A到J的右孩子的路徑獲得，其值為[ 1 , 0 , 1 , 0 ]。下一步為節(jié)點(diǎn)J，c w= 1 0。若移動到左孩子B則c w= 8，c w≤c1 = 1 2。當(dāng)且僅當(dāng)一個節(jié)點(diǎn)的c w值大于c1 時，定義它是不可行的。使用這些值，定義c w（當(dāng)前重量）為n 229。2. 第一種回溯算法既然想要找到一個重量的子集，使子集之和盡量接近c(diǎn)1，那么可以使用一個子集空間，并將其組織成如圖1 6 2那樣的二叉樹。{ 0 , 1 }，1≤i≤n。為了盡可能地將第一艘船裝滿，需要選擇一個貨箱的子集，它們的總重量盡可能接近c(diǎn)1。分割問題和子集之和問題都是N P復(fù)雜問題。i = 1wi＝c1+c2 時，兩艘船的裝載問題等價(jià)于子集之和（ s u m o f s u b s e t）問題，即有n 個數(shù)字，要求找到一個子集（如果存在的話）使它的和為c1。若有的話，找出該方法。在新問題中，有兩艘船， n 個貨箱。這樣一直打下去，直到兩個籃子為空。依回溯算法遍歷節(jié)點(diǎn)的順序標(biāo)記節(jié)點(diǎn)。2) 對該樹運(yùn)用回溯算法（利用給出的p s , w s , c值），依回溯算法遍歷節(jié)點(diǎn)的順序標(biāo)記節(jié)點(diǎn)。這個特性非常重要，因?yàn)榻饪臻g的大小通常是最長路徑長度的指數(shù)或階乘。3) 用深度優(yōu)先法搜索該空間，利用限界函數(shù)避免移動到不可能產(chǎn)生解的子空間。如果在圖1 6 4的例子中使用該限界函數(shù)，那么當(dāng)?shù)竭_(dá)節(jié)點(diǎn)I時，已經(jīng)找到了具有耗費(fèi)2 5的1 , 3 , 2 , 4 , 1的旅行。圖1 6 5中的樹是頂點(diǎn){ 2 , 3 , 4 }的最佳排列的解空間樹，頂點(diǎn)1是旅行的起點(diǎn)和終點(diǎn)。這樣一棵樹有2n 個葉節(jié)點(diǎn)，全部節(jié)點(diǎn)有2n+ 1－1個。在D點(diǎn)，再次向前移動，到達(dá)O點(diǎn)。既然它不比當(dāng)前的最佳旅行好，拋棄它并回溯到G，然后是C , B。從L點(diǎn)回溯到活節(jié)點(diǎn)F。回溯算法將用深度優(yōu)先方式從根節(jié)點(diǎn)開始，通過搜索解空間樹發(fā)現(xiàn)一個最小耗費(fèi)的旅行。從根到葉的路徑中各邊的標(biāo)號定義了一個旅行（還要附加1作為終點(diǎn)）。既然旅行是包含所有頂點(diǎn)的一個循環(huán)，故可以把任意一個點(diǎn)作為起點(diǎn)（因此也是終點(diǎn)）。一個循環(huán)的花費(fèi)包括生產(chǎn)一個循環(huán)中的產(chǎn)品所需的花費(fèi)以及循環(huán)中從一個產(chǎn)品轉(zhuǎn)變到另一個產(chǎn)品的花費(fèi)。利用一個生產(chǎn)循環(huán)不斷地生產(chǎn)這些產(chǎn)品。鉆所有孔所需的時間獨(dú)立于鉆孔順序。假定要在一個金屬薄片或印刷電路板上鉆許多孔。頂點(diǎn)表示旅行商所要旅行的城市（包括起點(diǎn)）。而旅行1 , 3 , 4 , 2 , 1是旅行1 , 2 , 4 , 3 , 1的“逆”。在旅行商問題中，要設(shè)法找到一條最小耗費(fèi)的旅行。繼續(xù)下去，搜索整棵樹。假定移動到L。假定移動到F。接著，回溯到B，它也死亡了，A再次變?yōu)镋節(jié)點(diǎn)。這個解的收益為c p= 4 0。在節(jié)點(diǎn)E，r= 1 0，c p= 4 0。移到D是不可行的，因?yàn)橐频紻所需的容量w2 為1 5。假設(shè)移動到B，則活節(jié)點(diǎn)為A和B。程序5 1 3是一個在迷宮中尋找路徑的回溯算法。這個節(jié)點(diǎn)再次變?yōu)镋節(jié)點(diǎn)，它可移動到( 2 , 1 )。圖1 6 1中，從( 1 , 3 )出發(fā)有兩個可能的移動，但沒有一個是可行的。( 1 , 2 )成為E節(jié)點(diǎn)。對于本例，兩種移動都是可行的，因?yàn)樵诿恳粋€位置都有一個值0。然而，圖1 6 1中有些從( 1 , 1 )到( 3 , 3 )的路徑卻不是迷宮中從入口到出口的路徑。當(dāng)我們已經(jīng)找到了答案或者回溯盡了所有的活節(jié)點(diǎn)時，搜索過程結(jié)束。開始節(jié)點(diǎn)既是一個活節(jié)點(diǎn)又是一個E節(jié)點(diǎn)（expansion node）。從根節(jié)點(diǎn)A到葉節(jié)點(diǎn)H的路徑定義了解x= [ 1 , 1 , 1 ]。圖1 6 1用圖的形式給出了一個33迷宮的解空間。在迷宮老鼠問題中，我們可以定義一個包含從入口到出口的所有路徑的解空間；在具有n 個對象的0 / 1背包問題中（見1 . 4節(jié)和2 . 2節(jié)），解空間的一個合理選擇是2n 個長度為n 的0 / 1向量的集合，這個集合表示了將0或1分配給x的所有可能方法。按照這兩種方法對候選解進(jìn)行系統(tǒng)檢查通常會使問題的求解時間大大減少（無論對于最壞情形還是對于一般情形）。信息學(xué)競賽必備算法系列回溯算法尋找問題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個，在檢查完所有或部分候選解后，即可找到所需要的解。對候選解進(jìn)行系統(tǒng)檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方法。本章集中闡述回溯方法，這種方法被用來設(shè)計(jì)貨箱裝船、背包、最大完備子圖、旅行商和電路板排列問題的求解算法。為了實(shí)現(xiàn)回溯，首先需要為問題定義一個解空間（ solution space），這個空間必須至少包含問題的一個解（可能是最優(yōu)的）。典型的組織方法是圖或樹。從i 層節(jié)點(diǎn)到i+ 1層節(jié)點(diǎn)的一條邊上的數(shù)字給出了向量x 中第i個分量的值xi ，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑定義了解空間中的一個元素。在迷宮老鼠問題中，開始節(jié)點(diǎn)為入口節(jié)點(diǎn)( 1 , 1 )；在0 / 1背包問題中，開始節(jié)點(diǎn)為根節(jié)點(diǎn)A。如果不能移到一個新節(jié)點(diǎn)，當(dāng)前的E節(jié)點(diǎn)就“死”了（即不再是一個活節(jié)點(diǎn)），那么便只能返回到最近被考察的活節(jié)點(diǎn)（回溯），這個活節(jié)點(diǎn)變成了新的E節(jié)點(diǎn)。從迷宮的入口到出口的每一條路徑都與圖1 6 1中從( 1 , 1 )到( 3 , 3 )的一條路徑相對應(yīng)。從這個位置，能移動到( 1 , 2 )或( 2 , 1 )兩個位置。這時有兩個活節(jié)點(diǎn)(1,1) (1,2)。移動到這個位置，并置m a z e( 1 , 3 )為1以避免再次經(jīng)過該點(diǎn)，此時迷宮狀態(tài)為1 6 3 c。唯一留下的活節(jié)點(diǎn)是( 1 , 1 )。此時，活節(jié)點(diǎn)表為( 1 , 1 )，( 2 , 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，這即是到達(dá)出口的路徑。根節(jié)點(diǎn)是當(dāng)前唯一的活節(jié)點(diǎn)，也是E節(jié)點(diǎn)，從這里能夠移動到B或C點(diǎn)。從B點(diǎn)，能移動到D或E。這時活節(jié)點(diǎn)為A , B , E。因?yàn)镵是一個葉子，所以得到一個可行的解。既然不能進(jìn)一步擴(kuò)充K，K節(jié)點(diǎn)死亡，回溯到E，而E也不能進(jìn)一步擴(kuò)充，它也死亡了。從C點(diǎn)能夠移動到F或G。從F點(diǎn)，能移動到L或M。節(jié)點(diǎn)L死亡，回溯到節(jié)點(diǎn)F。任何一個包含網(wǎng)絡(luò)中所有n 個頂點(diǎn)的環(huán)路被稱作一個旅行（t o u r）。旅行2 , 4 , 3 , 1 , 2；4 , 3 , 1 , 2 , 4和3 , 1 , 2 , 4 , 3和旅行1 , 2 , 4 , 3 , 1一樣。顧名思義，旅行商問題可被用來模擬現(xiàn)實(shí)生活中旅行商所要旅行的地區(qū)問題。 旅行商問題還可用來模擬其他問題?？偣不ǖ臅r間是鉆所有孔的時間與鉆頭移動的時間。另有一個例子，考察一個批量生產(chǎn)的環(huán)境，其中有一個特殊的機(jī)器可用來生產(chǎn)n 個不同的產(chǎn)品。例如，如果這臺機(jī)器被用來順序?yàn)樾∑噰娂t、白、藍(lán)漆，那么在為藍(lán)色小汽車噴漆之后，我們又開始了新一輪循環(huán)，為紅色小汽車噴漆，然后是白色小汽車、藍(lán)色小汽車、紅色小汽車，..，如此下去。一個最小耗費(fèi)的旅行定義了一個最小耗費(fèi)的生產(chǎn)循環(huán)。圖1 6 5給出了一棵表示四頂點(diǎn)網(wǎng)