背包問題的實(shí)用求解算法研究.pdf

1、背包問題在信息加密、預(yù)算控制、項(xiàng)目選擇、材料切割、貨物裝載、網(wǎng)絡(luò)信息安全等應(yīng)用中具有重要的價(jià)值。從計(jì)算復(fù)雜性理論看，背包問題是一個(gè)經(jīng)典NP難解問題。半個(gè)多世紀(jì)以來，該問題一直是算法與復(fù)雜性研究的熱點(diǎn)問題之一。論文研究了背包問題的實(shí)用求解算法，提出了改進(jìn)的新算法，并利用Maltab對(duì)幾種算法進(jìn)行了仿真實(shí)驗(yàn)，測(cè)試的結(jié)果顯示出新算法在解決0/1背包問題時(shí)表現(xiàn)出了良好的性能。在論文中主要進(jìn)行的工作如下： 1.首先討論了傳統(tǒng)算法設(shè)計(jì)技術(shù)求

2、解背包問題的方法，主要有遞歸算法、動(dòng)態(tài)規(guī)劃算法、分支定界法、圖論法、貪婪算法等，同時(shí)討論了背包問題在電子商務(wù)公鑰密碼系統(tǒng)中的應(yīng)用。 2.論文中重點(diǎn)研究了遺傳算法(GA)在解決背包問題上的應(yīng)用，在廣泛了解現(xiàn)有遺傳算法的優(yōu)缺點(diǎn)的基礎(chǔ)上，結(jié)合耗散結(jié)構(gòu)理論提出了耗散遺傳算法(DGA)。耗散遺傳算法能夠在一定程度上克服普通遺傳算法的缺點(diǎn)。通過仿真實(shí)驗(yàn)證實(shí)了該方法在解決0/1背包問題上的有效性。 3.另外本文還研究了蟻群算法(ACO