算法設(shè)計與分析 課件 7.11-回溯法 - 總結(jié)

算法設(shè)計與分析回溯法總結(jié)信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版回溯法可以系統(tǒng)地搜索一個問題的所有解或任一解。搜索策略：深度優(yōu)先。搜索過程：

搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。

如果肯定不包含，則跳過以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。

否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。解題步驟（1）判斷解是否可以表示為解向量的形式（2）判斷解空間樹是子集樹還是排列樹（3）以子集樹或排列樹代碼框架為基礎(chǔ)，設(shè)計算法（4）設(shè)計剪枝函數(shù)優(yōu)化：約束函數(shù)、限界函數(shù)子集樹代碼框架voidBackTrack(intt){if(t>n)Output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(Constraint(t)&&Bound(t))BackTrack(t+1); }}排列樹代碼框架voidBackTrack(intt){if(t>n)Output(x);elsefor(inti=t;i<=n;i++){

swap(x[t],x[i]);if(Constraint(t)&&Bound(t))BackTrack(t+1);swap(x[t],x[i]); }}在調(diào)用BackTrack(1)進(jìn)行回溯搜索前，先將變量數(shù)組x初始化為排列(1,2,…,n)?；厮莘ǖ牡湫蛻?yīng)用（1）0-1背包問題（2）裝載問題（3）

旅行售貨員問題（TSP）（4）批處理作業(yè)調(diào)度問題（5）符號三角形問題（6）N皇后問題回溯算法的效率在很大程度上依賴于以下因素： (1)產(chǎn)生x[k]的時間； (2)x[k]值的個數(shù)； (3)計算約束函數(shù)constraint的時間； (4)計算限界函數(shù)bound的時間； (5)滿足約束函數(shù)和限界函數(shù)的所有x[k]的個數(shù)。好的剪枝函數(shù)能顯著地減少所生成的結(jié)點數(shù)，但這樣的剪枝函數(shù)往往計算量較大。

因此，在選擇剪枝函數(shù)時通常存在生成結(jié)點數(shù)與剪枝函數(shù)計算量之間的折衷。

在搜索試探時，選取x[i]值的順序是任意的。在其它條件相當(dāng)?shù)那疤嵯拢M可能讓可取值最少的x[i]優(yōu)先?；厮莘ㄊ腔陔[式圖的深度優(yōu)先搜索，解空間樹動態(tài)生成。

測試選擇題：下列描述正確的有（）A：回溯法的搜索策略是深度