计算机求解背包问题的研究

《计算机求解背包问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、贵州大学硕士学位论文计算机求解背包问题的研究姓名：王成强申请学位级别：硕士专业：计算机软件与理论指导教师：李祥20010301致谢Ys2№衷心感谢导师李祥教授!从论文的选题、可行性研究、文件的收集、到研究工作的开展，特别是论文的撰写，老师给予了无微不至的关怀，提出了许多富有建设性的意见。导师认真、严谨、踏实的科研作风和渊博的学识，使我受益非浅。今后惟有加倍努力，以报答导师的培育之情。最后，感谢所有关心和帮助过我的人们!谢谢!摘要算法研究是计算机科学研究的核心问题之一。其中包含了可计算性理论，它讨论的是“什么样的问题可以利用

2、计算机来解决”，当然并非任何问题都可以利用计算机来解决。另外还包含了NP完全理论，讨论的是一个可计算的问题是否存在有效的算法(即多项式时间的算法)，七十年代，以库克(cook)为首的组合数学家们建立了NP完全理论，提出：有一类问题，它们的难度是相似的，只要其中一个问题有有效的算法，则所有问题都有有效算法；反之，若能证明其中有一个问题没有有效算法，则所有问题都没有有效算法，即如下命题：NP=P?。这一问题是目前的一个世界性问题，还没有能够解决的迹象，但是大多数科学家认为NP<>P，即NP完全类问题没有有效算法。背包问题是一个

3、传统问题，它的出现非常早，通俗的表达方式是：有若干物品，它们有不同的重量和价值，一个旅行者要出门旅行，他可以带走一些物品，但是他能够携带的重量有限，于是问题就是：这个旅行者要怎样选择物品才能使他携带的物品的价值最大。在长期的求解研究过程中，人们发现虽然背包问题表述起来非常简单，但是求解却非常困难，相当长的时间都找不到比较有效的方法。于是，背包问题就成了组合数学中的～个经典问题。在NP完全理论建立后不久，背包伺题就被证明属于NP完全问题，也就是说，背包问题可能没有有效算法，在规模比较大的时候，我们无法得到背包问题的解。很久以

4、前，人们在认识自然的过程中，提出了大量的实际的数学问题，这些问题在当时并没有理论依据来求解，所以人们总是会暂时提出一些近似算法，用于实践，取得了很好的效果。在NP完全理论建立之后，既然NP完全问题暂时是没有有效算法的，则必须提出它们的近似算法作为暂时的解决方案。在背包问题的研究过程中，最早出现的近似算法是贪心法，它的基本原理是尽可能先选择单位价值高的物品，直到背包装满为止。但是从本文的讨论可以看出，贪心法的结果在最坏情况下可能非常坏，以至于根本不能作为可用的近似解。针对上述讨论，本文对计算机求解背包问题进行了理论与实际方面

5、的研究，主要工作如下：1、本文提出了一种改进的贪心法，得到了一个较好的理论结果，这一结果叙述为如下定理。O／1背包最优问题：在约束条件∑qt≤6下，使目标maxz=∑c，x达到极大，此处删或1’1<退肌不妨设暑≥毒孙≥嚣a定理，设z‘为前述背包问题的最优解．z”={从第m个物品开始选择。使用贪心法所褥的解，。令z8=maxF，『_1，2，A玎)．(其中旦≥鱼≥^≥鱼)则有以下结论，(1)矿sz‘≤2zs；(2)改进的算法的时q吨％同复杂度为0(姐2)。2、解决大规模背包问题的另一种方法是利用发展迅速的计算机网络求解，当前，

6、网络的发展极为迅速，计算机的并行和分布式处理技术也在不断成熟，利用分布技术来求解大规模的背包问题成为可能。本文使用winsock作为通信工具，综合应用了windows平台的多种技术，对分布式求解背包问题作了一定的探索，在windows平台下对穷举法和深度优先搜索算法进行了试验。实验表明，由于使用多台机器，对于穷举算法起到了相当明显的加速效果，但对深度优先搜索算法没有多大用处．并分析了其中的原因。本文的主要结果已经在由中国计算机学会、香港电脑学会联合主办的第七界联合国际计算机会议(The7”JointIntemational

7、comPuterconference)上发表，并被收入会议论文集。关键词NP完全问题0／l背包问题近似算法贪心法深度优先搜索时间复杂度winsock分布式计算计算机网络Internet近似解的估计AbstractThealgorithmisoneofthemostimportantprObleminthecomputerscience。Thereinto，therearethecomputabletheorywhichdiscusstheproblemscanbes01vedbycomputing，andtheNPcomp

8、letetheorywhichdiscussifthereisausablealgorithmforacomputableproblem．At70’s．MrCookandothercombinatoricorscreatedtheNPcompletetheory．Thetheorysaystherear