計算機算法設(shè)計五大常用算法的分析及實例-資料下載頁
2025-06-25 05:16本頁面
【正文】 題P的一個解。 回溯發(fā)解題基本步驟(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。兩個常用的剪枝函數(shù)：(1)約束函數(shù)：在擴(kuò)展結(jié)點處減去不滿足約束的子數(shù)(2)限界函數(shù)：減去得不到最優(yōu)解的子樹用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當(dāng)前擴(kuò)展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2^h(n))或O(h(n)!)內(nèi)存空間。有遞歸回溯和迭代回溯?；厮莘▽饪臻g作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。 實例——01背包問題0—1背包問題是一個子集選取問題，適合于用子集樹表示0—1背包問題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點是一個可行結(jié)點，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。 背包問題的解空間書 分支限界法 分支限界法思想分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點只有一次機會成為擴(kuò)展結(jié)點?；罱Y(jié)點一旦成為擴(kuò)展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，并重復(fù)上述結(jié)點擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。(1):常見的兩種分支限界法（1）隊列式(FIFO)分支限界法按照隊列先進(jìn)先出（FIFO）原則選取下一個節(jié)點為擴(kuò)展節(jié)點。（2）優(yōu)先隊列式分支限界法按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴(kuò)展節(jié)點。(2):分支限界法與回溯法的不同①求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。②搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。(3):分支限界法的設(shè)計思路 設(shè)求解最大化問題，解向量為X=(x1,…,xn)，xi的取值范圍為Si，|Si|=ri。在使用分支限界搜索問題的解空間樹時，先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界[down, up]，然后從根結(jié)點出發(fā)，擴(kuò)展根結(jié)點的r1個孩子結(jié)點，從而構(gòu)成分量x1的r1種可能的取值方式。對這r1個孩子結(jié)點分別估算可能的目標(biāo)函數(shù)bound(x1)，其含義：以該結(jié)點為根的子樹所有可能的取值不大于bound(x1)，即：bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)若某孩子結(jié)點的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的下界，則將該孩子結(jié)點丟棄；否則，將該孩子結(jié)點保存在待處理結(jié)點表PT中。再取PT表中目標(biāo)函數(shù)極大值結(jié)點作為擴(kuò)展的根結(jié)點，重復(fù)上述。直到一個葉子結(jié)點時的可行解X=(x1,…,xn)，及目標(biāo)函數(shù)值bound(x1,…,xn)。 實例——裝載問題(1):問題描述有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船上，其中集裝箱i的重量為wi，且w1+w2+...+wn = c1+c2。 裝載問題要求確定，是否有一個合理的裝載方案可將這n個集裝箱裝上2艘輪船。如果有，找出一種裝載方案。 例如，當(dāng)n=3,c1=c2=50,且w=[10,40,40]時，可將集裝箱1和集裝箱2裝上一艘輪船，而將集裝箱3裝在第二艘輪船；如果=[20,40,40],則無法將這3個集裝箱都裝上輪船。當(dāng)w1+w2+...+wn = c1+c2時，裝載問題等價于子集和問題。當(dāng)c1=c2，且w1+w2+...+wn = 2c1時，裝載問題等價于劃分問題。即使限制wi，i=1,2,...,n為整數(shù)，c1和c2也是整數(shù)。子集和問題與劃分問題都是NP難的。由此可知，裝載問題也是NP難的。容易證明，如果一個給定的裝載問題有解，則采用下面的策略可以得到最優(yōu)裝載方案。① 首先將第一艘輪船盡可能裝滿。②然后將剩余的集裝箱裝上第二艘輪船。（2） 算法實現(xiàn) 裝載問題算法 算法MaxLoading的計算時間和空間復(fù)雜度為O(2n).總結(jié) 算法是程序設(shè)計的靈魂，本文通過對常見五中算法（遞歸與分治理、動態(tài)規(guī)劃、貪心算法、回溯發(fā)、分支限界發(fā)）的系統(tǒng)分析和實例講解，讓本人對算法的設(shè)計和分析有了生科的體會，同時更深刻地了解了五中常見的算法。在論文結(jié)束之時，回顧一下此次設(shè)計的過程，有許多的感慨。由于此次設(shè)計主要是在校內(nèi)進(jìn)行的，在設(shè)計的過程中得到了導(dǎo)師和同學(xué)以及論壇上朋友的大量的幫助，從而能順利的完成該設(shè)計。在這個過程中令我受益匪淺，特在此表示衷心的感謝！同時還要尤其感謝我的指導(dǎo)老師的悉心指導(dǎo)，為我的設(shè)計提供科學(xué)的指導(dǎo)和分析，同時也為我提供第一手的研究資料，使我在設(shè)計的過程中能夠迅速解決難題，再次表示衷心的感謝！參考文獻(xiàn) [1] 王曉東編著. 電子工業(yè)出版社，[2] . 北京市 國鐵道出版社，19
電大資料相關(guān)推薦
鄂ICP備17016276號-1