第六章回溯法1/11/2023學習要點理解回溯法的概念。著重討論可以用回溯法求解的問題的一般特征。掌握回溯算法的基本要素理解回溯算法的一般理論通過應用范例學習。（1）一般方法；（2）8皇后問題；（3）子集和數(shù)的問題；（4）圖的著色問題1/11/2023有許多問題，找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。回溯法有“通用的解題法”之稱。6.1回溯法的一般方法解決一個問題的所有可能的決策序列構成該問題的解空間。解空間中滿足約束條件的決策序列稱為可行解。一般說來，解任何問題都有一個目標，在約束條件下使目標達到最優(yōu)的可行解稱為該問題的最優(yōu)解。1/11/2023回溯法的基本思想是在一棵含有問題全部可行解的狀態(tài)空間樹上，從根結點出發(fā)進行深度優(yōu)先搜索，解在葉子結點上。搜索過程中，每到達一個結點時，則判斷該結點為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回到上層父結點，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構造出整棵狀態(tài)空間樹，再進行搜索，而是在搜索過程，逐步構造出狀態(tài)空間樹，即邊搜索，邊構造。1/11/2023例：迷宮游戲1/11/2023有關問題狀態(tài)的幾個術語問題狀態(tài)：樹中的每一個結點確定所求解問題的一個問題狀態(tài)。代表問題狀態(tài)的結點稱為問題結點狀態(tài)空間：由根結點到其它結點的所有路徑確定了這個問題的狀態(tài)空間。解狀態(tài)：是這樣的一些問題狀態(tài)S，對于這些問題狀態(tài)，由根到S的那條路徑確定了解空間的一個元組。其對應的結點稱為解結點。答案狀態(tài)：是這樣的一些問題狀態(tài)S，對于這些問題狀態(tài)，由根到S的那條路徑確定了這問題的一個解（即它滿足隱式約束條件）。擴展結點:一個正在產(chǎn)生兒子的結點稱為擴展結點(E)活結點:一個自身已生成但其兒子還沒有全部生成的結點稱做活結點死結點:一個所有兒子已經(jīng)產(chǎn)生的結點稱做死結點狀態(tài)空間樹的每個問題結點對應一個子解空間，同時也代表已經(jīng)作出的一些選擇。狀態(tài)空間樹是在算法執(zhí)行中產(chǎn)生的。為此還有以下術語：1/11/2023深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結點，繼續(xù)生成R的下一個兒子（如果存在）回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。狀態(tài)空間樹的產(chǎn)生方法定義了問題的解空間后，還應將解空間很好的組織起來，使得用回溯法能方便地搜索整個解空間。一般組織成樹或圖的形式。RC1/11/2023(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結構；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用限界函數(shù)避免無效搜索。用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間?；厮莘ǖ幕静襟E1/11/2023回溯法的基本思路：

問題的解可以用一個n元組(x1,…,xn)來表示，其中的xi取自于某個有窮集Si，并且這些解必須使得某一限界函數(shù)B(x1,…,xn)取極值。假設集合Si的大小是mi，于是就有m=m1m2…

mn個n-元組可能滿足函數(shù)B。構造出這m個n-元組并逐一測試它們是否滿足函數(shù)B，從而找出該問題的所有最優(yōu)解。所以不斷地用修改過的限界函數(shù)B(x1,…,xi)去測試正在構造的n元組的部分向量(x1,…,xi)，看是否可能導致最優(yōu)解。如果判定(x1,…,xi)不能導致最優(yōu)解，那么就將可能要測試的mi+1…mn個向量略去。因此回溯法的基本做法是搜索。或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索算法。x1x2xmi1/11/2023顯約束：對分量xi的取值限定。(顯式約束條件限定每個x只從一個給定的集合上取值)隱約束：為滿足問題的解而對不同分量之間施加的約束。問題的解空間和約束條件問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。而求得的解要滿足約束條件。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。例如，將A(1:n)中的整數(shù)或?qū)崝?shù)排序就是可用一個n元組表示其解的問題，其中xi是A中第i小元素的下標。判定函數(shù)是不等式A(xi)≤A(xi+1)，其中，1≤i＜n。這里，Si是一個包含整數(shù)1到n的有窮集合。1/11/2023x1x2xmi約束條件：用回溯法求解的許多問題都要求所有的解滿足一組綜合的約束條件。對n元組(x1,x2,…,xn)中的分量的約束，可分為兩類：一類是顯約束，一類是隱約束，顯約束是限定每個x只從一個給定的有限集合上取值。例如xi≥0Si={所有非負實數(shù)}xi=0或xi=1Si={0,1}bi≤xi≤ui

