算法分析與設(shè)計[回溯法].ppt

《算法分析與設(shè)計[回溯法].ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第六章回溯法什么是回溯法例：迷宮游戲可用回溯法求解的問題問題的解可以用一個n元組(x1,…,xn)來表示，其中的xi取自于某個有窮集Si，并且這些解必須使得某一規(guī)范函數(shù)P(x1,…,xn)（也稱限界函數(shù)）取極值或滿足該規(guī)范函數(shù)條件。例子：A(1:n)個元素的分類問題問題的解為n元組；xi取自有窮集；規(guī)范函數(shù)P：A(xi)≤A(xi+1)問題求解的方法硬性處理法列出所有候選解，逐個檢查是否為所需要的解理論上，候選解數(shù)量有限，并且通過檢查所有或部分候選解能夠得到所需解時，上述方法可行實際中則很少使用，因為候選解

2、的數(shù)量通常都非常大（比如指數(shù)級，甚至是大數(shù)階乘），即便采用最快的計算機也只能解決規(guī)模較小的問題?；厮莼蚍种ο藿绶ū苊鈱艽蟮暮蜻x解集合進行完全檢查大大減少問題的求解時間通常用來求解規(guī)模較大的問題回溯法概述回溯法可以系統(tǒng)的搜索一個問題的所有解或任一個解它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索到某一結(jié)點時，如果斷定該結(jié)點肯定不包含問題的解，則跳過以該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯這種以深度優(yōu)先方式搜索問題的解的方法稱為回溯法回溯法思想第一步：為問題定義

3、一個狀態(tài)空間(statespace)。這個空間必須至少包含問題的一個解第二步：組織狀態(tài)空間以便它能被容易地搜索。典型的組織方法是圖或樹第三步：按深度優(yōu)先的方法從開始結(jié)點進行搜索開始結(jié)點是一個活結(jié)點（也是E-結(jié)點：expansionnode）如果能從當前的E-結(jié)點移動到一個新結(jié)點，那么這個新結(jié)點將變成一個活結(jié)點和新的E-結(jié)點，舊的E-結(jié)點仍是一個活結(jié)點。如果不能移到一個新結(jié)點，當前的E-結(jié)點就“死”了（即不再是一個活結(jié)點），那么便只能返回到最近被考察的活結(jié)點（回溯），這個活結(jié)點變成了新的E-結(jié)點。當我們已經(jīng)找

4、到了答案或者回溯盡了所有的活結(jié)點時，搜索過程結(jié)束。回溯法如何提高效率？由開始結(jié)點到當前E-結(jié)點構(gòu)成解向量(x1,…,xi)；其中的xi取自于某個有窮集Si，假設(shè)集合Si的大小是mi。如果判定(x1,…,xi)不能導致最優(yōu)解，那么就將可能要測試的mi+1…mn個向量略去。因此回溯法的測試次數(shù)比硬性處理作的測試次數(shù)要少得多。如何判定(x1,…,xi)能否導致最優(yōu)解？約束條件回溯法的解需要滿足一組綜合的約束條件，通常分為：顯式約束和隱式約束顯式約束條件限定每個xi只從一個給定的集合上取值，例如：Xi≥0即si={

5、所有非負實數(shù)}xi=0或xi=1即si={0,1}l≤xi≤u即si={a:l≤a≤u}滿足顯式約束的所有元組確定一個可能的解空間隱式約束描述了xi必須彼此相關(guān)的情況，如0/1背包問題中的背包重量M回溯法求解的經(jīng)典問題（1）8-皇后問題在一個8*8棋盤上放置8個皇后，且使得每兩個之間都不能互相“攻擊”，也就是使得每兩個都不能在同一行、同一列及同一條斜角線上。8皇后問題的解可以表示為8-元組(x1,…,x8)，其中其中xi是第i行皇后所在的列號。顯式約束條件是si={1,2,3,4,5,6,7,8},1≤i≤

6、8隱式約束條件是，沒有兩個xi可以相同且沒有兩個皇后可以在同一條斜角線上。QQQQQQQQ1234567812345678由于解向量之間不能相同，所以解空間的大小由88個元組減少到8!個元組。上圖中的解表示為一個8-元組即（4，6，8，2，7，1，3，5）?；厮莘ㄇ蠼獾慕?jīng)典問題（2）子集和數(shù)問題已知(w1,w2,…,wn)和M，均為正數(shù)。要求找出wi的和數(shù)等于M的所有子集。例如：若n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31，則滿足要求的子集是(11,13,7)和(24,7).子

7、集和數(shù)問題解的一種表示方法若用Wi的下標表示解向量，這兩個解向量為(1,2,4)和(3,4)。子集和數(shù)問題的解可以表示為k-元組(x1,x2,…,xk),1≤k≤n并且不同的解可以是大小不同的元組。顯式約束條件是xi∈{j

8、j為整數(shù)且1≤j≤n}。隱式約束條件是1)沒有兩個xi是相同的;2)wxi的和為M;3)xi＜xi＋1,1≤i＜n（避免產(chǎn)生同一個子集的重復(fù)情況）子集和數(shù)問題解的另一種表達解由n-元組(x1,x2,…,xn)表示顯式約束條件xi∈{0,1}，1≤i≤n，如果沒有選擇Wi，則xi=0；如果

9、選擇了Wi，則xi=1。于是上面的解可以表示為(1，1，0，1)和(0，0，1，1)隱式約束條件(xi×wi)的和數(shù)為M解空間的大小為2n個元組解空間的樹結(jié)構(gòu)回溯算法通過系統(tǒng)地檢索給定問題的解空間來確定問題的解。這檢索可以用這個解空間的樹結(jié)構(gòu)來簡化。為了便于討論，引進一些關(guān)于解空間樹結(jié)構(gòu)的術(shù)語。問題狀態(tài)(problemstate)：樹中的每一個結(jié)點確定所求解問題的一個問題狀態(tài)。狀態(tài)空間(statespace)：由