【正文】 上第二艘輪船。由此可知，裝載問題等價(jià)于以下特殊的 01背包問題。在某些情況下該算法優(yōu)于動(dòng)態(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]。每個(gè)作業(yè)必須先由機(jī)器 1處理，然后由機(jī)器 2處理。對于一個(gè)確定的作業(yè)調(diào)度，設(shè) Fji是作業(yè) i在機(jī)器 j上完成處理的時(shí)間。 批處理作業(yè)調(diào)度問題要求對于給定的 n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。易見，最佳調(diào)度方案是 1,3,2，其完成時(shí)間和為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]。 // 當(dāng)前最優(yōu)值 static int [][] m。 // 當(dāng)前作業(yè)調(diào)度 static int [] bestx。 // 機(jī)器 2完成處理時(shí)間 13 符號三角形問題 + + + + + + + + + + + + + + 下圖是由 14個(gè) “ +”和 14個(gè) “ ”組成的符號三角形。 在一般情況下，符號三角形的第一行有 n個(gè)符號。 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ù)雜度分析 計(jì)算可行性約束需要 O(n)時(shí)間，在最壞情況下有 O(2n)個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號三角形問題的回溯算法所需的計(jì)算時(shí)間為 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 最大團(tuán)問題 給定無向圖 G=(V， E)。 G的完全子圖 U是 G的團(tuán)當(dāng)且僅當(dāng) U不包含在 G的更大的完全子圖中。 如果 U?V且對任意 u， v?U有 (u， v)?E，則稱 U是 G的 空子圖 。 G的 最大獨(dú)立集 是 G中所含頂點(diǎn)數(shù)最多的獨(dú)立集。 U是 G的最大團(tuán)當(dāng)且僅當(dāng) U是 G的最大獨(dú)立集。 ?上界函數(shù)：有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。 j = n。 bestn = 。 } // 檢查頂點(diǎn) i 與當(dāng)前團(tuán)的連接 boolean ok = true。 j i。amp。 break。 ++。 。 backtrack(i + 1)。 1 2 4 5 3 20 進(jìn)一步改進(jìn)算法的建議 ?選擇合適的搜索順序 ，可以使得上界函數(shù)更有效的發(fā)揮作用。這在某種意義上相當(dāng)于給回溯法加入了啟發(fā)性。從而得到一個(gè) 更精確的上界函數(shù) ，若 +Si=max則剪枝。 因此只要 max的值被更新過，就可以確定已經(jīng)找到最大值，不必再往下搜索了。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。這個(gè)問題是圖的 m可著色判定問題。求一個(gè)圖的色數(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。因此，回溯法總的時(shí)間耗費(fèi)是 ???10niim)()1/()1()(10nnnii nmOmmnmmnm ???????思考：圖的 m著色問題與圖的最大團(tuán)問題有何關(guān)系，你能否利用這個(gè)關(guān)系改進(jìn)最大團(tuá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++) // 是否可進(jìn)入 x[j]子樹 ? if (a[x[i 1]][x[j]] amp。 (bestc == || cc+a[x[i 1]][x[j]]bestc)) {// 搜索子樹 (x, i, j)。 backtrack(i + 1)。 (x, i, j)。 24 圓排列問題 給定 n個(gè)大小不等的圓 c1,c2,… ,，現(xiàn)要將這 n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。例如，當(dāng) n=3，且所給的 3個(gè)圓的半徑分別為 1， 1， 2時(shí)，這 3個(gè)圓的最小長度的圓排列如圖所示。 for (int j=1。j++) {