【正文】 n,t)。i++) { x[t]=h(i)。amp。 else t++。 } } 8 子集樹與排列樹 遍歷子集樹需 O(2n)計算時間 遍歷排列樹需要 O(n!)計算時間 void backtrack (int t) { if (tn) output(x)。i=1。 if (legal(t)) backtrack(t+1)。 else for (int i=t。i++) { swap(x[t], x[i])。 swap(x[t], x[i])。如果有，找出一種裝載方案。 (1)首先將第一艘輪船盡可能裝滿； (2)將剩余的集裝箱裝上第二艘輪船。由此可知，裝載問題等價于以下特殊的 01背包問題。在某些情況下該算法優(yōu)于動態(tài)規(guī)劃算法。return。 if (cw + w[i] = c) {// 搜索左子樹 x[i] = 1。 backtrack(i + 1)。 } if (cw + r bestw) { x[i] = 0。 } r += w[i]。每個作業(yè)必須先由機器 1處理，然后由機器 2處理。對于一個確定的作業(yè)調(diào)度，設(shè) Fji是作業(yè) i在機器 j上完成處理的時間。 批處理作業(yè)調(diào)度問題要求對于給定的 n個作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時間和達到最小。易見，最佳調(diào)度方案是 1,3,2，其完成時間和為18。 j = n。 bestf = f。 j = n。 f2[i]=((f2[i1]f1)?f2[i1]:f1)+m[x[j]][2]。 if (f bestf) { (x,i,j)。 (x,i,j)。 f=f2[i]。 // 當前最優(yōu)值 static int [][] m。 // 當前作業(yè)調(diào)度 static int [] bestx。 // 機器 2完成處理時間 13 符號三角形問題 + + + + + + + + + + + + + + 下圖是由 14個 “ +”和 14個 “ ”組成的符號三角形。 在一般情況下，符號三角形的第一行有 n個符號。 14 符號三角形問題 ?解向量：用 n元組 x[1:n]表示符號三角形的第一行。 if (tn) sum++。i2。 count+=i。j=t。 count+=p[j][tj+1]。 for (int j=2。j++) count=p[j][tj+1]。 } } + + + + + + + + + + + + + + 復(fù)雜度分析 計算可行性約束需要 O(n)時間，在最壞情況下有 O(2n)個結(jié)點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為 O(n2n)。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Q Q Q Q Q Q Q Q 16 ?解向量： (x1, x2, … , x n) ?顯約束： xi=1,2, … ,n ?隱約束： 1)不同列： xi?xj 2)不處于同一正、反對角線： |ij|?|xixj| n后問題 private static boolean place (int k) { for (int j=1。j++) if (((kj)==(x[j]x[k]))||(x[j]==x[k])) return false。 } private static void backtrack (int t) { if (tn) sum++。i=n。 if (place(t)) backtrack(t+1)。 // 剩余容量 double bound = cp。amp。 bound += p[i]。 } // 裝滿背包 if (i = n) bound += p[i] / w[i] * cleft。 } 18 最大團問題 給定無向圖 G=(V， E)。 G的完全子圖 U是 G的團當且僅當 U不包含在 G的更大的完全子圖中。 如果 U?V且對任意 u， v?U有 (u， v)?E，則稱 U是 G的 空子圖 。 G的 最大獨立集 是 G中所含頂點數(shù)最多的獨立集。 U是 G的最大團當且僅當 U是 G的最大獨立集。 ?上界函數(shù)：有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。 j = n。 bestn = 。 } // 檢查頂點 i 與當前團的連接 boolean ok = true。 j i。amp。 break。 ++。 。 backtrack(i + 1)。 1 2 4 5 3 20 進一步改進算法的建議 ?選擇合適的搜索順序 ，可以使得上界函數(shù)更有效的發(fā)揮作用。這在某種意義上相當于給回溯法加入了啟發(fā)性。從而得到一個 更精確的上界函數(shù) ，若 +Si=max則剪枝。 因此只要 max的值被更新過，就可以確定已經(jīng)找到最大值，不必再往下搜索了。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。這個問題是圖的 m可著色判定問題。求一個圖的色數(shù) m的問題稱為圖的 m可著色優(yōu)化問題。 圖的 m著色問題 private static void backtrack(int t) { if (tn) sum++。i=m。 if (ok(t)) backtrack(t+1)。j=n。amp。 return true。因此，回溯法總的時間耗費是 ???10niim)()1/()1()(10nnnii nmOmmnmmnm ???????思考：圖的 m著色問題與圖的最大團問題有何關(guān)系，你能否利用這個關(guān)系改進最大團問題的上界？ 23 旅行售貨員問題 ?解空間：排列樹 private static void backtrack(int i) { if (i == n) { if (a[x[n 1]][x[n]] amp。 a[x[n]][1] amp。 (bestc == || cc+a[x[n 1]][x[n]]+a[x[n]][1]bestc)) { for (int j = 1。 j++) bestx[j] = x[j]。 } } else { for (int j = i。 j++) // 是否可進入