【正文】 c void pute() {// 計(jì)算當(dāng)前圓排列的長度 float low=0, high=0。jt。圓排列問題要求從 n個(gè)圓的所有排列中找出有最小長度的圓排列。 cc=a[x[i 1]][x[i]]。amp。 bestc = cc+a[x[n 1]][x[n]]+a[x[n]][1]。amp。 } } 復(fù)雜度分析 圖 m可著色問題的解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是 對于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用 ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí) O(mn)。j++) if (a[k][j] amp。i++) { x[t]=i。 22 ?解向量： (x1, x2, … , x n)表示頂點(diǎn) i所著顏色 x[i] ?可行性約束函數(shù)：頂點(diǎn) i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。是否有一種著色法使 G中每條邊的 2個(gè)頂點(diǎn)著不同顏色。同時(shí)注意到：從 Si+1到 Si，如果找到一個(gè)更大的團(tuán)，那么 vi必然屬于找到的團(tuán)，此時(shí)有 Si=Si+1+1，否則 Si=Si+1。例如在搜索之前可以將頂點(diǎn)按度從小到大排序。 } if ( + n i bestn) {// 進(jìn)入右子樹 x[i] = 0。 } if (ok) {// 進(jìn)入左子樹 x[i] = 1。 j++) if (x[j] == 1 amp。 return。 private static void backtrack(int i) { if (i n) {// 到達(dá)葉結(jié)點(diǎn) for (int j = 1。 對于任一無向圖 G=(V， E)其 補(bǔ)圖 G=(V1， E1)定義為： V1=V，且 (u， v)?E1當(dāng)且僅當(dāng) (u， v)?E。 G的 最大團(tuán) 是指 G中所含頂點(diǎn)數(shù)最多的團(tuán)。 return bound。 w[i] = cleft) { cleft = w[i]。 } 17 01背包問題 ?解空間：子集樹 ?可行性約束函數(shù)： ?上界函數(shù)： 11 cxwniii ???private static double bound(int i) {// 計(jì)算上界 double cleft = c cw。 else for (int i=1。jk。 15 n后問題 在 n n格的棋盤上放置彼此不受攻擊的 n個(gè)皇后。j=t。j++) { p[j][tj+1]=p[j1][tj+1]^p[j1][tj+2]。i++) { p[1][t]=i。 ?可行性約束函數(shù)：當(dāng)前符號三角形所包含的“ +”個(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。 2個(gè)同號下面都是 “ +”， 2個(gè)異號下面都是 “ ”。 // 各作業(yè)所需的處理時(shí)間 static int [] x。 } f1=m[x[j]][1]。 f+=f2[i]。 } else for (int j = i。 12 批處理作業(yè)調(diào)度 ?解空間：排列樹 private static void backtrack(int i) { if (i n) { for (int j = 1。所有作業(yè)在機(jī)器 2上完成處理的時(shí)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。 } 11 批處理作業(yè)調(diào)度 給定 n個(gè)作業(yè)的集合 {J1,J2,…,J n}。 cw = w[i]。 r = w[i]。 nixcxwxwiniiiniii????????1},1,0{s .t .m a x111 用回溯法設(shè)計(jì)解裝載問題的 O(2n)計(jì)算時(shí)間算法。 容易證明，如果一個(gè)給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。 if (legal(t)) backtrack(t+1)。 } } void backtrack (int t) { if (tn) output(x)。 else for (int i=0。bound(t)) { if (solution(t)) output(x)。i=g(n,t)。bound(t)) backtrack(t+1)。i=g(n,t)。而顯式地存儲整個(gè)解空間則需要 O(2h(n))或 O(h(n)!)內(nèi)存空間。 常用剪枝函數(shù)： 用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹； 用限界函數(shù)剪去得不到最優(yōu)解的子樹。 注意：同一個(gè)問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更小（存儲量少，搜索方法簡單）。 3 問題的解空間 ? 問題的解向量：回溯法希望一個(gè)問題的解能夠表示成一個(gè) n元式 (x1,x2,… ,xn)的形式。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 ? 解空間：對于問題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。 具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法 5 回溯法的基本思想 (1)針對所給問題，定義問題的解空間； (2)確定易于搜索的解空間結(jié)構(gòu)； (3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計(jì)算空間通常為 O(h(n))。 else for (int i=f(n,t)。amp。 while (t0) { if (f(n,t)=g(n,t)) for (int i=f(n,t)。amp。 } } 8 子集樹與排列樹 遍歷子集樹需 O(2n)計(jì)算時(shí)間 遍歷排列樹需要 O(n!)計(jì)算時(shí)間 void backtrack (int t) { if (tn) output(x)。 if (legal(t)) backtrack(t+1)。i++) { swap(x[t], x[i])。如果有，找出一種裝載方案。由此可知，裝載問題等價(jià)于以下特殊的 01背包問題。return。 backtrack(i + 1)。 } r += w[i]。對于一個(gè)確定的作業(yè)調(diào)度，設(shè) Fji是作業(yè) i在機(jī)器 j上完成處理的時(shí)間。易見，最佳調(diào)度方案是 1,3,2，其完成時(shí)間和為18。 bestf = f。 f2[i]=((f2[i1]f1)?f2[i1]:f1)+m[x[j]][2]。 (x,i,j)。 // 當(dāng)前最優(yōu)值 static int [][] m。 // 機(jī)器 2完成處理時(shí)間