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