計(jì)算機(jī)算法分析與設(shè)計(jì)論文 背包問題的算法設(shè)計(jì)策略對比與分析

1、算法設(shè)計(jì)與分析課程考查論文背包問題的算法設(shè)計(jì)策略對比與分析0-1背包問題的算法設(shè)計(jì)策略對比與分析0 引言對于計(jì)算機(jī)科學(xué)來說，算法（Algorithm）的概念是至關(guān)重要的。算法是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟?；蛘呖闯砂凑找笤O(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類問題。算法可以使

2、用自然語言、偽代碼、流程圖等多種不同的方法來描述。一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：有窮性：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；確切性：算法的每一步驟必須有確切的定義； 輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件； 輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的； 可行性：算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。計(jì)算機(jī)科學(xué)家尼克勞斯-沃思曾著過一本著名的書數(shù)據(jù)結(jié)構(gòu)十算法= 程序，可見算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。1 算法復(fù)雜性分析的方法介紹算法的復(fù)雜性是算法效率

3、的度量，是評價(jià)算法優(yōu)劣的重要依據(jù)。一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上面，所需的資源越多，我們就說該算法的復(fù)雜性越高；反之，所需的資源越低，則該算法的復(fù)雜性越低。 計(jì)算機(jī)的資源，最重要的是時(shí)間和空間（即存儲器）資源。因而，算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。 不言而喻，對于任意給定的問題，設(shè)計(jì)出復(fù)雜性盡可能地的算法是我們在設(shè)計(jì)算法是追求的一個(gè)重要目標(biāo)；另一方面，當(dāng)給定的問題已有多種算法時(shí)，選擇其中復(fù)雜性最低者，是我們在選用算法適應(yīng)遵循的一個(gè)重要準(zhǔn)則。因此，算法的復(fù)雜性分析對算法的設(shè)計(jì)或選用有著重要的指導(dǎo)意義和實(shí)用價(jià)值。 關(guān)于算法的復(fù)雜性，有兩個(gè)問題要弄清楚：用

4、怎樣的一個(gè)量來表達(dá)一個(gè)算法的復(fù)雜性；對于給定的一個(gè)算法，怎樣具體計(jì)算它的復(fù)雜性。讓我們從比較兩對具體算法的效率開始。1.1比較兩對算法的效率考慮問題1：已知不重復(fù)且已經(jīng)按從小到大排好的m個(gè)整數(shù)的數(shù)組A1.m（為簡單起見。還設(shè)m=2 k，k是一個(gè)確定的非負(fù)整數(shù)）。對于給定的整數(shù)c，要求尋找一個(gè)下標(biāo)i，使得Ai=c；若找不到，則返回一個(gè)0。問題1的一個(gè)簡單的算法是：從頭到尾掃描數(shù)組A。照此，或者掃到A的第i個(gè)分量，經(jīng)檢測滿足Ai=c；或者掃到A的最后一個(gè)分量，經(jīng)檢測仍不滿足Ai=c。我們用一個(gè)函數(shù)Search來表達(dá)這個(gè)算法：Function Search (c:integer):integer;V

5、ar J:integer; BeginJ:=1; 初始化在還沒有到達(dá)A的最后一個(gè)分量且等于c的分量還沒有找到時(shí)，查找下一個(gè)分量并且進(jìn)行檢測 While (Ai<c)and(j<m) do          j:=j+1; If Aj=c then search:=j 在數(shù)組A中找到等于c的分量，且此分量的下標(biāo)為j else Search:=0; 在數(shù)組中找不到等于c的分量End;容易看出，在最壞的情況下，這個(gè)算法要檢測A的所有m個(gè)分量才能判斷在A中找不到等于c的分量。解決問題1的另一個(gè)算法利用到已知條件

6、中A已排好序的性質(zhì)。它首先拿A的中間分量Am/2與c比較，如果Am/2=c則解已找到。如果Am/2>c，則c只可能在A1,A2,.,Am/2-1之中，因而下一步只要在A1, A2, . ，Am/2-1中繼續(xù)查找；如果Am/2<c，則c只可能在Am/2+1,Am/2+2,.,Am之中，因而下一步只要在Am/2+1,Am/2+2,.,Am中繼續(xù)查找。不管哪一種情形，都把下一步需要繼續(xù)查找的范圍縮小了一半。再拿這一半的子數(shù)組的中間分量與c比較，重復(fù)上述步驟。照此重復(fù)下去，總有一個(gè)時(shí)候，或者找到一個(gè)i使得Ai=c，或者子數(shù)組為空（即子數(shù)組下界大于上界）。前一種情況找到了等于c的分量，后一種

7、情況則找不到。這個(gè)新算法因?yàn)橛蟹磸?fù)把供查找的數(shù)組分成兩半，然后在其中一半繼續(xù)查找的特征，我們稱為二分查找算法。它可以用函數(shù)B_Search來表達(dá)：Function B_Search ( c: integer):integer;VarL,U,I：integer;U和L分別是要查找的數(shù)組的下標(biāo)的上界和下界Found：boolean;BeginL:=1; U:=m; 初始化數(shù)組下標(biāo)的上下界Found:=false; 當(dāng)前要查找的范圍是AL.AU。當(dāng)?shù)扔赾的分量還沒有找到且U>=L時(shí)，繼續(xù)查找While (not Found) and (U>=L) doBeginI:=(U+L) div

