【正文】 else { //回溯 x[k]=0。 //搜索下一頂點(diǎn) while (x[k]=n) if (visited[x[k]]= =0 amp。 return true。 //搜索下一個(gè)顏色 if (color[k]=m amp。例如，圖 4皇后問(wèn)題，搜索空間的結(jié)點(diǎn)數(shù)取 4條隨機(jī)路徑結(jié)點(diǎn)總數(shù)的平均值，結(jié)果為 14。 else if (X為部分解 ) k=k+1。 將 xk加入 X。 確定正確的解空間很重要 ， 如果沒(méi)有確定正確的解空間就開(kāi)始搜索 ， 可能會(huì)增加很多重復(fù)解 ，或者根本就搜索不到正確的解 。 ? 需要注意的是 ， 問(wèn)題的解空間樹(shù)是虛擬的 ， 并不需要在算法運(yùn)行時(shí)構(gòu)造一棵真正的樹(shù)結(jié)構(gòu) ， 只需要存儲(chǔ)從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑 。 3． k=1。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 用概率方法估算回溯法所產(chǎn)生的結(jié)點(diǎn)數(shù)。 i++ ) //將數(shù)組 color[n]初始化為 0 color[i]=0。 //回溯 } } } bool Ok(int k) //判斷頂點(diǎn) k的著色是否發(fā)生沖突 { for (i=1。 visited[i]=0。 return。 i++) //初始化 x[i]=0。 //重置 x[k]，回溯 k=k1。 sum2[0]=0。 //重置 x[k]， 回溯 k=k1。 //安排下一個(gè)作業(yè) else { if (x[k]=n amp。 i++) { x[i]=0。 } 算法設(shè)計(jì)與分析 清華大學(xué)出版社 else if (x[k]=n amp。 由于兩個(gè)皇后不能位于同一列上 ， 所以 ， 解向量 X必須滿足約束條件： xi≠xj （ 式 ） 算法設(shè)計(jì)與分析 清華大學(xué)出版社 1 2 3 4 1 2 3 4 皇后 1 皇后 2 皇后 3 皇后 4 圖 四皇后問(wèn)題 為了簡(jiǎn)化問(wèn)題，下面討論四皇后問(wèn)題。amp。(x[k1],x[k])∈ E)， 轉(zhuǎn)步驟 。amp。在圖著色問(wèn)題的解空間樹(shù)中，如果從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)一個(gè)部分解，也就是所有的顏色指派都沒(méi)有沖突，則在當(dāng)前結(jié)點(diǎn)處選擇第一棵子樹(shù)繼續(xù)搜索，也就是為下一個(gè)頂點(diǎn)著顏色 1，否則，對(duì)當(dāng)前子樹(shù)的兄弟子樹(shù)繼續(xù)搜索，也就是為當(dāng)前頂點(diǎn)著下一個(gè)顏色，如果所有 m種顏色都已嘗試過(guò)并且都發(fā)生沖突，則回溯到當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)處，上一個(gè)頂點(diǎn)的顏色被改變，依此類(lèi)推。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 在用回溯法求解問(wèn)題時(shí)，常常遇到兩種典型的解空間樹(shù)： （ 1） 子集樹(shù) （ Subset Trees）：當(dāng)所給問(wèn)題是從 n個(gè)元素的集合中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹(shù)稱(chēng)為子集樹(shù)。 4. if (flag) 輸出解 X。 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問(wèn)題的解空間樹(shù) 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é)出版社 解空間樹(shù)的動(dòng)態(tài)搜索（ 1） 回溯法從根結(jié)點(diǎn)出發(fā) ， 按照深度優(yōu)先策略遍歷解空間樹(shù) ， 搜索滿足約束條件的解 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 問(wèn)題的解空間一般用 解空間樹(shù) （ Solution Space Trees,也稱(chēng)狀態(tài)空間樹(shù)）的方式組織，樹(shù)的根結(jié)點(diǎn)位于第 1層，表示搜索的初始狀態(tài)，第 2層的結(jié)點(diǎn)表示對(duì)解向量的第一個(gè)分量做出選擇后到達(dá)的狀態(tài)，第 1層到第 2層的邊上標(biāo)出對(duì)第一個(gè)分量選擇的結(jié)果，依此類(lèi)推，從樹(shù)的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑就構(gòu)成了解空間的一個(gè)可能解。 主算法 1． X={ }。 //回溯 5． if flag 輸出解 X。 例如， 5元組 (1, 2, 2, 3, 1)表示對(duì)具有 5個(gè)頂點(diǎn)的無(wú)向圖的一種著色，頂點(diǎn) 1著顏色 1，頂點(diǎn) 2著顏色 2，頂點(diǎn) 3著顏色 2，如此等等。 i++) coutcolor[i]。 從頂點(diǎn) 1出發(fā)構(gòu)造哈密頓回路； 3． while (k=1) x[k]=x[k]+1， 搜索下一個(gè)頂點(diǎn) 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 if (x[k]=n amp。問(wèn)題是：在 8 8的棋盤(pán)上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。 i=n。 作業(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)， 最后