算法設計與分析 課件 7.3-回溯法-基本思想-解題步驟

算法設計與分析回溯法-基本思想信息工程大學國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版基本思想解題步驟一二

回溯法也稱為通用解題法，是一種對問題解空間進行搜索的窮舉算法，在搜索過程中給出搜索回溯的條件，即剪枝函數(shù)。在確定解空間的組織結(jié)構(gòu)基礎上，從根結(jié)點出發(fā)，以深度優(yōu)先方式搜索解空間；設定開始結(jié)點為活結(jié)點，同時成為當前擴展結(jié)點，在當前擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點，若從當前擴展結(jié)點處不能向縱深方向移動，則成為死結(jié)點，并向回移動（回溯）至最近的活結(jié)點，使之成為當前擴展結(jié)點；以上述方式遞歸地在解空間中搜索，直到找到解或者解空間中沒有活結(jié)點為止?；厮莘ㄟm用于求解涉及一組解的問題或求滿足某些約束條件的最優(yōu)解問題，且適用于求解組合數(shù)較大的問題。回溯法的特征：回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。

在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))?；靖拍睿簡栴}的解向量：問題的解以n元向量的形式表示。如0-1背包問題，解可定義為(x1,x2,…,xn)，xi取值1或0。顯式約束：對解向量中每個分量取值的限定。如0-1背包問題，解分量只能取0或1。隱式約束：解向量整體應滿足的條件，也是在解分量之間施加的約束。如0-1背包問題，裝入背包的物品總重量不能超過背包載荷。問題的解空間：所有滿足顯式約束的解向量的集合。如有3種可選擇物品的0-1背包問題的解空間可定義為長度為3的0-1向量的集合，包括(0,0,0)，(0,0,1)，(0,1,0)，…，(1,1,1)共八種。問題的解空間樹：用樹結(jié)構(gòu)表示的解空間。樹中的活結(jié)點：以它為根的子樹未搜索結(jié)束。樹中的擴展結(jié)點：當前正在生成其兒子結(jié)點的活結(jié)點。樹中的死結(jié)點：不再進一步擴展或者以它為根的子樹搜索已經(jīng)結(jié)束。問題狀態(tài)：樹中每一個結(jié)點確定所求解問題的一個問題狀態(tài)。解狀態(tài)（解向量）：由根到葉子結(jié)點的路徑對應該解空間中的一個可能解。

沿著一條路徑，不斷深入，碰壁后回撤并換路，繼續(xù)不斷深入。有目標有策略有決策回溯法仰望星空腳踏實地運用回溯法解題通常包含以下三個步驟：針對所給問題，定義問題的解空間確定易于搜索的解空間結(jié)構(gòu)以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索測試選擇題：回溯法在問題的解空間樹中按（）策略從根結(jié)點出發(fā)搜索解空間樹。

A：廣度優(yōu)先B：活結(jié)點優(yōu)先C：隨機D：深度優(yōu)先在回溯法的搜索過程中，問題的解空間是（）A：搜索前靜態(tài)生成的B：搜索中動態(tài)生成的遞歸回溯BackTrack(1)voidBackTrack(intt){if(t>n)Output(x);else

for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i); if(Constraint(t)&&Bound(t)) BackTrack(t+1);}}//t代表遞歸的深度//