8、2;找數(shù)組的中間分量If c=AI then Found:=Tureelse if c>AI then L:=I+1 else U:=I-1;End;If Found then B_Search:=1else B_Search:=0;End;容易理解，在最壞的情況下最多只要測A中的k+1(k=logm,這里的log以2為底，下同)個(gè)分量，就判斷c是否在A中。算法Search和B_Search解決的是同一個(gè)問題，但在最壞的情況下（所給定的c不在A中），兩個(gè)算法所需要檢測的分量個(gè)數(shù)卻大不相同，前者要m=2 k個(gè)，后者只要k+1個(gè)?？梢娝惴˙_Search比算法Search高效得多。以上例子說

9、明：解同一個(gè)問題，算法不同，則計(jì)算的工作量也不同，所需的計(jì)算時(shí)間隨之不同，即復(fù)雜性不同。上圖是運(yùn)行這兩種算法的時(shí)間曲線。該圖表明，當(dāng)m適當(dāng)大（m>m0）時(shí)，算法B_Search比算法Search省時(shí)，而且當(dāng)m更大時(shí)，節(jié)省的時(shí)間急劇增加。不過，應(yīng)該指出：用實(shí)例的運(yùn)行時(shí)間來度量算法的時(shí)間復(fù)雜性并不合適，因?yàn)檫@個(gè)實(shí)例時(shí)間與運(yùn)行該算法的實(shí)際計(jì)算機(jī)性能有關(guān)。換句話說，這個(gè)實(shí)例時(shí)間不單純反映算法的效率而是反映包括運(yùn)行該算法的計(jì)算機(jī)在內(nèi)的綜合效率。我們引入算法復(fù)雜性的概念是為了比較解決同一個(gè)問題的不同算法的效率，而不想去比較運(yùn)行該算法的計(jì)算機(jī)的性能。因而，不應(yīng)該取算法運(yùn)行的實(shí)例時(shí)間作為算法復(fù)雜性的尺度

10、。我們希望，盡量單純地反映作為算法精髓的計(jì)算方法本身的效率，而且在不實(shí)際運(yùn)行該算法的情況下就能分析出它所需要的時(shí)間和空間。1.2復(fù)雜性的計(jì)量算法的復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要的時(shí)間資源的量稱作時(shí)間復(fù)雜性，需要的空間（即存儲器）資源的量稱作空間復(fù)雜性。這個(gè)量應(yīng)該集中反映算法中所采用的方法的效率，而從運(yùn)行該算法的實(shí)際計(jì)算機(jī)中抽象出來。換句話說，這個(gè)量應(yīng)該是只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A來表示算法要解問題的規(guī)模、算法的輸入和算法本身，用C表示算法的復(fù)雜性，那么應(yīng)該有：C =F(N,I,A)其中F(N,I,A)是N,I,A的一個(gè)確定的三元

