【正文】 n并且 1≤xi≤n， 即第 i個(gè)皇后放在第 i行第xi列上 。 //在下一列放置第 k個(gè)皇后 while (x[k]=n amp。 return。 i++) if (x[k]= =x[i] | | abs(ki)= =abs(x[k]x[i])) return false。 i=n。 while (k=1) { x[k]=x[k]+1。 kn) k=k+1。 i++) if (x[i]= =x[k]) return false。 } } } bool Ok(int k) //作業(yè) k與其他作業(yè)是否發(fā)生沖突 （ 重復(fù) ） { for (i=1。 if (x[k]=n amp。 //初始迭代使用 k=1。 作業(yè) 1:2 作業(yè) 2:3 作業(yè) 3:2 空閑 :2 作業(yè) 1:1 機(jī)器 1 機(jī)器 2 作業(yè) 2:1 作業(yè) 3:3 (a) 調(diào)度方案 (1, 2, 3)， 最后完成時(shí)間為 10 作業(yè) 1:2 作業(yè) 2:3 作業(yè) 3:2 空閑 :2 作業(yè) 1:1 機(jī)器 1 機(jī)器 2 作業(yè) 2:1 作業(yè) 3:3 (b) 調(diào)度方案 (1, 3, 2)， 最后完成時(shí)間為 8 算法設(shè)計(jì)與分析 清華大學(xué)出版社 作業(yè) 2:3 作業(yè) 1:2 作業(yè) 3:2 空閑 作業(yè) 2:1 機(jī)器 1 機(jī)器 2 作業(yè) 1:1 作業(yè) 3:3 (c) 調(diào)度方案 (2, 1, 3)， 最后完成時(shí)間為 10 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :3 作業(yè) 2:1 機(jī)器 1 機(jī)器 2 作業(yè) 1:1 作業(yè) 3:3 (d) 調(diào)度方案 (2, 3, 1)， 最后完成時(shí)間為 9 算法設(shè)計(jì)與分析 清華大學(xué)出版社 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :2 作業(yè) 2:1 機(jī)器 1 機(jī)器 2 作業(yè) 1:1 作業(yè) 3:3 (e) 調(diào)度方案 (3, 1, 2)， 最后完成時(shí)間為 8 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :2 作業(yè) 2:1 機(jī)器 1 機(jī)器 2 作業(yè) 2:1 作業(yè) 3:3 (f) 調(diào)度方案 (3, 2, 1)， 最后完成時(shí)間為 8 算法設(shè)計(jì)與分析 清華大學(xué)出版社 算法 —— 批處理作業(yè)調(diào)度問題 void BatchJob(int n, int a[ ], int b[ ], int amp。 } } } bool Place(int k) //考察皇后 k放置在 x[k]列是否發(fā)生沖突 { for (i=1。 i=n。 k=1。問題是：在 8 8的棋盤上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。 } else if (x[k]=n amp。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 if (x[k]=n amp。 } k=1。 從頂點(diǎn) 1出發(fā)構(gòu)造哈密頓回路； 3． while (k=1) x[k]=x[k]+1， 搜索下一個(gè)頂點(diǎn) 。 ik。 i++) coutcolor[i]。 k=1。 例如， 5元組 (1, 2, 2, 3, 1)表示對(duì)具有 5個(gè)頂點(diǎn)的無向圖的一種著色，頂點(diǎn) 1著顏色 1，頂點(diǎn) 2著顏色 2，頂點(diǎn) 3著顏色 2，如此等等。 基本思想：假定約束函數(shù)是靜態(tài)的（即在回溯法的執(zhí)行過程中，約束函數(shù)不隨算法所獲得信息的多少而動(dòng)態(tài)改變），在解空間樹上產(chǎn)生一條隨機(jī)路徑，然后沿此路徑估算解空間樹中滿足約束條件的結(jié)點(diǎn)總數(shù) m。 //回溯 5． if flag 輸出解 X。 4． while (k=1) 當(dāng) (Sk沒有被窮舉 )循環(huán)執(zhí)行下列操作 xk=Sk中的下一個(gè)元素 。 主算法 1． X={ }。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 回溯法的求解過程 由于問題的解向量 X=(x1, x2, … , xn)中的每個(gè)分量xi(1≤i≤n)都屬于一個(gè)有限集合 Si={ai1, ai2, … , airi}， 因此 ， 回溯法可以按某種順序 （ 例如字典序 ） 依次考察笛卡兒積S1 S2 … Sn中的元素 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 問題的解空間一般用 解空間樹 （ Solution Space Trees,也稱狀態(tài)空間樹）的方式組織，樹的根結(jié)點(diǎn)位于第 1層，表示搜索的初始狀態(tài)，第 2層的結(jié)點(diǎn)表示對(duì)解向量的第一個(gè)分量做出選擇后到達(dá)的狀態(tài)，第 1層到第 2層的邊上標(biāo)出對(duì)第一個(gè)分量選擇的結(jié)果，依此類推，從樹的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑就構(gòu)成了解空間的一個(gè)可能解。 解空間也就是進(jìn)行窮舉的搜索空間 ， 所以 ， 解空間中應(yīng)該包括所有的可能解 。 2 4 3 4 2 2 3 4 3 4 1 3 1 4 2 4 1 2 1 2 3 3 1 2 1 3 4 1 3 1 3 1 2 3 2 1 2 1 4 2 4 1 4 3 4 2 2 4 3 4 1 2 3 1 2 4 1 3 4 圖 n=4的 TSP問題的解空間樹 5 7 10 12 15 17 21 23 26 28 31 33 37 39 42 44 47 49 52 54 57 59 62 64 4 6 9 11 14 16 20 22 25 27 30 32 36 38 41 43 46 48 51 53 56 58 61 63 3 8 13 19 24 29 35 40 45 50 55 60 2 18 34 24 1 1 2 3 4 3 4 算法設(shè)計(jì)與分析 清華大學(xué)出版社 解空間樹的動(dòng)態(tài)搜索（ 1） 回溯法從根結(jié)點(diǎn)出發(fā) ， 按照深度優(yōu)先策略遍歷解空間樹 ， 搜索滿足約束條件的解 。如果問題只希望得到一個(gè)解 ， 則結(jié)束搜索 ， 否則繼續(xù)搜索其他解； （ 2） 如果 X=(x1, x2, … , xi＋ 1)是問題的部分解 ， 則繼續(xù)構(gòu)造解向量的下一個(gè)分量； （ 3） 如果 X=(x1, x2, … , xi＋ 1)既不是問題的部分解也不是問題的最終解 ， 則存在下面兩種情況： ① 如果 xi+1= ai＋ 1k不是集合 Si＋ 1的最后一個(gè)元素 ， 則令 xi+1= ai＋1k＋ 1， 即選擇 Si+1的下一個(gè)元素作為解向量 X的第 i+1個(gè)分量； ② 如果 xi+1= ai＋ 1k是集合 Si＋ 1的最后一個(gè)元素 ， 就回溯到 X=(x1, x2, … , xi)， 選擇 Si的下一個(gè)元素作為解向量 X的第 i個(gè)分量 ， 假