算法分析與設(shè)計(jì)論文.doc

算法設(shè)計(jì)與分析論文題 目0-1背包問(wèn)題的算法設(shè)計(jì)策略對(duì)比與分析專(zhuān) 業(yè) 班 級(jí) 學(xué) 號(hào) 姓 名 引言對(duì)于計(jì)算機(jī)科學(xué)來(lái)說(shuō)，算法（Algorithm）的概念是至關(guān)重要的。算法是一系列解決問(wèn)題的清晰指令，也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問(wèn)題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題。不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟?；蛘呖闯砂凑找笤O(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類(lèi)問(wèn)題。算法可以使用自然語(yǔ)言、偽代碼、流程圖等多種不同的方法來(lái)描述。一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：有窮性：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；確切性：算法的每一步驟必須有確切的定義； 輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件； 輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的； 可行性：算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。計(jì)算機(jī)科學(xué)家尼克勞斯-沃思曾著過(guò)一本著名的書(shū)數(shù)據(jù)結(jié)構(gòu)十算法= 程序，可見(jiàn)算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。1 算法復(fù)雜性分析的方法介紹算法的復(fù)雜性是算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上面，所需的資源越多，我們就說(shuō)該算法的復(fù)雜性越高；反之，所需的資源越低，則該算法的復(fù)雜性越低。 計(jì)算機(jī)的資源，最重要的是時(shí)間和空間（即存儲(chǔ)器）資源。因而，算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。 不言而喻，對(duì)于任意給定的問(wèn)題，設(shè)計(jì)出復(fù)雜性盡可能地的算法是我們?cè)谠O(shè)計(jì)算法是追求的一個(gè)重要目標(biāo)；另一方面，當(dāng)給定的問(wèn)題已有多種算法時(shí)，選擇其中復(fù)雜性最低者，是我們?cè)谶x用算法適應(yīng)遵循的一個(gè)重要準(zhǔn)則。因此，算法的復(fù)雜性分析對(duì)算法的設(shè)計(jì)或選用有著重要的指導(dǎo)意義和實(shí)用價(jià)值。 關(guān)于算法的復(fù)雜性，有兩個(gè)問(wèn)題要弄清楚：用怎樣的一個(gè)量來(lái)表達(dá)一個(gè)算法的復(fù)雜性；對(duì)于給定的一個(gè)算法，怎樣具體計(jì)算它的復(fù)雜性。讓我們從比較兩對(duì)具體算法的效率開(kāi)始。1.1比較兩對(duì)算法的效率考慮問(wèn)題1：已知不重復(fù)且已經(jīng)按從小到大排好的m個(gè)整數(shù)的數(shù)組A1.m（為簡(jiǎn)單起見(jiàn)。還設(shè)m=2 k，k是一個(gè)確定的非負(fù)整數(shù)）。對(duì)于給定的整數(shù)c，要求尋找一個(gè)下標(biāo)i，使得Ai=c；若找不到，則返回一個(gè)0。問(wèn)題1的一個(gè)簡(jiǎn)單的算法是：從頭到尾掃描數(shù)組A。照此，或者掃到A的第i個(gè)分量，經(jīng)檢測(cè)滿足Ai=c；或者掃到A的最后一個(gè)分量，經(jīng)檢測(cè)仍不滿足Ai=c。我們用一個(gè)函數(shù)Search來(lái)表達(dá)這個(gè)算法：Function Search (c:integer):integer;Var J:integer; BeginJ:=1; 初始化在還沒(méi)有到達(dá)A的最后一個(gè)分量且等于c的分量還沒(méi)有找到時(shí)，查找下一個(gè)分量并且進(jìn)行檢測(cè) While (Aic)and(jc，則c只可能在A1,A2,.,Am/2-1之中，因而下一步只要在A1, A2, . ，Am/2-1中繼續(xù)查找；如果Am/2=L時(shí)，繼續(xù)查找While (not Found) and (U=L) doBeginI:=(U+L) div 2;找數(shù)組的中間分量If c=AI then Found:=Tureelse if cAI then L:=I+1 else U:=I-1;End;If Found then B_Search:=1else B_Search:=0;End;容易理解，在最壞的情況下最多只要測(cè)A中的k+1(k=logm,這里的log以2為底，下同)個(gè)分量，就判斷c是否在A中。算法Search和B_Search解決的是同一個(gè)問(wèn)題，但在最壞的情況下（所給定的c不在A中），兩個(gè)算法所需要檢測(cè)的分量個(gè)數(shù)卻大不相同，前者要m=2 k個(gè)，后者只要k+1個(gè)?？梢?jiàn)算法B_Search比算法Search高效得多。以上例子說(shuō)明：解同一個(gè)問(wèn)題，算法不同，則計(jì)算的工作量也不同，所需的計(jì)算時(shí)間隨之不同，即復(fù)雜性不同。上圖是運(yùn)行這兩種算法的時(shí)間曲線。該圖表明，當(dāng)m適當(dāng)大（mm0）時(shí)，算法B_Search比算法Search省時(shí)，而且當(dāng)m更大時(shí)，節(jié)省的時(shí)間急劇增加。不過(guò)，應(yīng)該指出：用實(shí)例的運(yùn)行時(shí)間來(lái)度量算法的時(shí)間復(fù)雜性并不合適，因?yàn)檫@個(gè)實(shí)例時(shí)間與運(yùn)行該算法的實(shí)際計(jì)算機(jī)性能有關(guān)。換句話說(shuō)，這個(gè)實(shí)例時(shí)間不單純反映算法的效率而是反映包括運(yùn)行該算法的計(jì)算機(jī)在內(nèi)的綜合效率。我們引入算法復(fù)雜性的概念是為了比較解決同一個(gè)問(wèn)題的不同算法的效率，而不想去比較運(yùn)行該算法的計(jì)算機(jī)的性能。因而，不應(yīng)該取算法運(yùn)行的實(shí)例時(shí)間作為算法復(fù)雜性的尺度。我們希望，盡量單純地反映作為算法精髓的計(jì)算方法本身的效率，而且在不實(shí)際運(yùn)行該算法的情況下就能分析出它所需要的時(shí)間和空間。1.2復(fù)雜性的計(jì)量算法的復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要的時(shí)間資源的量稱(chēng)作時(shí)間復(fù)雜性，需要的空間（即存儲(chǔ)器）資源的量稱(chēng)作空間復(fù)雜性。這個(gè)量應(yīng)該集中反映算法中所采用的方法的效率，而從運(yùn)行該算法的實(shí)際計(jì)算機(jī)中抽象出來(lái)。換句話說(shuō)，這個(gè)量應(yīng)該是只依賴(lài)于算法要解的問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A來(lái)表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，用C表示算法的復(fù)雜性，那么應(yīng)該有：C =F(N,I,A)其中F(N,I,A)是N,I,A的一個(gè)確定的三元函數(shù)。如果把時(shí)間復(fù)雜性和空間復(fù)雜性分開(kāi)，并分別用T和S來(lái)表示，那么應(yīng)該有：T =T(N,I,A) (2.1)和 S =S(N,I,A) (2.2)通常，我們讓A隱含在復(fù)雜性函數(shù)名當(dāng)中，因而將（2.1）和（2.2）分別簡(jiǎn)寫(xiě)為T(mén) =T(N,I)和 S =S(N,I)由于時(shí)間復(fù)雜性和空間復(fù)雜性概念類(lèi)同，計(jì)算方法相似，且空間復(fù)雜性分析相對(duì)地簡(jiǎn)單些，所以下文將主要地討論時(shí)間復(fù)雜性。下面以T(N,I)為例，將復(fù)雜性函數(shù)具體化。根據(jù)T(N,I)的概念，它應(yīng)該是算法在一臺(tái)抽象的計(jì)算機(jī)上運(yùn)行所需的時(shí)間。設(shè)此抽象的計(jì)算機(jī)所提供的元運(yùn)算有k種，他們分別記為O1,O2 ,.,Ok；再設(shè)這些元運(yùn)算每執(zhí)行一次所需要的時(shí)間分別為t1,t2,.,tk 。對(duì)于給定的算法A，設(shè)經(jīng)過(guò)統(tǒng)計(jì)，用到元運(yùn)算Oi的次數(shù)為ei，i=1,2,.,k ，很明顯，對(duì)于每一個(gè)i，1=i0和pi0(i=1,2,，n)的物品，選擇哪些物品裝入背包，可使在背包的容量限制之內(nèi)所裝物品的價(jià)值最大，這就是背包問(wèn)題。0-1背包特點(diǎn)是：每種物品都僅有一件，可以選擇放入或不放。0-1背包問(wèn)題:給定n種物品和一個(gè)背包。物品i的重量是Wi,其價(jià)值為Vi,背包的容量為C。應(yīng)如何選擇裝入背包的物品,使得裝入背包中物品的總價(jià)值最大? 在選擇裝入背包的物品時(shí),對(duì)每種物品i只有兩種選擇,即裝入背包為1或不裝入背包為0。不能將物品i裝入背包多次,也不能只裝入部分的物品i。021背包問(wèn)題的主要特點(diǎn)是在選擇物品i裝入背包時(shí),每種物品僅有一件,可以選擇放或不放。3.2動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法的基本思想是把原問(wèn)題分解成一系列子問(wèn)題,然后從這些子問(wèn)題中求出原問(wèn)題的解。對(duì)一個(gè)負(fù)重能力為m的背包,如果選擇裝入一個(gè)第i種物品,那么原背包問(wèn)題就轉(zhuǎn)化為負(fù)重能力為m2w的子背包問(wèn)題。由于動(dòng)態(tài)規(guī)劃算法求解過(guò)程中反復(fù)出現(xiàn)子問(wèn)題,且對(duì)每次重復(fù)出現(xiàn)的子問(wèn)題都要重新解一次,這需要多花費(fèi)不少時(shí)間,因此動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O ( n* m) ,其中n為物體的個(gè)數(shù),m為背包負(fù)重。動(dòng)態(tài)規(guī)劃是用空間換時(shí)間的一種方法的抽象。其關(guān)鍵是發(fā)現(xiàn)子問(wèn)題和記錄其結(jié)果。然后利用這些結(jié)果減輕運(yùn)算量。因?yàn)楸嘲淖罱K最大容量未知，所以，我們得從1到M一個(gè)一個(gè)的試，比如，剛開(kāi)始任選N件物品中的一個(gè)，看對(duì)應(yīng)的M的背包，能不能放進(jìn)去，如果能放進(jìn)去，并且還有多少空間，則，多出來(lái)的空間能放N-1物品中的最大價(jià)值，怎么能保證總選則是最大價(jià)值呢，看下表：測(cè)試數(shù)據(jù)：10,33,44,55,6最大容量M物品個(gè)數(shù)Nj=0-m103C0123456789物品大小W物品價(jià)值p編號(hào)00000000034i=110004444444451-n 2200045559995633000456691011cij數(shù)組保存了1,2,3號(hào)物品依次選擇后的最大價(jià)值。這個(gè)最大價(jià)值是怎么得來(lái)的呢?從背包容量為0開(kāi)始,1號(hào)物品先試,0,1,2,的容量都不能放.所以置0,背包容量為3則里面放4.這樣,這一排背包容量為4,5,6,.10的時(shí)候，最佳方案都是放4.假如1號(hào)物品放入背包.則再看2號(hào)物品.當(dāng)背包容量為3的時(shí)候，最佳方案還是上一排的最價(jià)方案c為4.而背包容量為5的時(shí)候，則最佳方案為自己的重量5.背包容量為7的時(shí)候，很顯然是5加上一個(gè)值了。加誰(shuí)?很顯然是7-4=3的時(shí)候.上一排c3的最佳方案是4.所以?？偟淖罴逊桨甘?+4為9.這樣.一排一排推下去。最右下放的數(shù)據(jù)就是最大的價(jià)值了。(注意第3排的背包容量為7的時(shí)候,最佳方案不是本身的6.而是上一排的9.說(shuō)明這時(shí)候3號(hào)物品沒(méi)有被選.選的是1,2號(hào)物品.所以得9。從以上最大價(jià)值的構(gòu)造過(guò)程中可以看出。f(n,m)=maxf(n-1,m), f(n-1,m-wn)+P(n,m)這就是書(shū)本上寫(xiě)的動(dòng)態(tài)規(guī)劃方程.3.3回溯法用回溯法求解0-1背包問(wèn)題的算法思路是按照物品的單位價(jià)值從大到小排序,計(jì)算當(dāng)前節(jié)點(diǎn)的上界,搜索左子樹(shù)。只有當(dāng)右子樹(shù)包含可行解時(shí)才搜索右子樹(shù)。剪去右子樹(shù)的條件是當(dāng)前價(jià)值加上剩余物品的總價(jià)值小于當(dāng)前的最優(yōu)總價(jià)值時(shí),不需搜索右子樹(shù),可將右子樹(shù)剪去?；厮莘ㄓ靡欢ǖ募糁M(jìn)行優(yōu)化,算法的時(shí)間復(fù)雜度為O ( n3 2n ) , n為物品個(gè)數(shù)。3.4 貪心算法在求解0-1背包問(wèn)題時(shí),對(duì)貪心算法可以使用一些策略, 使其得到的解更接近最優(yōu)解。具體方案如下:(1) 價(jià)值優(yōu)先策略:從剩余的物品中,選取價(jià)值最大的可以裝入背包的物品。此時(shí),價(jià)值最大的優(yōu)先被裝入背包,然后裝入下一個(gè)價(jià)值最大的物品,直到不能再裝入剩下的物品為止。(2) 重量?jī)?yōu)先策略:從剩余的物品中選取重量最小的物品裝入背包中,這種策略一般不能得到最優(yōu)解。(3) 單位價(jià)值優(yōu)先策略:根據(jù)價(jià)值/重量的比值,按照每一次選取剩下的物品中比值最大的物品裝入背包,直到不能再裝入為止。以上三種策略都不能保證得到最優(yōu)解,但三種策略相比較而言,第三種策略與最優(yōu)解相差較小。如果可以選擇物品的一部分,用單位價(jià)值策略可以保證得到最優(yōu)解。在貪心算法時(shí)間復(fù)雜度的估算中,由于需要對(duì)重量或價(jià)值或兩者的比值進(jìn)行排序，所以貪心算法的時(shí)間復(fù)雜度為O(n*logn)。3.5分支限界法在解0-1背包問(wèn)題的優(yōu)先隊(duì)列式分支限界法中，活結(jié)點(diǎn)優(yōu)先隊(duì)列中結(jié)點(diǎn)元素N的優(yōu)先級(jí)由該結(jié)點(diǎn)的上界函數(shù)Bound計(jì)算出的值uprofit給出。子集樹(shù)中以結(jié)點(diǎn)N為根的子樹(shù)中任一結(jié)點(diǎn)的價(jià)值不超過(guò)N.profit。可用一個(gè)最大堆來(lái)實(shí)現(xiàn)活結(jié)點(diǎn)優(yōu)先隊(duì)列。堆中元素類(lèi)型為HeapNode，其私有成員有uprofit,profit,weight和level。對(duì)于任意活結(jié)點(diǎn)N，N.weight是結(jié)點(diǎn)N所相應(yīng)的重量；N.profit是N所相應(yīng)的價(jià)值；N.uprofit是結(jié)點(diǎn)N的價(jià)值上界，最大堆以這個(gè)值作為優(yōu)先級(jí)。子集空間樹(shù)中結(jié)點(diǎn)類(lèi)型為bbnode。3 算法比較以上方法對(duì)背包問(wèn)題的求解各有其優(yōu)缺點(diǎn)，如表3-1所示。表3-1求解背包問(wèn)題的算法比較算法名稱(chēng)時(shí)間復(fù)雜度優(yōu)點(diǎn)缺點(diǎn)改進(jìn)回溯法O(n*2n )優(yōu)解速度慢剪枝動(dòng)態(tài)規(guī)劃O(n*m)最優(yōu)解速度慢遞歸方程求解貪心算法O(n*logn)速度快不一定是最優(yōu)解啟發(fā)式方法分支限界法O(n*2n)最優(yōu)解速度慢0-1背包問(wèn)題是一個(gè)經(jīng)典的NP問(wèn)題。對(duì)于規(guī)模過(guò)大的0-1背包問(wèn)題，人們還是無(wú)法找到完美的求解方法。所有智能算法都有其局限性，只能在一定范圍內(nèi)求解。由于各種算法都有其自身的優(yōu)缺點(diǎn)，許多學(xué)者通過(guò)利用一種算法的優(yōu)點(diǎn)同時(shí)結(jié)合其他算法避免該算法的不足，出現(xiàn)了混合算法，這樣就取得了很大的成功。0-1背包問(wèn)題未來(lái)的發(fā)展趨勢(shì)是繼續(xù)研究結(jié)合多種算法的混合優(yōu)化算法；通過(guò)其他學(xué)科的算法得到啟發(fā)，提出一種新的算法，繼而推動(dòng)0-1背包問(wèn)題的研究。4 總結(jié)在寫(xiě)論文的過(guò)程中，我上網(wǎng)查詢(xún)了很多資料，并且也參考了書(shū)本里的內(nèi)容，通過(guò)這些我對(duì)算法分析設(shè)計(jì)又有了進(jìn)一步的了解