11、函數(shù)。如果把時(shí)間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示，那么應(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）分別簡寫為T =T(N,I)和 S =S(N,I)由于時(shí)間復(fù)雜性和空間復(fù)雜性概念類同，計(jì)算方法相似，且空間復(fù)雜性分析相對地簡單些，所以下文將主要地討論時(shí)間復(fù)雜性。下面以T(N,I)為例，將復(fù)雜性函數(shù)具體化。根據(jù)T(N,I)的概念，它應(yīng)該是算法在一臺抽象的計(jì)算機(jī)上運(yùn)行所需的時(shí)間。設(shè)此抽象的計(jì)算機(jī)所提供的元運(yùn)算有k種，他們分別記為O1,O2 ,.,Ok；再設(shè)這些元運(yùn)算每執(zhí)行一次所需要的時(shí)間

12、分別為t1,t2,.,tk 。對于給定的算法A，設(shè)經(jīng)過統(tǒng)計(jì)，用到元運(yùn)算Oi的次數(shù)為ei，i=1,2,.,k ，很明顯，對于每一個(gè)i，1<=i<=k，ei是N和I的函數(shù)，即ei=ei(N,I)。那么有：(2.3)其中ti，i=1,2,.,k,是與N,I無關(guān)的常數(shù)。顯然，我們不可能對規(guī)模N的每一種合法的輸入I都去統(tǒng)計(jì)ei(N,I),i=1,2,k。因此T(N,I)的表達(dá)式還得進(jìn)一步簡化，或者說，我們只能在規(guī)模為N的某些或某類有代表性的合法輸入中統(tǒng)計(jì)相應(yīng)的ei , i=1,2,k，評價(jià)時(shí)間復(fù)雜性。下面只考慮三種情況的復(fù)雜性，即最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜性，并分別記為Tmax

13、(N )、Tmin(N)和Tavg(N )。在數(shù)學(xué)上有：(2.4)(2.5)(2.6)其中，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ù)雜性各從某一個(gè)角度來反映算法的效率，各有各的用處，也各有各的局限性。但實(shí)踐表明可操作性最好的且最有實(shí)際價(jià)值的是最壞情況下的時(shí)間復(fù)雜性。下面我們將把對時(shí)間復(fù)雜性分析的主要興趣放在這種情形上。一般來說，最好情況和最壞情況的時(shí)間復(fù)雜性是很難計(jì)量的，原因是對于問題的任意確定的規(guī)模N達(dá)到了Tmax(

14、N)的合法輸入難以確定，而規(guī)模N的每一個(gè)輸入的概率也難以預(yù)測或確定。我們有時(shí)也按平均情況計(jì)量時(shí)間復(fù)雜性，但那時(shí)在對P(I)做了一些人為的假設(shè)（比如等概率）之后才進(jìn)行的。所做的假設(shè)是否符合實(shí)際總是缺乏根據(jù)。因此，在最好情況和平均情況下的時(shí)間復(fù)雜性分析還僅僅是停留在理論上。1.3復(fù)雜性的漸近性態(tài)及其階隨著經(jīng)濟(jì)的發(fā)展、社會的進(jìn)步、科學(xué)研究的深入，要求用計(jì)算機(jī)解決的問題越來越復(fù)雜，規(guī)模越來越大。但是，如果對這類問題的算法進(jìn)行分析用的是第二段所提供的方法，把所有的元運(yùn)算都考慮進(jìn)去，精打細(xì)算，那么，由于問題的規(guī)模很大且結(jié)構(gòu)復(fù)雜，算法分析的工作量之大、步驟之繁將令人難以承受。因此，人們提出了對于規(guī)模充分大、

15、結(jié)構(gòu)又十分復(fù)雜的問題的求解算法，其復(fù)雜性分析應(yīng)如何簡化的問題。我們先要引入復(fù)雜性漸近性態(tài)的概念。設(shè)T(N)是在第二段中所定義的關(guān)于算法A的復(fù)雜性函數(shù)。一般說來，當(dāng)N單調(diào)增加且趨于時(shí),T(N)也將單調(diào)增加趨于。對于T(N)，如果存在T(N)，使得當(dāng)N時(shí)有：(T(N )-T(N )/T(N ) 0那么，我們就說T(N)是T(N)當(dāng)N時(shí)的漸近性態(tài)，或叫T(N)為算法A當(dāng)N的漸近復(fù)雜性而與T(N)相區(qū)別，因?yàn)樵跀?shù)學(xué)上，T(N)是T(N)當(dāng)N時(shí)的漸近表達(dá)式。直觀上，T(N)是T(N)中略去低階項(xiàng)所留下的主項(xiàng)。所以它無疑比T(N)來得簡單。比如當(dāng)T(N)=3N 2+4Nlog2N +7時(shí)，T(N)的一個(gè)答

16、案是3N 2，因?yàn)檫@時(shí)有：顯然3N 2比3N 2 +4Nlog2N +7簡單得多。由于當(dāng)N時(shí)T(N)漸近于T(N)，我們有理由用T(N)來替代T(N)作為算法A在N時(shí)的復(fù)雜性的度量。而且由于于T(N)明顯地比T(N)簡單，這種替代明顯地是對復(fù)雜性分析的一種簡化。進(jìn)一步，考慮到分析算法的復(fù)雜性的目的在于比較求解同一間題的兩個(gè)不同算法的效率，而當(dāng)要比較的兩個(gè)算法的漸近復(fù)雜性的階不相同時(shí)，只要能確定出各自的階，就可以判定哪一個(gè)算法的效率高。換句話說，這時(shí)的漸近復(fù)雜性分析只要關(guān)心T(N)的階就夠了，不必關(guān)心包含在T(N)中的常數(shù)因子。所以，我們常常又對T(N)的分析進(jìn)-步簡化，即假設(shè)算法中用到的所有不