Si={a:bi≤a≤ui}隱約束條件則規(guī)定解空間中那些實際上滿足規(guī)范函數(shù)Bi(x1,x2,…,xi)的元組。因此，隱約束描述了xi必須彼此相關的情況。不過，顯約束和隱約束不是絕對的。有時顯約束可以表示成隱約束，隱約束也可以表示成顯約束。問題的解空間和約束條件解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。1/11/2023例：對于有n種可選擇物品的0/1背包問題，其解空間由長度為n的0-1向量組成。該解空間包含了對變量的所有可能的0-1賦值。當n=3時，其解空間是{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}1/11/2023如果n=3,M=30,w=(16,15,15),v=(45,25,25)，對0/1背包問題的求解，我們要從下圖的根結點開始搜索其解空間。

45r=M-w1=30-16=14Q=45r=r-w2=14-0=14Q=45(保留)50252501/11/2023對于許多問題，所給定的約束集D具有完備性，即i元組(x1,x2,…,xi)滿足D中僅涉及到x1,x2,…,xi的所有約束，這意味著，j(j<i)元組(x1,x2,…,xj)也一定滿足D。換句話說，只要存在1≤j≤n-1,使得(x1,…,xj)違反了D,則以(x1,…,xj)為前綴的任何n元組(x1,…,xj,…,xn)也一定違反D?；厮莘ɡ眠@種完備性，所以回溯法是一個即帶有系統(tǒng)性，又帶有跳躍性的搜索方法。x1x2x11/11/2023深度優(yōu)先搜索策略回溯法將n元組(x1,x2,…,xn)的狀態(tài)空間E表示成一棵高度為n的帶權有權樹T,把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索。下圖所示的是一棵高度為n=3、每層結點數(shù)都為3的狀態(tài)空間樹。從根出發(fā)進行搜索，搜索到每個結點，先判斷以該結點為根的子樹是否肯定不包含問題的解，如果不包含，則跳過對該子樹的搜索，一層一層向祖先結點回溯，直到遇上還未搜索過的子樹，才搜索這棵子樹?；厮莸礁Y點時，則找出了問題的所有解。1/11/2023

6.1.2回溯算法的形式描述：假設回溯法要找出所有的答案結點。設(x1,x2,…,xi-1)是狀態(tài)空間樹中由根到一個結點的路徑，而T(x1,…xi-1)是下述所有結點xi的集合，它使得對于每一個xi，(x1,x2,…,xi)是由根到一個結點xi的路徑；假定還存在著一些限界函數(shù)Bi，如果路徑(x1,x2,…,xi)不可能延伸到一個答案結點，則Bi(x1,x2,…,xi)取假值，否則取真值。于是解向量X(1:n)中的第i個分量，就是那些選自集合T(x1,x2,…,xi-1)且使Bi為真的xixixi+1BiProceduresearch(當前狀態(tài))if當前狀態(tài)是目標狀態(tài)

thenexit;for對所有可能的狀態(tài)dosearch(新狀態(tài))repeatEnd1/11/2023算法6.1回溯法的一般方法ProcedureBACKTRACK(n)k=1;//考察第1層while(k>0)do//k=0時，結點被搜索完

if

還剩有沒檢驗的xk使得//每個xk是1棵子樹

xkTk(x1,…,xk-1)andBk(x1,x2,…,xk)

//Xk=Tk(X1,…,Xk-1)中未取過的值；

