《算法設計與分析》第08章.ppt
《《算法設計與分析》第08章.ppt》由會員分享，可在線閱讀，更多相關《《算法設計與分析》第08章.ppt（66頁珍藏版）》請在裝配圖網(wǎng)上搜索。
,算法設計與分析,DeSignandAnalysisofAlgorithmsInC++,,,“十一五”國家級規(guī)劃教材,陳慧南編著,電子工業(yè)出版社,,第2部分算法設計策略,,,第8章回溯法,,,8.1一般方法8.2n-皇后8.3子集和數(shù)8.4圖的著色8.5哈密頓環(huán)8.60/1背包8.7批處理作業(yè)調(diào)度,,最優(yōu)化問題：滿足一定的約束條件解稱為可行解。使目標函數(shù)最優(yōu)的（最大或最?。┛尚薪夥Q為最優(yōu)解。問題的解向量：表示成一個n元式(x0,x1,…,xn-1)的形式貪心算法：最優(yōu)子結構特性和最優(yōu)量度標準動態(tài)規(guī)劃法：最優(yōu)子結構特性和重疊子問題,8.1一般方法,,回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。,回溯法的基本思想,一般的搜索算法（暴力算法），對所有可能的解逐一的試驗，看是否是問題的解。任何問題都可以用暴力搜索算法解決，因為它遍歷了全部可能解，但是顯然會很慢。,,搜索過程，要保證每個可能情況都要試到，不漏不重，所以就有了各種各樣的搜索算法，比如深度優(yōu)先搜索，廣度優(yōu)先搜索。他們的區(qū)別只在于構造可能解的方式不同，本質(zhì)是一樣的，都是試解，回溯算法是一種采用深度優(yōu)先方式來構造可能解的搜索算法。,n=3時的0-1背包問題用完全二叉樹表示的解空間,M=30（w0,w1,w2）=(18,15,10)，（p0,p1,p2）=(25,24,15)。,,搜索算法如果不做任何優(yōu)化那么執(zhí)行效率是一樣的。因為一定要搜索全部可能解。但是如果我們在搜索過程（可能解的構造）中已經(jīng)和問題不符合，我們就沒必要繼續(xù)構造下去，這就是所謂搜索算法里面的剪枝，不同的搜索算法就是為了盡可能地舍棄那些不可能的解，來達到提高搜索算法效率的目的。,n=3時的0-1背包問題用完全二叉樹表示的解空間,M=30（w0,w1,w2）=(18,15,10)，（p0,p1,p2）=(25,24,15)。,,回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。,n=3時的0-1背包問題用完全二叉樹表示的解空間,,8.1.1基本概念,問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x0,x1,…,xn-1)的形式。規(guī)定每個xi取值的約束條件稱為顯式約束。對給定的一個問題實例，顯式約束規(guī)定了所有可能的元組，它們組成問題的候選解集，被稱為該問題實例的解空間。隱式約束給出了判定一個候選解是否為可行解的條件。目標函數(shù)也稱代價函數(shù)，用來衡量每個可行解的優(yōu)劣。使目標函數(shù)取最大（或最?。┲档目尚薪鉃閱栴}的最優(yōu)解。,,狀態(tài)空間樹（statespace）是描述問題解空間的樹形結構。樹中每個結點稱為一個問題狀態(tài)（problemstate）。如果從根到樹中某個狀態(tài)的路徑代表一個作為候選解的元組，則稱該狀態(tài)為解狀態(tài)（solutionstate）。如果從根到某個解狀態(tài)的路徑代表一個作為可行解的元組，則稱該解狀態(tài)為答案狀態(tài)(answerstate)。,M=30（w0,w1,w2）=(18,15,10)，（p0,p1,p2）=(25,24,15)。,,8.1.2剪枝函數(shù)和回溯法,為了提高搜索效率，在搜索過程中使用約束函數(shù)（constraintfunction），可以避免無謂地搜索那些已知不含答案狀態(tài)的子樹。如果是最優(yōu)化問題，還可使用限界函數(shù)（boundfunction）剪去那些不可能包含最優(yōu)答案結點的子樹。約束函數(shù)和限界函數(shù)的目的是相同的，都為了剪去不必要搜索的子樹，減少問題求解所需實際生成的狀態(tài)結點數(shù)，它們統(tǒng)稱為剪枝函數(shù)（pruningfunction）。,,,,使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結點的求解方法稱為回溯法（backtracking）；廣度優(yōu)先生成結點，并使用剪枝函數(shù)的方法稱為分枝限界法（branch-and-bound）。,剪枝函數(shù)：約束函數(shù)在擴展結點處剪去不滿足約束的子樹；限界函數(shù)剪去得不到最優(yōu)解的子樹。,,對n個元素（a0,a1,…,an-1)排序，本質(zhì)是求元素下標（0，1,…,n-1)的一種排列X(x0,x1,…,xn-1)，使得axi≤axi+1例如：n=3,（a0,a1,a2)=(13,24,9),,設(x0,x1,…,xk-1)是從根到某個問題狀態(tài)Y的一條路徑，令T(x0,x1,…,xk-1)是xk可取值的集合，對于xk的每個取值(x0,x1,…,xk-1，xk)，是一條從根到Y再到Y的某個孩子Z的路徑。如果約束函數(shù)Bk(x0,x1,…,xk)為真，則繼續(xù)檢測以Z為根的子樹，否則將不再考慮以Z為根的子樹。如果(x0,x1,…,xk-1)到達葉子結點，T(x0,x1,…,xk-1)應為空集。,,【程序8－1】遞歸回溯法VoidRBacktrack(intk){//應以RBacktrack(0)調(diào)用本函數(shù)for(每個x[k],使得x[k]?T(x[0],?,x[k-1])//深度優(yōu)先進入下一層}}},n=3,（a0,a1,a2)=(13,24,9),,【程序8-2】迭代回溯法VoidIBacktrack(intn){intk=0;while(k>=0){if(還剩下尚未檢測的x[k]，使得x[k]?T(x[0],?,x[k-1])//回溯到上一層}},,8.1.3回溯法的效率分析,回溯算法的最壞情況時間復雜度可達O(p(n)n!)（或O(p(n)2n)或O(p(n)nn)），這里p(n)是n的多項式，是生成一個結點所需的時間。,,,,蒙特卡羅方法（MonteCarlo）。這種估計方法的基本思想是在狀態(tài)空間樹中隨機選擇一條路徑(x0,x1,…,xn?1)。設X是這條隨機路徑上，代表部分向量(x0,x1,…,xk?1)的結點，如果在X處不受限制的孩子數(shù)目是mk，則認為與X同層的其他結點不受限制的孩子數(shù)目也都是mk。整個狀態(tài)空間樹上將實際生成的結點數(shù)估計為m=1+m0+m0m1+m0m1m2+?,,【程序8-3】蒙特卡羅算法intEstimate(SType*x){intk=0,m=1,r=1;do{SetTypeS={x[k]|x[k]?T(x[1],?,x[k?1])},,8.2n-皇后,,,,,8.2.1問題描述,n-皇后問題要求在一個n?n的棋盤上放置n個皇后，使得它們彼此不受“攻擊”。n-皇后問題要求尋找在棋盤上放置這n個皇后的方案，使得它們中任何兩個都不在同一行、同一列或同一斜線上。,,,,,,8.2.2回溯法求解,皇后問題可用n-元組（x0,x1,…,xn?1）表示n-皇后問題的解，其中xi表示第i行的皇后所處的列號(0≤xi＜n)。顯式約束的一種觀點是：xi?{0,1,…,n?1}，0≤i＜n。此時的解空間大小為nn。相應的隱式約束為：對任意0≤i,j＜n，當i?j時，xi?xj且|i-j|?|xi-xj|。另一種顯式約束的觀點是：xi?{0,1,…,n?1}，0≤i＜n，且xi?xj(0≤i,j＜n,i?j)。與此相對應的解空間大小為n!。相應的隱式約束為：對任意0≤i,j＜n，當i?j時，|i-j|?|xi-xj|。,,,,,皇后問題的狀態(tài)空間樹是一棵排列樹。排列樹有n!個葉結點，遍歷排列樹的時間為?(n!).,,,8.2.3n-皇后算法,,,【程序8-4】n-皇后問題的回溯算法boolPlace(intk,inti,int*x){//假定第k+1個皇后放在第i列上(xk=i)，判定第k+1個皇后是否與之前的k個皇后在同一列或在同一斜線上for(intj=0;j
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞：
- 算法設計與分析 算法 設計 分析 08
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學習交流，未經(jīng)上傳用戶書面授權，請勿作他用。
鏈接地址：http://www.hcyjhs8.com/p-11499798.html