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

6 算法初步結(jié)課論文 0-1背包問題的算法設(shè)計(jì)策略對比與分析孫旭東（天津師范大學(xué)2011級(jí)軟件工程5班，天津，300387）摘 要：算法的復(fù)雜性是算法效率的度量，是評價(jià)算法優(yōu)劣的重要依據(jù)。一個(gè)算法的復(fù)雜性的高低主要體現(xiàn)在運(yùn)行該算法需要占取多大的計(jì)算機(jī)資源。0-1背包問題是一例典型的組合優(yōu)化的NP完全問題。但是對于規(guī)模過大的0-1背包問題，還是無法找到最完美的求解方法。本文主要通過對背包問題使用不同的算法進(jìn)行求解，并對他們的時(shí)間復(fù)雜度，空間復(fù)雜度，優(yōu)缺點(diǎn)進(jìn)行比較并提出改進(jìn)的措施。從而深化對于算法復(fù)雜性的認(rèn)知。關(guān)鍵詞: 算法的復(fù)雜性；計(jì)算機(jī)資源；0-1背包問題；精確最優(yōu)解；近似最優(yōu)解 0-1 Knapsack problem algorithm design strategyof contrast and analysisSun Xu-dong(2011 the software engineering class five，Tianjin normal university，Tianjin ,300387)Abstract: The algorithm is the complexity of the algorithm is efficiency measure, the important basis of evaluation algorithm. The complexity of an algorithm of high and low in running the algorithm need to take how much computer resources. 0-1 knapsack problem is a typical combinatorial optimization of np-complete problems. But for 0-1 knapsack problem too big, still cant find the perfect solution. This article mainly through to the knapsack problem using different algorithms for solving, and for their time complexity and space complexity, the advantages and disadvantages are compared and improved measures are put forward. To deepen the perception of algorithm complexity.Key words:The complexity of the algorithm; Computer resources;0-1 knapsack problem; Accurate optimal solutions; The approximate optimal solution0 引言對于計(jì)算機(jī)科學(xué)而言，算法（Algorithm）的概念是至關(guān)重要的。算法是一系列解決問題的清晰指令，即能夠?qū)σ欢ㄒ?guī)范的輸出，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或者不適用于某個(gè)問題，那么，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。用不同的算法來完成相同的任務(wù)需要的時(shí)間、空間以及效率都有可能會(huì)有所不同。而一個(gè)算法的優(yōu)劣主要通過時(shí)間復(fù)雜度和空間復(fù)雜度來衡量。算法可以看成有基本運(yùn)算以及規(guī)定的運(yùn)算順序所構(gòu)成的完成解題步驟。算法可以使用自然語言、偽代碼、流程圖等多種不同的算法來描述。一個(gè)算法應(yīng)該具有五個(gè)重要的特征，它們分別是：有窮性：一個(gè)算法必須保證執(zhí)行有限步驟之后結(jié)束；確切性：算法的每一個(gè)步驟必須有明確的定義；可行性：算法原則上能夠精確地進(jìn)行，并且人們用筆和紙?jiān)谧鲇邢薮芜\(yùn)算之后即可完成；輸入：一個(gè)算法有0個(gè)或者多個(gè)輸入，以刻畫運(yùn)算對象的初始情況，所謂0個(gè)輸入是指算法本身出了初始條件；輸出；一個(gè)算法有一個(gè)或者多個(gè)輸出，以反映輸出數(shù)據(jù)加工后的結(jié)果沒有輸出的算法是沒有任何意義的.計(jì)算機(jī)科學(xué)家尼克勞斯-沃思曾經(jīng)寫過一本著名的書數(shù)據(jù)結(jié)構(gòu)+算法=程序，由此可見算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。1 算法復(fù)雜性分析的方法介紹算法的復(fù)雜性是算法效率的度量，是評價(jià)算法優(yōu)劣的重要依據(jù)。一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上面，所需的資源越多，那就稱之為該算法的復(fù)雜性越高；反之，所需的資源越低，則該算法的復(fù)雜性越低。 計(jì)算機(jī)的資源，最重要的是時(shí)間資源和空間（即存儲(chǔ)器）資源。因而，算法的復(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è)問題要弄清楚：用怎樣的一個(gè)量來表達(dá)一個(gè)算法的復(fù)雜性；對于給定的一個(gè)算法，怎樣具體計(jì)算它的復(fù)雜性。2 常見的算法分析設(shè)計(jì)策略介紹我們一般常見的幾種算法分析設(shè)計(jì)策略主要有：動(dòng)態(tài)規(guī)劃、貪心算法、回溯法。接下來我主要介紹一下這幾種算法。2.1 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計(jì)算那樣，具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動(dòng)態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時(shí)，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動(dòng)態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會(huì)并掌握這一設(shè)計(jì)方法。動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。在編程中常用解決最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線等問題。2.2 貪心算法所謂貪心算法（又稱貪婪算法）是指，在對問題求解時(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è)可以試用貪心算法解的題目，貪心解的確不錯(cuò)，可惜不是最優(yōu)解。2.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)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(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)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。換句話說，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。用回溯法解題的一般步驟：（1）針對所給問題，定義問題的解空間； （2）確定易于搜索的解空間結(jié)構(gòu)； （3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。3 0-1背包問題的幾種算法背包問題是一類具有廣泛的實(shí)際應(yīng)用背景的經(jīng)典NP-hard組合優(yōu)化問題，在解決大量的復(fù)雜組合優(yōu)化問題時(shí)，它常常作為一個(gè)子問題出現(xiàn)，從實(shí)際觀點(diǎn)看，許多問題可以用背包問題來描述，如裝箱問題，貨倉裝載，預(yù)算控制，存儲(chǔ)分配，項(xiàng)目選擇決策等等，都是典型的應(yīng)用例子。隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，背包公鑰密碼在電子商務(wù)中的公鑰設(shè)計(jì)中也起著重要的作用。然而當(dāng)問題的規(guī)模較大時(shí)，得到最優(yōu)解是極其困難的。因此，借鑒前人的研究成果，開展對解決復(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)化問題中得到了很好的應(yīng)用。綜上所述，傳統(tǒng)求解該問題的方法可以概括為精確算法和近似算法，其中精確算法有動(dòng)態(tài)規(guī)劃法、回溯法、分支限界法等，近似算法有遺傳算法、貪婪法、粒子群算法、蟻群算法等，由于精確算法的時(shí)間復(fù)雜性和空間復(fù)雜性等缺點(diǎn)，近年來利用近似算法求解背包問題成為重點(diǎn)。因此此處對精確算法只做簡單的描述，對幾種近似算法則較為詳細(xì)的說明了它們的思想和在背包問題中的運(yùn)用。除了以上幾種常見的算法，最近幾年又出現(xiàn)了知識(shí)進(jìn)化算法、二進(jìn)制差異演化算法等新的算法解決背包問題，本文也對它們做一個(gè)簡介。最后提出了將知識(shí)發(fā)現(xiàn)的方法引入遺傳算法中來解決背包問題，擬提高單存遺傳算法的搜索效率和解的質(zhì)量。3.1 0-1背包問題描述一個(gè)旅行者有一個(gè)最多能裝C公斤重量的背包，已知n個(gè)重量和價(jià)值分別為ci0和pi0(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裝入背包時(shí),每種物品僅有一件,可以選擇放或不放。3.2動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法的基本思想是把原問題分解成一系列子問題,然后從這些子問題中求出原問題的解。對一個(gè)負(fù)重能力為m的背包,如果選擇裝入一個(gè)第i種物品,那么原背包問題就轉(zhuǎn)化為負(fù)重能力為m2w的子背包問題。由于動(dòng)態(tài)規(guī)劃算法求解過程中反復(fù)出現(xiàn)子問題,且對每次重復(fù)出現(xià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)子問題和記錄其結(jié)果。然后利用這些結(jié)果減輕運(yùn)算量。因?yàn)楸嘲淖罱K最大容量未知，所以，我們得從1到M一個(gè)一個(gè)的試，比如，剛開始任選N件物品中的一個(gè)，看對應(yīng)的M的背包，能不能放進(jìn)去，如果能放進(jìn)去，并且還有多少空間，則，多出來的空間能放N-1物品中的最大價(jià)值，怎么能保證總選則是最大價(jià)值呢，看下表：測試數(shù)據(jù)：(10,3)，(3,4)，（4,5），（5,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à)值是怎么得來的呢?從背包容量為0開始,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è)值了。加誰?很顯然是7-4=3的時(shí)候.上一排c3的最佳方案是4.所以。總的最佳方案是5+4為9.這樣.一排一排推下去。最右下放的數(shù)據(jù)就是最大的價(jià)值了。(注意第3排的背包容量為7的時(shí)候,最佳方案不是本身的6.而是上一排的9.說明這時(shí)候3號(hào)物品沒有被選.選的是1,2號(hào)物品.所以得9。從以上最大價(jià)值的構(gòu)造過程中可以看出：f(n,m)=maxf(n-1,m), f(n-1,m-wn)+P(n,m)這就是書本上寫的動(dòng)態(tài)規(guī)劃方程。3.3回溯法用回溯法求解0-1背包問題的算法思路是按照物品的單位價(jià)值從大到小排序,計(jì)算當(dāng)前節(jié)點(diǎn)的上界,搜索左子樹。只有當(dāng)右子樹包含可行解時(shí)才搜索右子樹。剪去右子樹的條件是當(dāng)前價(jià)值加上剩余物品的總價(jià)值小于當(dāng)前的最優(yōu)總價(jià)值時(shí),不需搜索右子樹,可將右子樹剪去?；厮莘ㄓ靡欢ǖ募糁M(jìn)行優(yōu)化,算法的時(shí)間復(fù)雜度為O ( n3 2n ) , n為物品個(gè)數(shù)。3.4 貪心算法在求解0-1背包問題時(shí),對貪心算法可以使用一些策略, 使其得到的解更接近最優(yōu)解。具體方案如下:(1) 價(jià)值優(yōu)先策略:從剩余的物品中,選取價(jià)值最大的可以裝入背包的物品。此時(shí),價(jià)值最大的優(yōu)先被裝入背包,然后裝入下一個(gè)價(jià)值最大的物品,直到不能再裝入剩下的物品為止。(2) 重量優(yōu)先策略:從剩余的物品中選取重量最小的物品裝入背包中,這種策略一般不能得到最優(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)。4 算法比較0-1背包問題是一