【正文】 5, 25}，背包容量為 30，從其解空間樹的根結點開始搜索，搜索過程如下： A Cr=C=30， V=0 H I w1=16， v1=45 Cr=14， V=45 B 1 D Crw2 不可行解 1 J Crw3 不可行解 1 F w2=15， v2=25 Cr=15， V=25 1 C Cr=30， V=0 0 Cr=14 V=45 E 0 L w3=15， v3=25 Cr=0， V=50 5045 x=(0,1,1) 1 K Cr=14 V=45 x=(1,0,0) 0 M 2550 不是 最優(yōu) 解 0 N O G V=25 不包含 最優(yōu)解 0 2021年 11月 12日 22 回溯法的基本思想 ?回溯法是一種通用性解法，可以將回溯法看作是帶優(yōu)化的窮舉法。i=g(n,t)。bound(t)) backtrack(t+1)。i++) { x[t]=h(i)。 else t++。i=1。bound(t)) backtrack(t+1)。i++) { swap(x[t], x[i])。 swap(x[t], x[i])。 常用剪枝函數： 用約束函數在擴展結點處剪去不滿足約束的子樹； 用限界函數剪去得不到最優(yōu)解的子樹。 而顯式地存儲整個解空間則需要O(2h(n))或 O(h(n)!)內存空間 。 ? 如果 w=[20,40,40]，則無法將這 3個集裝箱都裝上輪船。 nixcxwxwiniiiniii????????1},1,0{s . t .m ax1112021年 11月 12日 31 ? 解空間：子集樹 ? 可行性約束函數 (選擇當前元素 )： ? 上界函數 (不選擇當前元素 )： 當前載重量 cw+剩余集裝箱的重量 r當前最優(yōu)載重量 bestw 11cxwniii ???1 0 1 1 1 1 0 0 0 不滿足 約束函數 不滿足 上界函數 0 0 1 2021年 11月 12日 32 算法描述 void backtrack (int i) {// 搜索第 i層結點 if (i n) // 到達葉結點 更新最優(yōu)解 bestx,bestw。 cw += w[i]。 backtrack(i + 1)。 2021年 11月 12日 33 習題 51 2021年 11月 12日 34 2021年 11月 12日 35 習題 52 2021年 11月 12日 36 2021年 11月 12日 37 2021年 11月 12日 38 提綱 一、回溯法的算法框架 二、裝載問題 三、 n后問題 四、 01背包問題 五、最大團問題 六、圖的 m著色問題 七、旅行售貨員問題 2021年 11月 12日 39 N 皇后問題是由八皇后問題演化而來的。 引言 2021年 11月 12日 40 問題定義 ? 八皇后問題是一個非常著名的問題，最初是由著名數學家高斯提出的。 ? 每次擺放都要檢查當前擺放是否可行。 N后問題回溯算法 2021年 11月 12日 43 皇后不在同一行上同一列上 : 設解向量： (x1, x2, … , xn)， x[i]表示皇后 i放在棋盤的第 i行的第 x[i]列。j++) if ((abs(kj)==abs(x[j]x[k]))||(x[j]==x[k])) return false。 While(k0){ x[k]+=1。 if(x[k]=n) if(k==n) sum++。 } } 2021年 11月 12日 48 問題的解 ? 4皇后問題： * * * * * * * * ? 8皇后問題： 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q 8 Q 1 2 3 4 5 6 7 8 2021年 11月 12日 49 參考文獻 [1]張萬軍 ， 《 N 皇后問題回溯算法探討 》 ， 宜賓學院學報 ， [2]韓宇南 , 呂英華 , 黃小紅 ， 《 并行改進回溯算法實現 N 皇后問題的快速計 數 》 ， ?求路徑：只需要找到一條路徑便可以得到解。 2021年 11月 12日 54 ? 解空間：子集樹 ? 可行性約束函數： 或： cw+wi=c cxwijjj ???1templateclass Typew, class Typep Typep KnapTypew, Typep::Bound(int i) {// 計算上界 Typew cleft = c cw。 w[i] = cleft) { cleft = w[i]。 return b。 cp += p[i]。 } if (bound (i+1) bestp) //x[i]=0，否則剪去右子樹 backtrack(i+1)。如果 U?V，且對任意 u， v?U有 (u， v)?E，則稱 U是 G的完全子圖。 ? 獨立集 ： G的空子圖 U是 G的獨立集當且僅當 U不包含在 G的更大的空子圖中。 1 2 4 5 3 1 2 4 5 3 2021年 11月 12日 59 問題分析 ? 解空間：子集樹 ? 可行性約束函數： 頂點 i到已選入的頂點集中每一個頂點都有邊相連。 j++) bestx[j] = x[j]。 // 檢查頂點 i 與當前團的連接 for (int j = 1。 a[i][j] == 0) { // i與 j不相連 OK = 0。 Backtrack(i+1)。 Backtrack(i+1)。是否有一種著色法使 G中每條邊的 2個頂點著不同顏色。 2021年 11月 12日 63 問題定義 ? 可平面圖：如果一個圖的所有頂點和邊都能用某種方式畫在一個平面上且沒有任何兩邊相交，則稱這個圖是可平面圖。 ? 解空間：完全 m叉樹 ? 可行性約束函數：頂點 i與已著色的相鄰頂點顏色不重復。 i++) cout x[i] 39。i=m。j=n。 return true。經典 ./ 可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發(fā)，需要經過所有城市后，回到出發(fā)地。由于其在交通運輸、電路板線路設計以及物流配送等領域內有著廣泛的應用，國內外學者對其進行了大量的研究。換一種說法，對于一個給定的網絡，確定起點和終點后，如果存在一條路徑，穿過這個網絡，我們就說這個網絡存在哈密頓路徑。 2021年 11月 12日 71 從圖中的任意一點出發(fā)，路途中經過圖中每一個結點當且僅當一次，則成為哈密頓回路。 平凡圖是哈密頓圖。 2021年 11月 12日 75 問題定義 ? 某售貨員要到若干城市去推銷商品，已知各城市之間的路程或旅費，他要選定一條從駐地出發(fā)，經過每個城市僅一遍，最后回到駐地的路線，使總的路程或總的旅費最小。 ? 上界函數： 當前費用 +頂點 x[i1]與頂點 x[i]的邊的權值 當前最優(yōu)值。amp。 bestc = cc + a[x[n1]][x[n]] + a[x[n]][1]。amp。 cc = a[x[i1]][x[i]]