算法設(shè)計與分析 課件 第六章 回溯法6.2.2 回溯法框架

計算機算法設(shè)計與分析第6章回溯法6.2.2回溯法框架回溯法基本步驟①定義問題的解空間：確定問題的解向量空間②確定易于搜索的解空間結(jié)構(gòu)：通常為樹或者圖形式。③確定剪枝函數(shù)：確定問題的約束條件或者進一步搜索的限界條件，即解空間中的每個解必須滿足的條件。④實現(xiàn)回溯法：根據(jù)問題的解空間、約束條件和搜索策略，以深度優(yōu)先方式搜索，實現(xiàn)回溯法。⑤處理結(jié)果：在回溯法的遞歸過程中，可以根據(jù)需要對每個解進行處理，如對解進行輸出等。6.2.2回溯法框架設(shè)問題的解是一個n維向量（x[1],x[2],...,x[n]）Constraint(i)表示當(dāng)前擴展結(jié)點處的約束函數(shù)。Bound(i)表示當(dāng)前擴展結(jié)點處的的限界函數(shù)。h[j]表示當(dāng)前擴展結(jié)點處x[i]第j個可取的值。print(x)表示輸出得到的可行解。start[i]表示在當(dāng)前擴展結(jié)點處未搜索過子樹的起始編號。end[i]表示在當(dāng)前擴展結(jié)點處未搜索過子樹的終止編號。（1）迭代回溯法Iterative_Backtrack(x):begini

1whilei>0do//還未回溯到頭ifstart[i]<end[i]then//第i層還有未搜索過的子結(jié)點 forj

start[i]toend[i]do//未搜索的結(jié)點逐個搜索 x[i]

h[j]//x[i]選擇一個取值h[j] ifConstraint(i)andBound(i)then//x[i]滿足約束條件和界限函數(shù) ifx為可行解thenprint(x)elsei

i+1endif endif endforelse//回溯，返回上一層 i

i-1endifendwhileendi表示當(dāng)前搜索層次i=0表示起始結(jié)點全部搜索完畢i層結(jié)點為死節(jié)點，則回溯（2）子集樹形式的遞歸回溯法backtrack(x,i)beginifi>nthenprint(x)elseforj

start(i)toend(i)do//枚舉i所有可能的路徑 x[i]=h[j] ifConstraint(i)andBound(i)then//滿足限界函數(shù)和約束條件 backtrack(x,i+1)endifendforendifend搜索到葉子結(jié)點，一個可行解出來對i層上每個子結(jié)點逐個搜索x[i]選擇一個可取值遞歸到下一層（3）排列樹形式的遞歸回溯法backtrack(x,i)beginifi>nthen print(x)elseforj

itondo //枚舉i所有可能的路徑

swap(x[i],x[j]) ifConstraint(i)andBound(i)then//滿足限界函數(shù)和約束條件 backtrack(x,i+1) endif

swap(x[i