xk的取值與前k-1個有關

then

if(X1,…,Xk)是一答案路徑；//可能成為解，或需深度搜索

then輸出

(X1,…,Xk)；endif//是一條已抵達一答案結點的路徑

k=k+1;

//深度擴展搜索，向下一層

elsek=k-1//試探完了所有的xk,回溯到上一層

endifrepeatEndBACKTRACKxkxk+1對控制流程的抽象描述，每個解在x(1:n)中生成,求出解后輸出,用Bk函數(shù)作約束。1/11/2023算法6.2遞歸回溯算法設對于任意的1≤k≤n，狀態(tài)結點(x1,x2,…,xk-1)被激活以后，滿足顯約束的xk的全體解集Tk(x1,x2,…,xk-1)，而滿足隱約束的xk當且僅當邏輯表達式Bk(x1,x2,…,xk)為真。ProcedureRBACKTRACK(k)globaln,X(1:n)//n控制深度

ifk>nthenreturn;/表示搜索完，達到空間樹的深度，結束

elseforxkTk(x1,…,xk-1)andBk(x1,x2,…,xk)do

ifk==nthen輸出(X1,…,Xn)endifcallRBACKTRACE(k+1);//深度擴展搜索

repeat

endifEndRBACKTRACK

對于所有可以由根結點到達，并可能使界限函數(shù)B為真的結點X(k)

，判斷X(1),…,X(k)是否是一條已抵達一答案結點的路徑Proceduresearch(當前狀態(tài))if當前狀態(tài)是目標狀態(tài)

thenexit;for對所有可能的狀態(tài)dosearch(新狀態(tài))repeatEnd產(chǎn)生所有解，只需要一個解時，要改造。Proceduresearch(當前狀態(tài))if當前狀態(tài)超出目標狀態(tài)

thenexit;for對所有可能的狀態(tài)dosearch(新狀態(tài))repeatEnd圖x1k=1x2k=2

x3k=3k==n:表明(x1,x2,…,xn)是一條已抵達答案結點的路徑1/11/2023通過前面具體實例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素：(1)產(chǎn)生下一個x[k]的時間；(2)滿足顯約束條件的x[k]值的個數(shù)；(3)計算約束函數(shù)Bi的時間；(4)滿足約束函數(shù)Bi的所有x[k]的個數(shù)。好的約束函數(shù)能顯著地減少所生成的結點數(shù)。但這樣的約束函數(shù)往往計算量較大。因此，在選擇約束函數(shù)時通常存在生成結點數(shù)與約束函數(shù)計算量之間的折衷?；厮莘ㄐ史治鰔1k=1x2k=2

x3k=31/11/20236.2n皇后問題問題描述：找出在一個n*n棋盤上放置n個皇后，且使得每兩個之間都不能互相“攻擊”，也就是使得每兩個都不能在同一行、同一列及同一條斜角線上的所有方案。問題的狀態(tài)：即棋盤的布局狀態(tài)，狀態(tài)空間樹的根為空棋盤，每個布局的下一步可能布局為該布局結點的子結點；n皇后問題可以表示為n-元組(x1,…,xn)，其中xi是放置皇后i所在的列號。例：n=4，即4皇后問題。用4元組(x1,..x4),i=1,2,3,4,表示問題的解，其中xi表示把第i個皇后放在第i行的第xi列。所以

(1)顯式約束條件：xisi={1,2,3,4},1≤i≤4(2)隱式約束條件:沒有兩個xi可以相同且沒有兩個皇后可以在同一條斜角線上。1/11/2023考察發(fā)現(xiàn)有許多結點是可以不要搜索的，例如x1=1,x2=1的子樹。因此，對于每個結點需要用判定函數(shù)進行考察，不能使判定函數(shù)為真的結點就處死。4-皇后問題的狀態(tài)空間樹在狀態(tài)空間樹上搜索的約束(隱約束)為：

xixj

