【文章內(nèi)容簡介】 1 2 4 5 3 1 2 4 5 3 19 最大團問題 ?解空間：子集樹 ?可行性約束函數(shù)：頂點 i到已選入的頂點集中每一個頂點都有邊相連。 ?上界函數(shù)：有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。 private static void backtrack(int i) { if (i n) {// 到達葉結(jié)點 for (int j = 1。 j = n。 j++) bestx[j] = x[j]。 bestn = 。 return。 } // 檢查頂點 i 與當(dāng)前團的連接 boolean ok = true。 for (int j = 1。 j i。 j++) if (x[j] == 1 amp。amp。 !a[i][j]) {// i與 j不相連 ok = false。 break。 } if (ok) {// 進入左子樹 x[i] = 1。 ++。 backtrack(i + 1)。 。 } if ( + n i bestn) {// 進入右子樹 x[i] = 0。 backtrack(i + 1)。 } }} 復(fù)雜度分析 最大團問題的回溯算法 backtrack所需的計算時間顯然為 O(n2n)。 1 2 4 5 3 20 進一步改進算法的建議 ?選擇合適的搜索順序 ，可以使得上界函數(shù)更有效的發(fā)揮作用。例如在搜索之前可以將頂點按度從小到大排序。這在某種意義上相當(dāng)于給回溯法加入了啟發(fā)性。 ?定義 Si={vi,vi+1,...,vn}，依次求出 Sn,Sn1,...,S1的解。從而得到一個 更精確的上界函數(shù) ，若 +Si=max則剪枝。同時注意到：從 Si+1到 Si，如果找到一個更大的團，那么 vi必然屬于找到的團，此時有 Si=Si+1+1，否則 Si=Si+1。 因此只要 max的值被更新過，就可以確定已經(jīng)找到最大值，不必再往下搜索了。 21 圖的 m著色問題 給定無向連通圖 G和 m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使 G中每條邊的 2個頂點著不同顏色。這個問題是圖的 m可著色判定問題。若一個圖最少需要 m種顏色才能使圖中每條邊連接的 2個頂點著不同顏色，則稱這個數(shù) m為該圖的色數(shù)。求一個圖的色數(shù) m的問題稱為圖的 m可著色優(yōu)化問題。 22 ?解向量： (x1, x2, … , x n)表示頂點 i所著顏色 x[i] ?可行性約束函數(shù)：頂點 i與已著色的相鄰頂點顏色不重復(fù)。 圖的 m著色問題 private static void backtrack(int t) { if (tn) sum++。 else for (int i=1。i=m。i++) { x[t]=i。 if (ok(t)) backtrack(t+1)。 } } private static boolean ok(int k) {// 檢查顏色可用性 for (int j=1。j=n。j++) if (a[k][j] amp。amp。 (x[j]==x[k])) return false。 return true。 } } 復(fù)雜度分析 圖 m可著色問題的解空間樹中內(nèi)結(jié)點個數(shù)是 對于每一個內(nèi)結(jié)點，在最壞情況下，用 ok檢查當(dāng)前擴展結(jié)點的每一個兒子所相應(yīng)的顏色可用性需耗時 O(mn)。因此，回溯法總的時間耗費是 ???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。amp。 a[x[n]][1] amp。amp。 (bestc == || cc+a[x[n 1]][x[n]]+a[x[n]][1]bestc)) { 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]] amp。amp。 (bestc == || cc+a[x[i 1]][x[j]]bestc)) {// 搜索子樹 (x, i, j)。 cc+=a[x[i 1]][x[i]]。 backtrack(i + 1)。 cc=a[x[i 1]][x[i]]。 (x, i, j)。 } } 復(fù)雜度分析 算法 backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解 O((n1)!)次，每次更新 bestx需計算時間O(n)，從而整個算法的計算時間復(fù)雜性為 O(n!)。 24 圓排列問題 給定 n個大小不等的圓 c1,c2,… ,，現(xiàn)要將這 n個圓排進一個矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從 n個圓的所有排列中找出有最小長度的圓排列。例如，當(dāng) n=3，且所給的 3個圓的半徑分別為 1， 1， 2時，這 3個圓的最小長度的圓排列如圖所示。其最小長度為 242 ?25 圓排列問題 private static float center(int t) {// 計算當(dāng)前所選擇圓的圓心橫坐標 float temp=0。 for (int j=1。jt。j++) { float valuex=x[j]+*(r[t]*r[j])。 if (valuextemp) temp=valuex。 } return temp。 } private static void pute() {// 計算當(dāng)前圓排列的長度 float low=0, high=0。 for (int i=1。i=n。i++) { if (x[i]r[i]low) low=x[i]r[i]。 if (x[i]+r[i]high) high=x[i]+r[i]。 } if (highlowmin) min=highlow。 } private static void backtrack(int t) { if (tn) pute()。 else for (