17、同的元運(yùn)算各執(zhí)行一次，所需要的時(shí)間都是一個(gè)單位時(shí)間。綜上所述，我們已經(jīng)給出了簡化算法復(fù)雜性分析的方法和步驟，即只要考察當(dāng)問題的規(guī)模充分大時(shí)，算法復(fù)雜性在漸近意義下的階。與此簡化的復(fù)雜性分析方法相配套，需要引入五個(gè)漸近意義下的記號：、和。以下設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)Cg(N)。則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=(g(N)。這時(shí)我們還說f(N)的階不高于g(N)的階。舉幾個(gè)例子：(1)因?yàn)閷λ械腘1有3N4N，我們有3N =(N)；(2)因?yàn)楫?dāng)N1時(shí)有N+10241025N，我

18、們有N +1024=(N)；(3)因?yàn)楫?dāng)N10時(shí)有2N 2+11N -103N 2，我們有2N 2+11N -10=(N 2)；(4)因?yàn)閷λ蠳1有N 2N 3，我們有N2=(N 3)；(5)作為一個(gè)反例N 3(N 2)。因?yàn)槿舨蝗?，則存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有N3C N 2，即NC 。顯然當(dāng)取N =max(N0,C+l)時(shí)這個(gè)不等式不成立，所以N3(N 2)。按照大的定義，容易證明它有如下運(yùn)算規(guī)則：(f)+(g)=(max(f,g)； (f)+ (g)=(f +g)； (f)·(g)= (f·g)； 如果g(N)= (f(N)，則(f)+ (g)= (

19、f)； (Cf(N)= (f(N)，其中C是一個(gè)正的常數(shù)； f =(f)； 1.4復(fù)雜性漸近階的重要性計(jì)算機(jī)的設(shè)計(jì)和制造技術(shù)在突飛猛進(jìn)，一代又一代的計(jì)算機(jī)的計(jì)算速度和存儲容量在直線增長。有的人因此認(rèn)為不必要再去苦苦地追求高效率的算法，從而不必要再去無謂地進(jìn)行復(fù)雜性的分析。他們以為低效的算法可以由高速的計(jì)算機(jī)來彌補(bǔ)，以為在可接受的一定時(shí)間內(nèi)用低效的算法完不成的任務(wù)，只要移植到高速的計(jì)算機(jī)上就能完成。這是一種錯(cuò)覺。造成這種錯(cuò)覺的原因是他們沒看到：隨著經(jīng)濟(jì)的發(fā)展、社會的進(jìn)步、科學(xué)研究的深入，要求計(jì)算機(jī)解決的問題越來越復(fù)雜、規(guī)模越來越大，也呈線性增長之勢；而問題復(fù)雜程度和規(guī)模的線性增長導(dǎo)致的時(shí)耗的增長

20、和空間需求的增長，對低效算法來說，都是超線性的，決非計(jì)算機(jī)速度和容量的線性增長帶來的時(shí)耗減少和存儲空間的擴(kuò)大所能抵銷。事實(shí)上，我們只要對效率上有代表性的幾個(gè)檔次的算法作些簡單的分析對比就能明白這一點(diǎn)。我們還是以時(shí)間效率為例。設(shè)A1,A2,和A6。是求解同一間題的6個(gè)不同的算法，它們的漸近時(shí)間復(fù)雜性分別為N，NlogN，N 2，N 3，2N，N!。讓這六種算法各在C1和C2兩臺計(jì)算機(jī)上運(yùn)行，并設(shè)計(jì)算機(jī)C2的計(jì)算速度是計(jì)算機(jī)C1的10倍。在可接受的一段時(shí)間內(nèi)，設(shè)在C1上算法Ai可能求解的問題的規(guī)模為N1i，而在C2上可能求解的問題的規(guī)模為N2i，那么，我們就應(yīng)該有Ti(N2i)=10Ti(N1i)

21、，其中Ti(N)是算法Ai漸近的時(shí)間復(fù)雜性，i=1,2,6。分別解出N2i和N1i的關(guān)系，可列成下表：表1-1算法與漸近時(shí)間復(fù)雜性的關(guān)系算法漸進(jìn)時(shí)間復(fù)雜性T(N)在C1上可解的規(guī)模N1在C2上可解的規(guī)模N2N1和N2的關(guān)系A(chǔ)1NN11N21N21=10N11A2NlogNN12N22N2210N12A3N2N13N23A4N3N14N24A52NN15N25N25 =N15+log10A6N!N16N26N26 =N16+小的常數(shù)從表1-1的最后一列可以清楚地看到，對于高效的算法A1，計(jì)算機(jī)的計(jì)算速度增長10倍，可求解的規(guī)模同步增長10倍；對于A2，可求解的問題的規(guī)模的增長與計(jì)算機(jī)的計(jì)算速度的

22、增長接近同步；但對于低效的算法A3，情況就大不相同，計(jì)算機(jī)的計(jì)算速度增長10倍只換取可求解的問題的規(guī)模增加log10。當(dāng)問題的規(guī)模充分大時(shí)，這個(gè)增加的數(shù)字是微不足道的。換句話說，對于低效的算法，計(jì)算機(jī)的計(jì)算速度成倍乃至數(shù)10倍地增長基本上不帶來求解規(guī)模的增益。因此，對于低效算法要擴(kuò)大解題規(guī)模，不能寄希望于移植算法到高速的計(jì)算機(jī)上，而應(yīng)該把著眼點(diǎn)放在算法的改進(jìn)上。從表1-l的最后一列我們還看到，限制求解問題規(guī)模的關(guān)鍵因素是算法漸近復(fù)雜性的階，對于表中的前四種算法，其漸近的時(shí)間復(fù)雜性與規(guī)模N的一個(gè)確定的冪同階，相應(yīng)地，計(jì)算機(jī)的計(jì)算速度的乘法增長帶來的是求解問題的規(guī)模的乘法增長，只是隨著冪次的提高，

23、規(guī)模增長的倍數(shù)在降低。我們把漸近復(fù)雜性與規(guī)模N的冪同階的這類算法稱為多項(xiàng)式算法。對于表中的后兩種算法，其漸近的時(shí)間復(fù)雜性與規(guī)模N的一個(gè)指數(shù)函數(shù)同階，相應(yīng)地計(jì)算機(jī)的計(jì)算速度的乘法增長只帶來求解問題規(guī)模的加法增長。我們把漸近復(fù)雜性與規(guī)模N的指數(shù)同階的這類算法稱為指數(shù)型算法。多項(xiàng)式算法和指數(shù)型算法是在效率上有質(zhì)的區(qū)別的兩類算法。這兩類算法的區(qū)別的內(nèi)在原因是算法漸近復(fù)雜性的階的區(qū)別?？梢姡惴ǖ臐u近復(fù)雜性的階對于算法的效率有著決定性的意義。所以在討論算法的復(fù)雜性時(shí)基本上都只關(guān)心它的漸近階。多項(xiàng)式算法是有效的算法。絕大多數(shù)的問題都有多項(xiàng)式算法。但也有一些問題還未找到多項(xiàng)式算法，只找到指數(shù)型算法。我們在討

24、論算法復(fù)雜性的漸近階的重要性的同時(shí)，有兩條要記?。骸皬?fù)雜性的漸近階比較低的算法比復(fù)雜性的漸近階比較高的算法有效”這個(gè)結(jié)論，只是在問題的求解規(guī)模充分大時(shí)才成立。比如算法A4比A5有效只是在N 3<2N，即Nc 時(shí)才成立。其中c是方程N(yùn) 3=2N的解。當(dāng)N <c時(shí)，A5反而比A4有效。所以對于規(guī)模小的問題，不要盲目地選用復(fù)雜性階比較低的算法。其原因一方面是如上所說，復(fù)雜性階比較低的算法在規(guī)模小時(shí)不一定比復(fù)雜性階比較高的算法更有效；另方面，在規(guī)模小時(shí)，決定工作效率的可能不是算法的效率而是算法的簡單性，哪一種算法簡單，實(shí)現(xiàn)起來快，就選用那一種算法。 當(dāng)要比較的兩個(gè)算法的漸近復(fù)雜性的階相同時(shí)

25、，必須進(jìn)一步考察漸近復(fù)雜性表達(dá)式中常數(shù)因子才能判別它們誰好誰差。顯然常數(shù)因子小的優(yōu)于常數(shù)因子大的算法。比如漸近復(fù)雜性為N1ogN/l00的算法顯然比漸近復(fù)雜性為l00NlogN的算法來得有效。2 常見的算法分析設(shè)計(jì)策略介紹我們一般常見的幾種算法分析設(shè)計(jì)策略主要有：動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法。接下來我主要介紹一下這幾種算法。1.1動態(tài)規(guī)劃動態(tài)規(guī)劃程序設(shè)計(jì)是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計(jì)算那樣，具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計(jì)往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同

26、，因而動態(tài)規(guī)劃的設(shè)計(jì)方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時(shí)，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會并掌握這一設(shè)計(jì)方法。動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個(gè)解都對應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不

27、同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。在編程中常用解決最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線等問題。1.2 貪心算法所謂貪心算法（又稱貪婪算法）是指，在對

28、問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法的基本思路：a.建立數(shù)學(xué)模型來描述問題。b.把求解的問題分成若干個(gè)子問題。c.對每一子問題求解，得到子問題的局部最優(yōu)解。d.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。實(shí)現(xiàn)該算法的過程： a.從問題的某一初始解出發(fā)；b.while 能朝給定總目標(biāo)前進(jìn)一步 doc.求出可行解的一個(gè)解元素；d.由所有解元素組合成問題的一個(gè)可行解。e.下面是一個(gè)可以試用貪心算法解

29、的題目，貪心解的確不錯(cuò)，可惜不是最優(yōu)解。1.3 回溯法回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合

30、數(shù)較大的問題?；厮莘ǖ幕舅枷耄捍_定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。換句話說，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。用回溯法解題的一般步驟：（1）針對所給

31、問題，定義問題的解空間； （2）確定易于搜索的解空間結(jié)構(gòu)； （3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。1.4 分支限界法分支定界 (branch and bound) 搜索法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方法搜索解空間樹，并且，在分支定界算法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)。分支定界法的思想是：首先確定目標(biāo)值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。解題步驟：（1）在問題的邊帶權(quán)的解空間樹中進(jìn)行廣度優(yōu)先搜索 （2）找一個(gè)葉結(jié)點(diǎn)使其對應(yīng)路徑的權(quán)最小(最大)（3）當(dāng)搜索到達(dá)一個(gè)擴(kuò)展

32、結(jié)點(diǎn)時(shí),一次性擴(kuò)展它的所有兒子（4）將滿足約束條件且最小耗費(fèi)函數(shù)£目標(biāo)函數(shù)限界的兒子,插入活結(jié)點(diǎn)表中（5）從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)同樣擴(kuò)展（6）直到找到所需的解或活動結(jié)點(diǎn)表為空為止3 0-1背包問題的幾種算法背包問題是一類具有廣泛的實(shí)際應(yīng)用背景的經(jīng)典NP-hard組合優(yōu)化問題，在解決大量的復(fù)雜組合優(yōu)化問題時(shí)，它常常作為一個(gè)子問題出現(xiàn)，從實(shí)際觀點(diǎn)看，許多問題可以用背包問題來描述，如裝箱問題，貨倉裝載，預(yù)算控制，存儲分配，項(xiàng)目選擇決策等等，都是典型的應(yīng)用例子。隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，背包公鑰密碼在電子商務(wù)中的公鑰設(shè)計(jì)中也起著重要的作用。然而當(dāng)問題的規(guī)模較大時(shí)，得到最優(yōu)解是極其困難的。因此，

33、借鑒前人的研究成果，開展對解決復(fù)雜組合優(yōu)化問題的算法研究或改進(jìn)是一項(xiàng)十分優(yōu)異的工作。Dantzing 在20世紀(jì)50年代首先進(jìn)行了開創(chuàng)性的研究，利用貪心算法求得了0-1背包問題最優(yōu)解的上屆。1974年，horowitz和salmi利用分支限界法解答了背包問題，并提出了背包問題的可分性，指出了求解該問題的一條新途徑。隨后，Balas和Zemel提出了背包問題的“核”思想，是背包問題的呀牛獲得了較大進(jìn)展。上世紀(jì)九十年代以后，隨著生物仿生技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)，例如遺傳算法已經(jīng)在 0-1背包問題上得到了較好的應(yīng)用，螞蟻算法、粒子群等仿生算法也在組合優(yōu)化問

