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

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

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

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

否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。解題步驟（1）判斷解是否可以表示為解向量的形式（2）判斷解空間樹(shù)是子集樹(shù)還是排列樹(shù)（3）以子集樹(shù)或排列樹(shù)代碼框架為基礎(chǔ)，設(shè)計(jì)算法（4）設(shè)計(jì)剪枝函數(shù)優(yōu)化：約束函數(shù)、限界函數(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); }}排列樹(shù)代碼框架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背包問(wèn)題（2）裝載問(wèn)題（3）

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

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

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

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