【文章內(nèi)容簡介】 versity 16 應(yīng)用回溯法求解的步驟 在用回溯法搜索解空間樹時，利用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹 (如前面例子中的 D和 J） ,從而提高搜索效率。 綜上所述，應(yīng)用回溯法求解通常包含以下 三個步驟 ： （ 1）針對所給問題，定義問題的解空間。 （ 2）確定易于求解的解空間結(jié)構(gòu)；并組織成解空間樹。 （ 3）以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用約束函數(shù)避免無效搜索。 Jin Zheng,Central South University 17 回溯算法的形式描述 ? 假設(shè) 1：回溯法要找出所有可行解（即答案結(jié)點） ? 假設(shè) 2: (x1,x2,… ,x i1)是解空間樹中由根到一個結(jié)點的路徑 ,而 T(x1,x2,… ,x i1)是下述所有結(jié)點 xi的集合 ,它使得對于每一個 xi, (x1,x2,… ,x i1)是一條由根到結(jié)點 xi 的路徑 . ? 假設(shè) 3:一些 約束函數(shù) Bi,如果 Bi (x1,x2,… ,x i)為假 , 表示路徑 (x1,x2,… ,x i)不能延伸到一個答案結(jié)點 (可行解 )。反之，表示可能延伸，于是解向量 X(1:n)中第 i個分量就是那些選自集合 T (x1,x2,… ,x i1) 且使Bi為真的 xi Jin Zheng,Central South University 18 procedure BACAKTRACE(n) k =1 。 //從根開始 while (k0) do if T (x1， x2， … ， x k1)的值還未取遍 then {xk = T (x1， x2， … ， x k1)中未取過的值； if Bk (x1， x2， … ， x k) then { (x1， x2， … ， x k)被激活； if k ==n then 輸出 (x1， x2， … ， x n)； else k =k+1； } // 深度擴展搜索 } else k = k 1 // 試探完了所有的 x k，回溯 end BACAKTRACE 狀態(tài)節(jié)點 (x1， x2， … ， x k1)被激活以后，滿足顯約束的xk的全體即為 Tk(x1， x2， … ， x k1)，而滿足隱約束的 xk當(dāng)且僅當(dāng)邏輯表達式 Bk(x1， x2， … ， x k)為真。 Jin Zheng,Central South University 19 procedure RBACAKTRACE(k) if k 〉 n then return ； else for x k ? T (x1， x2， … ， x k1) and Bk(x1，x2， … ， x k) do { if k ==n then 輸出 (x1， x2， … ， x n)； RBACAKTRACE(k+1)； // 深度擴展搜索 } end BACAKTRACE n是全局變量，控制遞歸深度 回溯法的一般方法遞歸形式描述 Jin Zheng,Central South University 20 要求找出在一個 n n棋盤上放置 n個皇后并使其不能互相攻擊 (不在同行同列、不在同斜角線上 ) 的所有方案。用 n元組 (x1， x2， … ， xn)， 為了方便，可以討論 n=4，即 4皇后問題。 Example１ nQueens Problem Jin Zheng,Central South University 21 4Queens Problem 用 4元組 (x1， ? ， x4)， i=1,2,3,4，表示問題的解，其中 xi表示把第 i個皇后放在第 i行的第 xi列。所以 xi ? Si ={1,2,3,4}， i=1,2,3,4。 (顯約束 ) 4皇后問題的狀態(tài)空間 E可以表示為 高度為４的完全４叉樹（狀態(tài)空間樹），在狀態(tài)空間樹上搜索的約束為： xi?xj ， i ? j (即不在同一列 ) 且｜ j－ 1 | ? | i－ k | ： (不在同斜角線上 ) (在同一對角線上 ,則兩個元素有相同的“行 +列”值 ,即如果一個在 (i,k)位置 ,另一個在 (k,l)位置 ,則當(dāng)且僅當(dāng) i+j=k+l, 即｜ j－ 1 | = | i－ k |,才在同一斜角線上 ) Jin Zheng,Central South University 22 State space tree of 4Queens Problem 考察 4后問題的狀態(tài)空間樹可以發(fā)現(xiàn)有許多節(jié)點時可以不要搜索的，例如 x1=1,x2=1的子樹。因此，對于每個節(jié)點需要用判定函數(shù)進行考察，不能使判定函數(shù)為真的節(jié)點就處死 (使其變?yōu)樗拦?jié)點 )。 Jin Zheng,Central South University 23 4Queens Problem’s statespace by backtracking X1=1 X1=2 X1=3 X1=4 X2=3 X2=4 X2=4 X2=1 X2=1 X2=3 X3=2 X3=1 X3=4 X3=3 X4=3 X4=2 用過程 PLACE(k) 測試待確定的第 k皇后是否和前面已確定的 k 1個皇后是否在同一條斜角線，第 k個皇后只要與任一皇后在同一條斜角線，就返回 false，當(dāng)?shù)趉個皇后能放置于 X(k)的當(dāng)前值處時，這個返回值為真。 Jin Zheng,Central South University 24 測試 X(K)是否合理 procedure PLACE(k) //如果一個皇后能放在第 k行的 X(k)列，則返 回 true；否則返回 false。 X是一個全程數(shù) 組，進入此過程時已置了 k個值。 // global X(1： k)； integer i，