34、題中得到了很好的應(yīng)用。綜上所述，傳統(tǒng)求解該問題的方法可以概括為精確算法和近似算法，其中精確算法有動態(tài)規(guī)劃法、回溯法、分支限界法等，近似算法有遺傳算法、貪婪法、粒子群算法、蟻群算法等，由于精確算法的時(shí)間復(fù)雜性和空間復(fù)雜性等缺點(diǎn)，近年來利用近似算法求解背包問題成為重點(diǎn)。因此此處對精確算法只做簡單的描述，對幾種近似算法則較為詳細(xì)的說明了它們的思想和在背包問題中的運(yùn)用。除了以上幾種常見的算法，最近幾年又出現(xiàn)了知識進(jìn)化算法、二進(jìn)制差異演化算法等新的算法解決背包問題，本文也對它們做一個(gè)簡介。最后提出了將知識發(fā)現(xiàn)的方法引入遺傳算法中來解決背包問題，擬提高單存遺傳算法的搜索效率和解的質(zhì)量。3.1 0-1背包問

35、題描述一個(gè)旅行者有一個(gè)最多能裝C公斤重量的背包，已知n個(gè)重量和價(jià)值分別為ci>0和pi>0(i=1,2,，n)的物品，選擇哪些物品裝入背包，可使在背包的容量限制之內(nèi)所裝物品的價(jià)值最大，這就是背包問題。0-1背包特點(diǎn)是：每種物品都僅有一件，可以選擇放入或不放。0-1背包問題:給定n種物品和一個(gè)背包。物品i的重量是Wi,其價(jià)值為Vi,背包的容量為C。應(yīng)如何選擇裝入背包的物品,使得裝入背包中物品的總價(jià)值最大? 在選擇裝入背包的物品時(shí),對每種物品i只有兩種選擇,即裝入背包為1或不裝入背包為0。不能將物品i裝入背包多次,也不能只裝入部分的物品i。021背包問題的主要特點(diǎn)是在選擇物品i裝入背包

