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