算法分析與設(shè)計(jì)論文-背包問題的算法設(shè)計(jì)策略對(duì)比與分析-預(yù)覽頁
【正文】 例，將復(fù)雜性函數(shù)具體化。那么有： () 其中 ti， i=1,2,..,k,是與 N,I 無關(guān)的常數(shù)。在數(shù)學(xué)上有： () () () 其中， DN 是規(guī)模為 N 的合法輸入的集合； I *是 DN 中一個(gè)使 T(N,I *)達(dá)到Tmax(N)的合法輸入， 是 DN 中一個(gè)使 T(N, )到 Tmin(N)的合法輸入；而 P(I)是在算法的應(yīng)用中出現(xiàn)輸入 I 的概率。 一般來說，最好情況和最壞情況的時(shí)間復(fù)雜性是很難計(jì)量的，原因是對(duì)于問題的任意確定的規(guī)模 N 達(dá)到了 Tmax(N)的合法輸入難以確定，而規(guī)模 N 的每一個(gè)輸入的概率也難以預(yù)測(cè)或確定。 2 常見的算法分析設(shè)計(jì) 策略介紹 我們一般常見的幾種算法分析設(shè)計(jì)策略主要有：動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)往往是針對(duì)一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對(duì)不同的問題，有各具特色的解題方法，而不存在一種萬能的動(dòng)態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。在這類問題中，可能會(huì)有許多可行解。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。這就是動(dòng)態(tài)規(guī)劃法的基本思路。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。 c..對(duì)每一子問題求解，得到子問題的局部最優(yōu)解。 回溯法 回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。 回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。 用回溯法解題的一般步驟： （ 1）針對(duì)所給問題，定義問題的解空間； （ 2）確定易于搜索的解空間結(jié)構(gòu)； （ 3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。 解題步驟： （ 1）在問題的邊帶權(quán)的解空間樹中進(jìn)行廣度優(yōu)先搜索 （ 2）找一個(gè)葉結(jié)點(diǎn)使其對(duì)應(yīng)路徑的權(quán)最小 (最大 ) （ 3）當(dāng)搜索到達(dá)一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí) ,一次性擴(kuò)展它的所有兒子 （ 4）將 滿足約束條件且最小耗費(fèi)函數(shù) ?目標(biāo)函數(shù)限界的兒子 ,插入活結(jié)點(diǎn)表中 （ 5）從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)同樣擴(kuò)展 （ 6）直到找到所需的解或活動(dòng)結(jié)點(diǎn)表為空為止 3 01 背包問題的幾種算法 背包問題是一類具有廣泛的實(shí)際應(yīng)用背景的經(jīng)典 NPhard 組合優(yōu)化問題，在解決大量的復(fù)雜組合優(yōu)化問題時(shí)，它常常作為一個(gè)子問題出現(xiàn)，從實(shí)際觀點(diǎn)看，許多問題可以用背包問題來描述，如裝箱問題，貨倉裝載，預(yù)算控制，存儲(chǔ)分配，項(xiàng)目選擇決策等等，都是典型的應(yīng)用例子。 Dantzing 在 20 世紀(jì) 50 年代首先進(jìn)行了開創(chuàng)性的研究，利用貪心算法求得了 01 背包問題最優(yōu)解的上屆。 綜上所述，傳統(tǒng)求解該問題的方法可以概括為精確算法和近似算法，其中精確算法有動(dòng)態(tài)規(guī)劃法、回溯法、分支限界法等，近似算法有遺傳算法、貪婪法、粒子群算法、蟻群算法等，由于精確算法的時(shí)間復(fù)雜性和空間復(fù)雜性等缺點(diǎn)，近年來利用近似算法求解背包問題成為重點(diǎn)。 01 背包問題描述 一個(gè)旅行者有一個(gè)最多能裝 C 公斤重量的背包，已知 n 個(gè)重量和價(jià)值分別為 ci0 和 pi0(i=1,2,?， n)的物品，選擇哪些物品裝入背包，可使在背包的容量限制之內(nèi)所裝物品的價(jià)值最大，這就是背包問題。應(yīng)如何選擇裝入背包的物品 ,使得裝入背包中物品的總價(jià)值最大 ? 在選擇裝入背包的物品時(shí) ,對(duì)每種物品 i 只有兩種選擇 ,即裝入背包為 1 或不裝入背包為 0。對(duì)一個(gè)負(fù)重能力為 m 的背包 ,如果選擇裝入一個(gè)第 i 種物品 ,那 么原背包問題就轉(zhuǎn)化為負(fù)重能力為 m2w 的子背包問題。然后利用這些結(jié)果減輕運(yùn)算量?？偟淖罴?方案是 5+4 為 .一排一排推下去。 f(n,m)=max{f(n1,m), f(n1,mw[n])+P(n,m)}這就是書本上寫的動(dòng)態(tài)規(guī)劃方程 . 回溯法 用回溯法求解 01背包問題的算法思路是按照物品的單位價(jià)值從大到小排序 ,計(jì)算當(dāng)前節(jié)點(diǎn)的上界 ,搜索左子樹。 貪心算法 在求解 01背包問題時(shí) ,對(duì)貪心算法可以使用一些策略 , 使其得到的解更接近最優(yōu)解。 (3) 單位價(jià)值優(yōu)先策略 :根據(jù)價(jià)值 /重量的比值 ,按照每一次選取剩下的物品中比值最大的物品裝入背包 ,直到不能再裝入為止。 分支限界法 在解 01 背包問題的優(yōu)先隊(duì)列式分支限界法中，活結(jié)點(diǎn) 優(yōu)先隊(duì)列中結(jié)點(diǎn)元素N 的優(yōu)先級(jí)由該結(jié)點(diǎn)的上界函數(shù) Bound 計(jì)算出的值 uprofit 給出。對(duì)于任意活結(jié)點(diǎn) N， 是結(jié)點(diǎn) N 所相應(yīng)的重量； 是 N 所相應(yīng)的價(jià)值； 是結(jié)點(diǎn) N 的價(jià)值上界，最大堆以這個(gè)值作為優(yōu)先級(jí)。對(duì)于規(guī)模過大的 01背包問題，人們還是無法找到完美的求解方法。 4 總結(jié) 在寫論文的過程中，我上網(wǎng)查詢了很多資料，并且也參考了書本里的內(nèi)容，通過這些我對(duì)算法分析設(shè)計(jì)又有了進(jìn)一步的了解，對(duì)算法的復(fù)雜度也有了
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1