36、時(shí),每種物品僅有一件,可以選擇放或不放。3.2動態(tài)規(guī)劃動態(tài)規(guī)劃算法的基本思想是把原問題分解成一系列子問題,然后從這些子問題中求出原問題的解。對一個(gè)負(fù)重能力為m的背包,如果選擇裝入一個(gè)第i種物品,那么原背包問題就轉(zhuǎn)化為負(fù)重能力為m2w的子背包問題。由于動態(tài)規(guī)劃算法求解過程中反復(fù)出現(xiàn)子問題,且對每次重復(fù)出現(xiàn)的子問題都要重新解一次,這需要多花費(fèi)不少時(shí)間,因此動態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O ( n* m) ,其中n為物體的個(gè)數(shù),m為背包負(fù)重。動態(tài)規(guī)劃是用空間換時(shí)間的一種方法的抽象。其關(guān)鍵是發(fā)現(xiàn)子問題和記錄其結(jié)果。然后利用這些結(jié)果減輕運(yùn)算量。因?yàn)楸嘲淖罱K最大容量未知，所以，我們得從1到M一個(gè)一個(gè)的試，比

37、如，剛開始任選N件物品中的一個(gè)，看對應(yīng)的M的背包，能不能放進(jìn)去，如果能放進(jìn)去，并且還有多少空間，則，多出來的空間能放N-1物品中的最大價(jià)值，怎么能保證總選則是最大價(jià)值呢，看下表：測試數(shù)據(jù)：10,33,44,55,6最大容量M物品個(gè)數(shù)Nj=0-m103C0123456789物品大小W物品價(jià)值p編號00000000034i=110004444444451-n 2200045559995633000456691011cij數(shù)組保存了1,2,3號物品依次選擇后的最大價(jià)值。這個(gè)最大價(jià)值是怎么得來的呢?從背包容量為0開始,1號物品先試,0,1,2,的容量都不能放.所以置0,背包容量為3則里面放4.這樣,這

