算法設(shè)計(jì)與分析 課件 7.3-回溯法-基本思想-解題步驟

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

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

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

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

A：廣度優(yōu)先B：活結(jié)點(diǎn)優(yōu)先C：隨機(jī)D：深度優(yōu)先在回溯法的搜索過程中，問題的解空間是（）A：搜索前靜態(tài)生成的B：搜索中動(dòng)態(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代表遞歸的深度//