算法分析與設(shè)計(jì)(第2版)回溯算法ppt課件.ppt

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

1、第5章回溯法有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。本章主要知識點(diǎn)：5.1回朔法的算法框架5.2裝載問題5.3批處理作業(yè)調(diào)度5.4符號三角形問題5.5

2、n后問題5.60-1背包問題5.7最大團(tuán)問題5.8圖的m著色問題5.9旅行售貨員問題5.10圓排列問題5.11電路板排列問題5.12連續(xù)郵資問題5.13回朔法效率分析5.1回朔法的算法框架5.1.1問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。

3、對于n=3的0-1背包問題，其解空間是一個深度為4的滿二叉數(shù)。當(dāng)w={16，15，15}，p={45，25，25}，c=30時(shí)，0-1背包問題的解向量是：（0，1，1）5.1.2回朔法的基本思想擴(kuò)展結(jié)點(diǎn):一個正在產(chǎn)生兒子的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn):一個自身已生成但其兒子還沒有全部生成的節(jié)點(diǎn)稱做活結(jié)點(diǎn)。死結(jié)點(diǎn):一個所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱做死結(jié)點(diǎn)。深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個兒子（如果存在）。寬度優(yōu)先的問題狀態(tài)

4、生成法：在一個擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)?；厮莘ǎ簽榱吮苊馍赡切┎豢赡墚a(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻

5、，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。例如:對于n=3的0-1背包問題，當(dāng)w={16，15，15}，p={45，25，25}，c=30時(shí)，該0-1背包問題的最優(yōu)解向量是x=（0，1，1）。其解空間是一個深度為4的滿二叉數(shù)。各葉子所代表的解向量是結(jié)點(diǎn)H：x=（1，1，1）結(jié)點(diǎn)I：x=（1，1，0）結(jié)點(diǎn)J：x=（1，0，1）結(jié)點(diǎn)K：x=（1，0，0）結(jié)點(diǎn)L：x=（0，1，1）結(jié)點(diǎn)M：x=（0，

6、1，0）結(jié)點(diǎn)N：x=（0，0，1）結(jié)點(diǎn)O：x=（0，0，0）當(dāng)擴(kuò)展結(jié)點(diǎn)是E時(shí)，活結(jié)點(diǎn)有A,B,E;死結(jié)點(diǎn)有D,H,I。當(dāng)擴(kuò)展結(jié)點(diǎn)是F時(shí)，活結(jié)點(diǎn)有A,C,F;死結(jié)點(diǎn)有B,D,H,I,E,J,K。例如:對于帶權(quán)圖G，在圖G中求費(fèi)用最小的周游路線，其解空間是如右圖所示的樹。它的每個葉子代表了一個解向量。含有n個頂點(diǎn)的無向完全圖有n(n-1)/2條邊。由于是完全圖，所以從指定的頂點(diǎn)出發(fā)的不同周游路線有(n-1)!條?；厮莘ň褪窃诮饪臻g數(shù)上一個一個地搜索出每一個解向量，并在一定的意義下，從這些解向量中通過計(jì)算，求出最優(yōu)解向量。對于特定的問題，其解空間樹往往特別大，包含的葉子

7、非常多，因此，剪枝函數(shù)對回溯算法的優(yōu)化非常重要。5.1.3遞歸回朔回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(xiàn)回溯法。voidbacktrack(intt)//對于第t層的一個擴(kuò)展結(jié)點(diǎn){if(t>n)output(x);//到達(dá)一個葉子，輸出該葉子所表示的解向量else//沒有到達(dá)一個葉子for(inti=f(n,t);i<=g(n,t);i++){//對于當(dāng)前擴(kuò)展結(jié)點(diǎn)的第i個孩子x[t]=h(i);//求該孩子所表示的部分解向量if(constraint(t)&&bound(t))//如果該孩子滿足剪枝函數(shù)backtrack(t+1);//生成

8、該孩子，并