38、一排背包容量為4,5,6,.10的時(shí)候，最佳方案都是放4.假如1號物品放入背包.則再看2號物品.當(dāng)背包容量為3的時(shí)候，最佳方案還是上一排的最價(jià)方案c為4.而背包容量為5的時(shí)候，則最佳方案為自己的重量5.背包容量為7的時(shí)候，很顯然是5加上一個(gè)值了。加誰?很顯然是7-4=3的時(shí)候.上一排c3的最佳方案是4.所以?？偟淖罴逊桨甘?+4為9.這樣.一排一排推下去。最右下放的數(shù)據(jù)就是最大的價(jià)值了。(注意第3排的背包容量為7的時(shí)候,最佳方案不是本身的6.而是上一排的9.說明這時(shí)候3號物品沒有被選.選的是1,2號物品.所以得9。從以上最大價(jià)值的構(gòu)造過程中可以看出。f(n,m)=maxf(n-1,m), f(

39、n-1,m-wn)+P(n,m)這就是書本上寫的動態(tài)規(guī)劃方程.下面是一種實(shí)現(xiàn)過程： #include<iostream>using namespace std;int c10100;/*對應(yīng)每種情況的最大價(jià)值*/int knapsack(int m,int n) int i,j,w10,p10; for(i=1;i<n+1;i+) cin>>wi>>pi; for(i=0;i<10;i+) for(j=0;j<100;j+) cij=0;/*初始化數(shù)組*/ for(i=1;i<n+1;i+) for(j=1;j<m+1;j+)

40、if(wi<=j) /*如果當(dāng)前物品的容量小于背包容量*/ if(pi+ci-1j-wi>ci-1j) /*如果本物品的價(jià)值加上背包剩下的空間能放的物品的價(jià)值*/ /*大于上一次選擇的最佳方案則更新cij*/ cij=pi+ci-1j-wi; else cij=ci-1j; else cij=ci-1j; cout<<"背包中放著重量如下的物品："<<endl; /*確定選取了哪幾個(gè)物品*/ i=n;j=m; while(i>=0)&&(j>=0) if(pi+ci-1j-wi>ci-1j)&&a

41、mp;(i-1>=0)&&(j-wi>=0) cout<<wi<<" " j=j-wi; i=i-1; else i=i-1; cout<<endl; return(cnm);void main() int m,n; cout<<"輸入總背包容量：" cin>>m; cout<<endl; cout<<"輸入背包最多可放的物品個(gè)數(shù)：" cin>>n; cout<<endl; cout<<&

42、quot;輸入每一組數(shù)據(jù):"<<endl; cout<<"背包所能容納的最大價(jià)值為："<<knapsack(m,n)<<endl;3.3回溯法用回溯法求解0-1背包問題的算法思路是按照物品的單位價(jià)值從大到小排序,計(jì)算當(dāng)前節(jié)點(diǎn)的上界,搜索左子樹。只有當(dāng)右子樹包含可行解時(shí)才搜索右子樹。剪去右子樹的條件是當(dāng)前價(jià)值加上剩余物品的總價(jià)值小于當(dāng)前的最優(yōu)總價(jià)值時(shí),不需搜索右子樹,可將右子樹剪去。回溯法用一定的剪枝進(jìn)行優(yōu)化,算法的時(shí)間復(fù)雜度為O ( n3 2n ) , n為物品個(gè)數(shù)。下面是一種實(shí)現(xiàn)過程： #include<io

43、stream> using namespace std; class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m<=n;m+) cout<<bestxm<<" " cout<<endl; ; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品數(shù) int *w;/物品重量數(shù)組 int *p;/物品價(jià)值數(shù)組 i

