【正文】 k= =n) //得到一個(gè)作業(yè)安排 if (bestTimesum2[k]) bestTime=sum2[k]。 sum2[i]=0。 kn) k=k+1。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 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皇后問(wèn)題的搜索過(guò)程 算法設(shè)計(jì)與分析 清華大學(xué)出版社 算法 —— n皇后問(wèn)題 void Queue(int n) { for (i=1。 k=n。 i=n。 //處理下一個(gè)頂點(diǎn) else { color[k]=0。 3． while (k=1) 依次考察每一種顏色 ， 若頂點(diǎn) k的著色與其他頂點(diǎn)的著色不發(fā)生沖突 ， 則轉(zhuǎn)步驟 ；否則 ， 搜索下一個(gè)顏色； 若頂點(diǎn)已全部著色 ， 則輸出數(shù)組 color[n]， 返回； 否則 ， 若頂點(diǎn) k是一個(gè)合法著色 ， 則 k=k+1， 轉(zhuǎn)步驟 3處理下一個(gè)頂點(diǎn)； 否則 ， 重置頂點(diǎn) k的著色情況 ， k=k1， 轉(zhuǎn)步驟 3回溯； 算法設(shè)計(jì)與分析 清華大學(xué)出版社 算法 —— 圖著色問(wèn)題 void GraphColor(int n, int c[ ][ ], int m) //所有數(shù)組下標(biāo)從 1開(kāi)始 { for (i=1。（ 2）排列樹(shù) （ Permutation Trees）：當(dāng)所給問(wèn)題是確定 n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹(shù)稱為排列樹(shù)。 回溯法的遞歸形式的一般框架如下： 算法設(shè)計(jì)與分析 清華大學(xué)出版社 回溯法的一般框架 —— 迭代形式 1． X={ }。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 例如，對(duì)于 n=3的 0/1背包問(wèn)題，三個(gè)物品的重量為 {20, 15, 10}，價(jià)值為 {20, 30, 25}，背包容量為25，從圖 ，搜索過(guò)程如下： 1 不可行解 價(jià)值 =20 價(jià)值 =55 價(jià)值 =30 價(jià)值 =25 價(jià)值 =0 1 1 1 1 0 0 0 0 0 0 1 1 2 8 11 12 14 15 13 10 6 9 不可行解 算法設(shè)計(jì)與分析 清華大學(xué)出版社 再如，對(duì)于 n=4的 TSP問(wèn)題，其代價(jià)矩陣如圖 ， C= ∞ 3 6 7 12 ∞ 2 8 8 6 ∞ 2 3 7 6 ∞ 圖 TSP問(wèn)題的代價(jià)矩陣 算法設(shè)計(jì)與分析 清華大學(xué)出版社 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問(wèn)題的搜索空間 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è)計(jì)與分析 清華大學(xué)出版社 ? 回溯法的搜索過(guò)程涉及的結(jié)點(diǎn) （ 稱為搜索空間 ）只是整個(gè)解空間樹(shù)的一部分 ， 在搜索過(guò)程中 ， 通常采用兩種策略避免無(wú)效搜索： （ 1） 用 約束條件 剪去得不到可行解的子樹(shù)； （ 2） 用 目標(biāo)函數(shù) 剪去得不到最優(yōu)解的子樹(shù) 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 對(duì)于任何一個(gè)問(wèn)題 ， 可能解的 表示方式 和它相應(yīng)的 解釋 隱含了解空間及其大小 。 return。 重置 Sk， 使得下一個(gè)元素排在第 1位 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 圖問(wèn)題中的回溯法 圖著色問(wèn)題 哈密頓回路問(wèn)題 算法設(shè)計(jì)與分析 清華大學(xué)出版社 圖著色問(wèn)題 圖著色問(wèn)題描述為：給定無(wú)向連通圖 G=(V, E)和正整數(shù) m，求最小的整數(shù) m，使得用 m種顏色對(duì) G中的頂點(diǎn)著色，使得任意兩個(gè)相鄰頂點(diǎn)著色不同。 k= =n) //求解完畢 ， 輸出解 { for (i=1。 visited[1]=1。 c[x[k1]][x[k]]= =1) break。 k=k1。amp?？梢宰C明，存在一個(gè)最優(yōu)作業(yè)調(diào)度使得在機(jī)器 1和機(jī)器 2上作業(yè)以相同次序完成。 else x[k]=x[k]+1。 } 算法設(shè)計(jì)與分析 清華大學(xué)出版社 實(shí)驗(yàn)項(xiàng)目 —— 0/1背包問(wèn)題 1. 實(shí)驗(yàn)題目 給定 n種物品和一個(gè)容量為 C的背包 ， 物品 i的重量是 wi，其價(jià)值為 vi， 0/1背包問(wèn)題是如何選擇裝入背包的物品 （ 物品不可分割 ） ， 使得裝入背包中物品的總價(jià)值最大 ? 2. 實(shí)驗(yàn)?zāi)康? （ 1） 掌握回溯法的設(shè)計(jì)思想； （ 2） 掌握解空間樹(shù)的構(gòu)造方法 ， 以及在求解過(guò)程中如何存儲(chǔ)求解路徑； （ 3） 考察回溯法求解問(wèn)題的有效程度 。 sum2[k]=max(sum1[k], sum2[k1])+b[x[k]]。 } 算法設(shè)計(jì)與分析 清華大學(xué)出版社 批處理作業(yè)調(diào)度問(wèn)題 n個(gè)作業(yè) {1, 2, … , n}要在兩臺(tái)機(jī)器上處理 ， 每個(gè)作業(yè)必須先由機(jī)器 1處理 ， 然后再由機(jī)器 2處理 ，機(jī)器 1處理作業(yè) i所需時(shí)間為 ai， 機(jī)器 2處理作業(yè) i所需時(shí)間為 bi（ 1≤ i≤ n） ， 批處理作業(yè)調(diào)度問(wèn)題要求確定這 n個(gè)作業(yè)的最優(yōu)處理順序 ， 使得從第 1個(gè)作業(yè)在機(jī)器 1上處理開(kāi)始 ， 到最后一個(gè)作業(yè)在機(jī)器 2上處理結(jié)束所需時(shí)間最少 。 !Place(k)) x[k]=x[k]+1。 }