【正文】 (b) 三維搜索空間的解 圖 錯誤的解空間將不能搜索到正確答案 例如：桌子上有 6根火柴棒，要求以這 6根火柴棒為邊搭建 4個等邊三角形。 算法設(shè)計與分析 清華大學出版社 例如，對于 n=3的 0/1背包問題，三個物品的重量為 {20, 15, 10}，價值為 {20, 30, 25}，背包容量為25，從圖 ，搜索過程如下： 1 不可行解 價值 =20 價值 =55 價值 =30 價值 =25 價值 =0 1 1 1 1 0 0 0 0 0 0 1 1 2 8 11 12 14 15 13 10 6 9 不可行解 算法設(shè)計與分析 清華大學出版社 再如，對于 n=4的 TSP問題，其代價矩陣如圖 ， C= ∞ 3 6 7 12 ∞ 2 8 8 6 ∞ 2 3 7 6 ∞ 圖 TSP問題的代價矩陣 算法設(shè)計與分析 清華大學出版社 2 3 4 4 2 2 1 2 3 1 3 4 1 3 1 3 1 2 3 2 1 2 1 4 2 4 1 4 2 2 4 3 4 1 2 3 1 2 4 1 3 4 圖 TSP問題的搜索空間 5 47 54 4 11 27 46 48 51 53 58 3 8 13 24 29 35 40 45 50 55 60 2 18 34 24 1 2 3 4 1 算法設(shè)計與分析 清華大學出版社 ? 回溯法的搜索過程涉及的結(jié)點 （ 稱為搜索空間 ）只是整個解空間樹的一部分 ， 在搜索過程中 ， 通常采用兩種策略避免無效搜索： （ 1） 用 約束條件 剪去得不到可行解的子樹； （ 2） 用 目標函數(shù) 剪去得不到最優(yōu)解的子樹 。 if (X是最終解 ) flag=true。 回溯法的遞歸形式的一般框架如下： 算法設(shè)計與分析 清華大學出版社 回溯法的一般框架 —— 迭代形式 1． X={ }。 轉(zhuǎn)步驟 4。（ 2）排列樹 （ Permutation Trees）：當所給問題是確定 n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹。而 4皇后問題的解空間樹中的結(jié)點總數(shù)為 65，則回溯法求解 4皇后問題產(chǎn)生的搜索空間的結(jié)點數(shù)大約是解空間樹中的結(jié)點總數(shù)的 14/65≈ %，這說明回溯法的效率大大高于蠻力窮舉法。 3． while (k=1) 依次考察每一種顏色 ， 若頂點 k的著色與其他頂點的著色不發(fā)生沖突 ， 則轉(zhuǎn)步驟 ；否則 ， 搜索下一個顏色； 若頂點已全部著色 ， 則輸出數(shù)組 color[n]， 返回； 否則 ， 若頂點 k是一個合法著色 ， 則 k=k+1， 轉(zhuǎn)步驟 3處理下一個頂點； 否則 ， 重置頂點 k的著色情況 ， k=k1， 轉(zhuǎn)步驟 3回溯； 算法設(shè)計與分析 清華大學出版社 算法 —— 圖著色問題 void GraphColor(int n, int c[ ][ ], int m) //所有數(shù)組下標從 1開始 { for (i=1。amp。 //處理下一個頂點 else { color[k]=0。 } 算法設(shè)計與分析 清華大學出版社 哈密頓回路問題 假定圖 G=(V, E)的頂點集為 V={1, 2, … , n}， 則哈密頓回路的可能解表示為 n元組 X=(x1, x2, … , xn)，其中 ， xi∈ {1, 2, … , n} ， 并有如下約束條件： (xi, xi+1)∈ E (1≤i≤n－ 1) (xn, x1)∈ E xi≠xj (1≤i, j≤n， i≠j) 算法設(shè)計與分析 清華大學出版社 1 2 4 3 5 (a) 一個無向圖 (b) 哈密頓回路的搜索空間 x4=4 x3=3 x2=2 2 1 x1=1 4 7 11 17 16 x5=5 x4=5 3 5 10 8 9 6 12 13 14 15 21 20 18 19 x5=4 算法設(shè)計與分析 清華大學出版社 算法 —— 哈密頓回路問題 1． 將頂點數(shù)組 x[n]初始化為 0， 標志數(shù)組 visited[n]初始化為 0； 2． k=1。 i=n。amp。 k=n。 visited[x[k]]=0。 算法設(shè)計與分析 清華大學出版社 Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) Q Q Q 回溯法求解 4皇后問題的搜索過程 算法設(shè)計與分析 清華大學出版社 算法 —— n皇后問題 void Queue(int n) { for (i=1。 //搜索下一列 if (x[k]=n amp。 kn) k=k+1。 算法設(shè)計與分析 清華大學出版社 顯然，批處理作業(yè)的一個最優(yōu)調(diào)度應(yīng)使機器 1沒有空閑時間，且機器 2的空閑時間最小。 sum2[i]=0。 if (sum2[k]bestTime) break。 k= =n) //得到一個作業(yè)安排 if (bestTimesum2[k]) bestTime=sum2[k]。 算法設(shè)計與分析 清華大學出版社 3. 實驗要求 （ 1） 設(shè)計可能解的表示方式 ， 構(gòu)成解空間樹； （ 2） 設(shè)計回溯算法完成問題求解； （ 3） 設(shè)計測試數(shù)據(jù) ， 統(tǒng)計搜索空間的結(jié)點數(shù)；