44、nt cw;/當(dāng)前重量 int cp;/當(dāng)前價(jià)值 int bestp;/當(dāng)前最優(yōu)值 int *bestx;/當(dāng)前最優(yōu)解 int *x;/當(dāng)前解 ; int Knap:Bound(int i) /計(jì)算上界 int cleft=c-cw;/剩余容量 int b=cp; /以物品單位重量價(jià)值遞減序裝入物品 while(i<=n&&wi<=cleft) cleft-=wi; b+=pi; i+; /裝滿背包 if(i<=n) b+=pi/wi*cleft; return b; void Knap:Backtrack(int i) if(i>n) if(bestp

45、<cp) for(int j=1;j<=n;j+) bestxj=xj; bestp=cp; return; if(cw+wi<=c) /搜索左子樹 xi=1; cw+=wi; cp+=pi; Backtrack(i+1); cw-=wi; cp-=pi; if(Bound(i+1)>bestp)/搜索右子樹 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n); public: int operator<=(Object a)const return (d&

46、gt;=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) /為Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i<=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W<=c) return P;/裝入所有物品 /依物品單位重量排序 float f; for( i=0;i<n;i+) for(int j=i;j<n;j+)

47、 if(Qi.d<Qj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( i=1;i<=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); K.print(); delete Q; delete K.w; dele

48、te K.p; return K.bestp; void main() int *p; int *w; int c=0; int n=0; int i=0; cout<<"請輸入背包個(gè)數(shù)："<<endl; cin>>n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout<<"請輸入個(gè)背包的價(jià)值："<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<"請輸入個(gè)背包的重量："<

49、<endl; for(i=1;i<=n;i+) cin>>wi; cout<<"請輸入背包容量："<<endl; cin>>c; cout<<Knapsack(p,w,c,n)<<endl; 3.4 貪心算法在求解0-1背包問題時(shí),對貪心算法可以使用一些策略, 使其得到的解更接近最優(yōu)解。具體方案如下:(1) 價(jià)值優(yōu)先策略:從剩余的物品中,選取價(jià)值最大的可以裝入背包的物品。此時(shí),價(jià)值最大的優(yōu)先被裝入背包,然后裝入下一個(gè)價(jià)值最大的物品,直到不能再裝入剩下的物品為止。(2) 重量優(yōu)先策略:從剩余的

50、物品中選取重量最小的物品裝入背包中,這種策略一般不能得到最優(yōu)解。(3) 單位價(jià)值優(yōu)先策略:根據(jù)價(jià)值/重量的比值,按照每一次選取剩下的物品中比值最大的物品裝入背包,直到不能再裝入為止。以上三種策略都不能保證得到最優(yōu)解,但三種策略相比較而言,第三種策略與最優(yōu)解相差較小。如果可以選擇物品的一部分,用單位價(jià)值策略可以保證得到最優(yōu)解。在貪心算法時(shí)間復(fù)雜度的估算中,由于需要對重量或價(jià)值或兩者的比值進(jìn)行排序，所以貪心算法的時(shí)間復(fù)雜度為O(n*logn)。下面是一種實(shí)現(xiàn)過程： #include <iostream.h>#include <math.h>#include <stri

51、ng.h>#include "time.h"#include "windows.h"#include <stdlib.h>#include <stdio.h>#define num 100void bagloading(int x,float p,float w,float c,int n) /x取值為0或1，xi=1當(dāng)且僅當(dāng)背包i背裝載； /p是物品價(jià)值； /w是物品重量； /c表示背包的容量； /n表示物品的件數(shù)； float t,k,pwnum; int i,j,m,kk; for(i=0;i<n;i+) pwi=pi/wi; /對各個(gè)點(diǎn)的坐標(biāo)按由大到小進(jìn)行排序(使用改進(jìn)的冒泡排序) m=n-1; while (m>0) kk=0; for(j=0;j<m;j+) if (pwj<pwj+1) t=pj; pj=pj+1; pj+1=t; k=wj; wj=wj+1; wj+1=k; kk=j; m=kk; /按p/w次序從大到小選擇物品 i=0; while(i<n