算法設(shè)計(jì)與分析6回溯法.ppt

《算法設(shè)計(jì)與分析6回溯法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第6章回溯法回溯法的基本思想回溯法是一種通用性解法，可以將回溯法看作是帶優(yōu)化的窮舉法?；厮莘ǖ幕舅枷胧窃谝豢煤袉栴}全部可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點(diǎn)。搜索過程中，每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，則判斷該結(jié)點(diǎn)為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對(duì)該子樹的搜索，退回到上層父結(jié)點(diǎn)，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造?；厮莘ǖ幕静襟E1、針對(duì)所給問題，定義問題的解空間；2、確定易于搜索的解空間結(jié)構(gòu)

2、（樹）；3、以深度優(yōu)先方式搜索解空間，盡量避免無效搜索；0-1背包問題問題描述：3個(gè)物W=[16,15,15],S=[45,25,25],C=301.定義解空間：(0,0,0),(0,0,1)…(1,1,1)，含有個(gè)解。2.確定解空間的結(jié)構(gòu)(二叉樹)如圖3.進(jìn)行深度優(yōu)先搜索n=3時(shí)的0-1背包問題用完全二叉樹表示的解空間旅行商(TSP)問題問題描述：某售貨員要到若干城市去推銷商品，給出各城市之間的路程，他要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一遍，最后回到住地的路線，使總的路程最短。該問題是一個(gè)NP完全問題，有(n-1)!條可選路線最優(yōu)

3、解(1,3,2,4,1)，最優(yōu)值251234206305410ABCDEFGHIJKLMNOPQ1234344342322423剪枝函數(shù)回溯法：在解空間樹中按深度優(yōu)先策略從根節(jié)點(diǎn)出發(fā)搜索解空間樹剪枝函數(shù)：1.用約束函數(shù)剪去不滿足的子樹2.用限界函數(shù)剪去肯定得不到最優(yōu)解的子樹解空間樹的兩種常用結(jié)構(gòu)1.子集樹：當(dāng)所給問題是從n個(gè)元素的集合s中找到滿足某種性質(zhì)的子樹集時(shí)相應(yīng)的解空間樹，如0-1背包問題。2.排列樹：當(dāng)所給問題是確定n個(gè)元素是否滿足某個(gè)性質(zhì)的排列時(shí)相應(yīng)的解空間樹成為排列樹，如TSP問題。0-1背包問題的具體求解過程問題描述：

4、n個(gè)物品，第i個(gè)物品的體積為Si，價(jià)值為Wi，背包容量為C。變量Xi表示物體i放入背包的情況，0表示不放，1表示放。1.解空間，2.解空間結(jié)構(gòu)樹：高度為n+1的完全二叉樹，結(jié)點(diǎn)總數(shù)為，左孩子為1，右孩子為0.0-1背包問題的具體求解過程求解過程：1.初始化：目標(biāo)函數(shù)置為0，將物品按價(jià)值體積比的非增順序排序2.搜索：從根節(jié)點(diǎn)出發(fā)，盡量沿左孩子結(jié)點(diǎn)前進(jìn)，當(dāng)不能繼續(xù)沿左孩子前進(jìn)時(shí)，得到問題的一部分解，把搜索轉(zhuǎn)到右子樹。3.估計(jì)由部分解所能得到的最大價(jià)值：如果估計(jì)價(jià)值高于上界，繼續(xù)向下搜索，直到找到可行解保存可行解，并用可行解得到的目標(biāo)函數(shù)

5、的值更新目標(biāo)函數(shù)的上界，向上回溯，尋找其他可行解。若估計(jì)值小于目標(biāo)函數(shù)的上界，則丟棄當(dāng)前的部分解，向上回溯。由部分解估計(jì)目標(biāo)函數(shù)值最大值的方法1.假定當(dāng)前部分解為，并且滿足2.將得到新的部分解，由這個(gè)部分解繼續(xù)向下搜索直到滿足3.能夠找到得最大價(jià)值不會(huì)超過由部分解估計(jì)目標(biāo)函數(shù)值最大值的方法4.回溯：當(dāng)前估計(jì)值小于上界時(shí)向上回溯，若當(dāng)前結(jié)點(diǎn)是左孩子，則轉(zhuǎn)向搜索右孩子；若當(dāng)前結(jié)點(diǎn)是右孩子，則繼續(xù)向上回溯，直到左孩子為止。然后轉(zhuǎn)到相應(yīng)的左孩子結(jié)點(diǎn)，重復(fù)（2），（3）實(shí)例1：0-1背包問題問題描述：C=50，S=(15,5,25,27,30

6、)W=(30,12,44,46,50)1.令Wup=0,將物體的序號(hào)按價(jià)值體積比排序結(jié)果是（2，1，3，4，5）2.生成部分解(1,1,1,0)，估計(jì)當(dāng)前部分解的價(jià)值為Weva=94.3，Weva>Wup3.繼續(xù)向下搜索生成結(jié)點(diǎn)6，得到可行解(1,1,1,0,0),得到價(jià)值為86，更新Wup=86實(shí)例1：0-1背包問題4.回溯：沿右孩子回溯到左孩子4，生成相應(yīng)右孩子7，得到部分解(1,1,0,1)，此時(shí)Weva=935.因?yàn)閃eva>Wup，繼續(xù)生成結(jié)點(diǎn)8，9，得到可行解(1,1,0,1,0),價(jià)值為88，更新Wup=88實(shí)例1：0

7、-1背包問題6.回溯到8生成10，得到部分解(1,1,0,0),估計(jì)部分解Weva=92>887.繼續(xù)生成結(jié)點(diǎn)11，得到可行解(1,1,0,0,1),更新Wup=928.因?yàn)?1是左孩子，生成其對(duì)應(yīng)的右孩子結(jié)點(diǎn)12，得到另一個(gè)可行解(1,1,0,0,0)實(shí)例1：0-1背包問題6.回溯，沿結(jié)點(diǎn)12向上回溯到結(jié)點(diǎn)3生成結(jié)點(diǎn)13，得到部分解(1,0),此時(shí)Weva=90<92,7.向上繼續(xù)回溯生成結(jié)點(diǎn)14，得到部分解(0),此時(shí)得到的Weva=91<92實(shí)例2：n皇后問題問題描述：在一個(gè)nn的棋盤上，布置n個(gè)皇后，使任意皇后之間不能相互攻

8、擊（不能同時(shí)在同一行，同一列，同一正反對(duì)角線上）1.解空間2.樹回溯法的效率分析產(chǎn)生一個(gè)結(jié)點(diǎn)的時(shí)間結(jié)點(diǎn)的個(gè)數(shù)判斷約束滿足與否的時(shí)間判斷上界滿足與否的時(shí)間回溯法的效率分析滿足約束的結(jié)點(diǎn)個(gè)數(shù)：1.剪枝函數(shù)與生成結(jié)點(diǎn)總數(shù)之間的一個(gè)折中2.生