資源描述：
《計算機求解背包問題的研究》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、貴州大學碩士學位論文計算機求解背包問題的研究姓名：王成強申請學位級別：碩士專業(yè)：計算機軟件與理論指導教師：李祥20010301致謝Ys2№衷心感謝導師李祥教授!從論文的選題、可行性研究、文件的收集、到研究工作的開展，特別是論文的撰寫，老師給予了無微不至的關懷，提出了許多富有建設性的意見。導師認真、嚴謹、踏實的科研作風和淵博的學識，使我受益非淺。今后惟有加倍努力，以報答導師的培育之情。最后，感謝所有關心和幫助過我的人們!謝謝!摘要算法研究是計算機科學研究的核心問題之一。其中包含了可計算性理論，它討論的是“什么樣的問題可以利用
2、計算機來解決”，當然并非任何問題都可以利用計算機來解決。另外還包含了NP完全理論，討論的是一個可計算的問題是否存在有效的算法(即多項式時間的算法)，七十年代，以庫克(cook)為首的組合數(shù)學家們建立了NP完全理論，提出：有一類問題，它們的難度是相似的，只要其中一個問題有有效的算法，則所有問題都有有效算法；反之，若能證明其中有一個問題沒有有效算法，則所有問題都沒有有效算法，即如下命題：NP=P?。這一問題是目前的一個世界性問題，還沒有能夠解決的跡象，但是大多數(shù)科學家認為NP<>P，即NP完全類問題沒有有效算法。背包問題是一個
3、傳統(tǒng)問題，它的出現(xiàn)非常早，通俗的表達方式是：有若干物品，它們有不同的重量和價值，一個旅行者要出門旅行，他可以帶走一些物品，但是他能夠攜帶的重量有限，于是問題就是：這個旅行者要怎樣選擇物品才能使他攜帶的物品的價值最大。在長期的求解研究過程中，人們發(fā)現(xiàn)雖然背包問題表述起來非常簡單，但是求解卻非常困難，相當長的時間都找不到比較有效的方法。于是，背包問題就成了組合數(shù)學中的～個經(jīng)典問題。在NP完全理論建立后不久，背包伺題就被證明屬于NP完全問題，也就是說，背包問題可能沒有有效算法，在規(guī)模比較大的時候，我們無法得到背包問題的解。很久以
4、前，人們在認識自然的過程中，提出了大量的實際的數(shù)學問題，這些問題在當時并沒有理論依據(jù)來求解，所以人們總是會暫時提出一些近似算法，用于實踐，取得了很好的效果。在NP完全理論建立之后，既然NP完全問題暫時是沒有有效算法的，則必須提出它們的近似算法作為暫時的解決方案。在背包問題的研究過程中，最早出現(xiàn)的近似算法是貪心法，它的基本原理是盡可能先選擇單位價值高的物品，直到背包裝滿為止。但是從本文的討論可以看出，貪心法的結果在最壞情況下可能非常壞，以至于根本不能作為可用的近似解。針對上述討論，本文對計算機求解背包問題進行了理論與實際方面
5、的研究，主要工作如下：1、本文提出了一種改進的貪心法，得到了一個較好的理論結果，這一結果敘述為如下定理。O／1背包最優(yōu)問題：在約束條件∑qt≤6下，使目標maxz=∑c，x達到極大，此處刪或1’1<退肌不妨設暑≥毒孫≥囂a定理，設z‘為前述背包問題的最優(yōu)解．z”={從第m個物品開始選擇。使用貪心法所褥的解，。令z8=maxF，『_1，2，A玎)．(其中旦≥魚≥^≥魚)則有以下結論，(1)礦sz‘≤2zs；(2)改進的算法的時q噸％同復雜度為0(姐2)。2、解決大規(guī)模背包問題的另一種方法是利用發(fā)展迅速的計算機網(wǎng)絡求解，當前，
6、網(wǎng)絡的發(fā)展極為迅速，計算機的并行和分布式處理技術也在不斷成熟，利用分布技術來求解大規(guī)模的背包問題成為可能。本文使用winsock作為通信工具，綜合應用了windows平臺的多種技術，對分布式求解背包問題作了一定的探索，在windows平臺下對窮舉法和深度優(yōu)先搜索算法進行了試驗。實驗表明，由于使用多臺機器，對于窮舉算法起到了相當明顯的加速效果，但對深度優(yōu)先搜索算法沒有多大用處．并分析了其中的原因。本文的主要結果已經(jīng)在由中國計算機學會、香港電腦學會聯(lián)合主辦的第七界聯(lián)合國際計算機會議(The7”JointIntemational
7、comPuterconference)上發(fā)表，并被收入會議論文集。關鍵詞NP完全問題0／l背包問題近似算法貪心法深度優(yōu)先搜索時間復雜度winsock分布式計算計算機網(wǎng)絡Internet近似解的估計AbstractThealgorithmisoneofthemostimportantprObleminthecomputerscience。Thereinto，therearethecomputabletheorywhichdiscusstheproblemscanbes01vedbycomputing，andtheNPcomp
8、letetheorywhichdiscussifthereisausablealgorithmforacomputableproblem．At70’s．MrCookandothercombinatoricorscreatedtheNPcompletetheory．Thetheorysaystherear
