【正文】 。 } } 復(fù)雜度分析 由于算法 backtrack在最壞情況下可能需要計(jì)算O(n!)次當(dāng)前圓排列長(zhǎng)度，每次計(jì)算需 O(n)計(jì)算時(shí)間，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為 O((n+1)!) ?上述算法尚有許多改進(jìn)的余地。 backtrack(t+1)。 float centerx=center(t)。 j = n。 } private static void backtrack(int t) { if (tn) pute()。 if (x[i]+r[i]high) high=x[i]+r[i]。i=n。 } private static void pute() {// 計(jì)算當(dāng)前圓排列的長(zhǎng)度 float low=0, high=0。 if (valuextemp) temp=valuex。jt。其最小長(zhǎng)度為 242 ?25 圓排列問題 private static float center(int t) {// 計(jì)算當(dāng)前所選擇圓的圓心橫坐標(biāo) float temp=0。圓排列問題要求從 n個(gè)圓的所有排列中找出有最小長(zhǎng)度的圓排列。 } } 復(fù)雜度分析 算法 backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解 O((n1)!)次，每次更新 bestx需計(jì)算時(shí)間O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為 O(n!)。 cc=a[x[i 1]][x[i]]。 cc+=a[x[i 1]][x[i]]。amp。 j = n。 bestc = cc+a[x[n 1]][x[n]]+a[x[n]][1]。 j = n。amp。amp。 } } 復(fù)雜度分析 圖 m可著色問題的解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是 對(duì)于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用 ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí) O(mn)。 (x[j]==x[k])) return false。j++) if (a[k][j] amp。 } } private static boolean ok(int k) {// 檢查顏色可用性 for (int j=1。i++) { x[t]=i。 else for (int i=1。 22 ?解向量： (x1, x2, … , x n)表示頂點(diǎn) i所著顏色 x[i] ?可行性約束函數(shù)：頂點(diǎn) i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。若一個(gè)圖最少需要 m種顏色才能使圖中每條邊連接的 2個(gè)頂點(diǎn)著不同顏色，則稱這個(gè)數(shù) m為該圖的色數(shù)。是否有一種著色法使 G中每條邊的 2個(gè)頂點(diǎn)著不同顏色。 21 圖的 m著色問題 給定無向連通圖 G和 m種不同的顏色。同時(shí)注意到：從 Si+1到 Si，如果找到一個(gè)更大的團(tuán)，那么 vi必然屬于找到的團(tuán)，此時(shí)有 Si=Si+1+1，否則 Si=Si+1。 ?定義 Si={vi,vi+1,...,vn}，依次求出 Sn,Sn1,...,S1的解。例如在搜索之前可以將頂點(diǎn)按度從小到大排序。 } }} 復(fù)雜度分析 最大團(tuán)問題的回溯算法 backtrack所需的計(jì)算時(shí)間顯然為 O(n2n)。 } if ( + n i bestn) {// 進(jìn)入右子樹 x[i] = 0。 backtrack(i + 1)。 } if (ok) {// 進(jìn)入左子樹 x[i] = 1。 !a[i][j]) {// i與 j不相連 ok = false。 j++) if (x[j] == 1 amp。 for (int j = 1。 return。 j++) bestx[j] = x[j]。 private static void backtrack(int i) { if (i n) {// 到達(dá)葉結(jié)點(diǎn) for (int j = 1。 1 2 4 5 3 1 2 4 5 3 19 最大團(tuán)問題 ?解空間：子集樹 ?可行性約束函數(shù)：頂點(diǎn) i到已選入的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連。 對(duì)于任一無向圖 G=(V， E)其 補(bǔ)圖 G=(V1， E1)定義為： V1=V，且 (u， v)?E1當(dāng)且僅當(dāng) (u， v)?E。G的空子圖 U是 G的 獨(dú)立集 當(dāng)且僅當(dāng) U不包含在 G的更大的空子圖中。 G的 最大團(tuán) 是指 G中所含頂點(diǎn)數(shù)最多的團(tuán)。如果 U?V，且對(duì)任意 u， v?U有 (u，v)?E，則稱 U是 G的 完全子圖 。 return bound。 i++。 w[i] = cleft) { cleft = w[i]。 // 以物品單位重量?jī)r(jià)值遞減序裝入物品 while (i = n amp。 } 17 01背包問題 ?解空間：子集樹 ?可行性約束函數(shù)： ?上界函數(shù)： 11 cxwniii ???private static double bound(int i) {// 計(jì)算上界 double cleft = c cw。i++) { x[t]=i。 else for (int i=1。 return true。jk。 n后問題等價(jià)于在 n n格的棋盤上放置 n個(gè)皇后，任何 2個(gè)皇后不放在同一行或同一列或同一斜線上。 15 n后問題 在 n n格的棋盤上放置彼此不受攻擊的 n個(gè)皇后。 count=i。j=t。 } backtrack(t+1)。j++) { p[j][tj+1]=p[j1][tj+1]^p[j1][tj+2]。 for (int j=2。i++) { p[1][t]=i。 else for (int i=0。 ?可行性約束函數(shù)：當(dāng)前符號(hào)三角形所包含的“ +”個(gè)數(shù)與“ ”個(gè)數(shù)均不超過 n*(n+1)/4 ?無解的判斷： n*(n+1)/2為奇數(shù) private static void backtrack (int t) { if ((counthalf)||(t*(t1)/2counthalf)) return。符號(hào)三角形問題要求對(duì)于給定的 n，計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含的 “ +”和 “ ”的個(gè)數(shù)相同。 2個(gè)同號(hào)下面都是 “ +”， 2個(gè)異號(hào)下面都是 “ ”。 // 當(dāng)前最優(yōu)作業(yè)調(diào)度 static int [] f2。 // 各作業(yè)所需的處理時(shí)間 static int [] x。 } } public class FlowShop static int n, // 作業(yè)數(shù) f1, // 機(jī)器 1完成處理時(shí)間 f, // 完成時(shí)間和 bestf。 } f1=