ij，且|j-i||xj-xi|這是皇后不同列且不在一條斜角線的約束。1/11/20234-皇后問題部分狀態(tài)空間樹用過程PLACE(k)測試待確定的第k皇后是否和前面已確定的k-1個皇后是否在同一列、同一條斜角線，第k個皇后只要與任一皇后在同一列、同一條斜角線，就返回false,當?shù)趉個皇后能放置于x(k)的當前位置時，這個返回值為真。1/11/2023QQ.QQ..QQ..QQQQ...Q

QQQ..QQ

Q..Q

QQQ

Q(1)(1,2)(1,3)(1,3,2)(1,3,4)(1,4)(1,4,2,3)(1,4,3)QQQ(2)用Q表示棋子，用?表示曾試圖放置棋子但由于不滿足條件要求而放棄了的格子。采用搜索的辦法，一旦發(fā)現(xiàn)“此路不通”就改變路徑（即回溯），則搜索過程可以用圖表達出來。解為(2,4,1,3)1/11/2023回溯過程分析1、從空棋盤起，逐行放置棋子。2、在一個布局中放下一個棋子，即推進到另一個布局。3、如果某一行中沒有可合法放置棋子的位置，則回溯到上一行，重新布放上一行的棋子。x1=1x1=2x1=3x1=41/11/20238-皇后問題實際上很容易一般化為n-皇后問題，即要求找出一個n*n棋盤上放置n個皇后并使其不能互相攻擊的所有方案。令(x1,…,xn)表示一個解，由于沒有兩個皇后可以放入同一列，因此所有的xi將是互不相同的，一行只能一個皇后。

不同列、不同行的表示：xixj，ij那么關鍵是應如何去測試兩個皇后是否在同一條斜角線上呢？例：8-皇后問題約束條件：xixj

ij，且|j-i||xj-xi|

不在斜角線上：|j-i||xj-xi|下一后1/11/2023QQQQQQQQ

1234567812345678由于解向量之間不能相同，所以解空間的大小由88個元組減少到8!個元組。圖中的解表示為一個8-元組即（4，6，8，2，7，1，3，5）。如果用二維數(shù)組A(1:n,1:n)的下標來標記每個皇后的位置，那么可以看到，對于在同一條斜角線上的由左上方到右下方的每一個元素有相同的“行-列”值，同樣，在同一條斜角線上的由右上方到左下方的每一個元素則有相同的“行+列”值。a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a32a33a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a88后退1/11/2023假設有兩個皇后被放置在(i，xi)和(j，xj)位置上，那么根據(jù)以上所述，僅當

i–xi=j-xj

或

i+xi=j+xj

時，它們才在同一條斜角線上。將這兩個等式分別變換成

xi-xj=i-j或

xj-xi=i-j

因此，當且僅當|xi-xj|=|i-j|

時（即兩個皇后所在位置的行差距等于列差距時），兩個皇后在同一條斜角線上。該過程的計算時間是O(k-1)

不在斜角線上：|i-j||xi-xj|約束條件：xixj

ij，且|j-i||xj-xi|1/11/2023算法描述初始化空棋盤（起始狀態(tài)）；從第一行開始，直至第一行出現(xiàn)回溯在當前行r中查找下一個可以放置王后的位置

如果找到了可以擺放的位置放下一個子

如果已經(jīng)是最后一行得到一個解撤掉該子，繼續(xù)尋找下一個解否則（未到最后一行）準備處理下一行

否則（沒有找到可以擺放的位置）回溯到上一行，并撤掉該行的棋子1/11/2023算法6.4：可以放置一個新皇后嗎？(測試x(k)是否合理)ProcedurePLACE(k)//相當于Bk,考察在放置了前k-1個后xk的合理性。

//如果一個皇后能放在第k行和X(k)列，則返回true，否則返回false。X是一個全程數(shù)組，進入此過程時已置入了k個值。ABS(r)過程返回r的絕對值// globalX(1:k);integeri,k; i1 whilei<kdo//i=k時結束，前i-1個不與第k個位置沖突

ifX(i)=X(k)orABS(X(i)-X(k))=ABS(i-k)