《计算机求解背包问题的研究》由会员分享，可在线阅读，更多相关《计算机求解背包问题的研究（31页珍藏版）》请在金锄头文库上搜索。
1、贵州大学硕士学位论文计算机求解背包问题的研究姓名：王成强申请学位级别：硕士专业：计算机软件与理论指导教师：李祥20010301致谢Ys 2 衷心感谢导师李祥教授! 从论文的选题、可行性研究、文件的收集、到研究工作的开展，特别是论文的撰写，老师给予了无微不至的关怀，提出了许多富有建设性的意见。导师认真、严谨、踏实的科研作风和渊博的学识，使我受益非浅。今后惟有加倍努力，以报答导师的培育之情。最后，感谢所有关心和帮助过我的人们!谢谢!摘要算法研究是计算机科学研究的核心问题之一。其中包含了可计算性理 论，它讨论的是“什么样的问题可以利用计算机来解决”，当然并非任何问 题都可以利用计算机来解决。另外还包
2、含了N P 完全理论，讨论的是一个可 计算的问题是否存在有效的算法( 即多项式时间的算法) ，七十年代，以库克( c o o k ) 为首的组合数学家们建立了N P 完全理论， 提出：有一类问题，它们的难度是相似的，只要其中一个问题有有效的算法， 则所有问题都有有效算法；反之，若能证明其中有一个问题没有有效算法， 则所有问题都没有有效算法，即如下命题：N P = P ? 。这一问题是目前的一个 世界性问题，还没有能够解决的迹象，但是大多数科学家认为N P P ，即N P 完全类问题没有有效算法。背包问题是一个传统问题，它的出现非常早，通俗的表达方式是：有 若干物品，它们有不同的重量和价值，一个
3、旅行者要出门旅行，他可以带走 一些物品，但是他能够携带的重量有限，于是问题就是：这个旅行者要怎样 选择物品才能使他携带的物品的价值最大。在长期的求解研究过程中，人们 发现虽然背包问题表述起来非常简单，但是求解却非常困难，相当长的时间 都找不到比较有效的方法。于是，背包问题就成了组合数学中的个经典问 题。在N P 完全理论建立后不久，背包伺题就被证明属于N P 完全问题，也就 是说，背包问题可能没有有效算法，在规模比较大的时候，我们无法得到背 包问题的解。很久以前，人们在认识自然的过程中，提出了大量的实际的数学问题，这些问题在当时并没有理论依据来求解，所以人们总是会暂时提出一些近似 算法，用于实
4、践，取得了很好的效果。在N P 完全理论建立之后，既然N P 完全问题暂时是没有有效算法的，则必须提出它们的近似算法作为暂时的解 决方案。在背包问题的研究过程中，最早出现的近似算法是贪心法，它的基 本原理是尽可能先选择单位价值高的物品，直到背包装满为止。但是从本文 的讨论可以看出，贪心法的结果在最坏情况下可能非常坏，以至于根本不能作为可用的近似解。针对上述讨论，本文对计算机求解背包问题进行了理论与实际方面的研究，主要工作如下：1 、本文提出了一种改进的贪心法，得到了一个较好的理论结果，这一 结果叙述为如下定理。O 1 背包最优问题：在约束条件q t 6下，使目标m a x z = c ，x达到
5、极大，此处删或1 1 P ，n a m e l yN Pc o m p l e t ep r o b l e mh a v en oa n yu s a g ea l g o r i t h m T h e0 1 一k n a p s a c kp r o b l e misat r a d i t i o n a lp r o b l e m A ne x p r e s s i o no fi ti st h a tt h e r ea r em a n ya r t i c l e sw h i c hh a v ed i f f e r e n tw e i g h ta n dv a
6、 l u e O n ep e r s o nw h oi sg o i n gt ot r a v e lc a nt a k es o m eo ft h ea r t i c l e sw i t hh i 讥，b u th ec a nc a r r ya1 i m i t e dw e i g h t A n dt h ep r o b l e mi sh o wt oc h o o s et h ea r t i c l e sh ec a ng e tm o s tv a l u e T h eO l k n a p s a c kp r o b l e mi st o od i
7、 f f i c u l tt ob es o l v e d A f t e rt h eN Pc o m D l e t et h e o r yh a sb e e ne s t a b l i s h e d ，s o m e o n ep r o v e dt h a tt h eO 1 一k n a p s a c kp r o b l e misaN Pc o m p l e t ep r o b l e m N a m e l y ，m a y b et h e0 1 一k n a p s a c kp r o b l e mh a sn o tau s a g ea l g
8、o r i t h m T h e r ea r em a n ym a t h s sp r o b l e mt h a th a v en o au s a g ea l g o r i t h m T og e tt h e s ep r o b l e m s a n s w e r ，s c i e n t i s t sh a dt og i v eo u ts o m ea p p r o x i m a t ea l g o r i t h mt og e taa p p r o x i a t ea n s w e r F o rt h eO 1 一k n a p s a
9、c kp r o b l e m ，t h eG r e e d ym e t h o d ，w h i c hs e l e c tt h ea r t i c l e sa se x p e n s i v ea si tc a nu n t i li tc a n tc a r r ya n ym o r e ，ist h ef i r s ta p p r o x i m a t ea l g o r i t h m B u ti nt h i sp a p e r ，w es h a lls e et h a ts o m e t i m e st h em e t h o dw i
10、 l lg e tav e r yb a d l ya n s w e r I nt h i sp a p e r ，w eh a ss t u d i e dt h eO l k n a p s a c kp r o b l e mi np r a c t ic ea n di nt h e o r y T h ef 0 1 l o w i n gi st h ec o n c l u s i o n ：l 、T h i sp a p e rg i v eo u ta ni m p r o v e dg r e e d ym e t h o da n dag o o dc o n c l u
11、 s i o n T h ec o n c l u s i o nisat h e o r ya sf o l l o w i n g T h i si st h e0 l k n a p s 8 c kp r o b l e m a t i cd e p i c t i o n ：t h e r ea r ena r t i c l e s ，a n dt h e ya r ec a l l e dl ，2 ，a n dn T h ea r t i c l en u m b e r1w h i c hw e i g h tis仉，v a l u eisc T h ep r o b l e m
12、iso p t i m i z e dm a x z = 叩q s 6 T h eq u a l i f i c a t i o n ：，；1A n dt = 0o rl ，1 蔓f 玎。旦垒人鱼 T H E O R E M ：T ot h eO 1 一k n a p s a c kp r o b l e m ，w ea s s u m e口l口2w ea s s u m ez a st h eb e s ta n s w e r ，z ”： T h eG r e e d yM e t h o d sa n s w e rs t a r tf r o mt h ea r t i c l en
13、u m b e rm ，三8 = m a x z4 ，f = 1 ，2 ，A 靠t h e n ：( 1 ) z 8 z + 2 2 5 。( 2 ) T h et i m ec o m p l e x i t yo ft h ea l g o r i t h mis0 ( n 2 )2 、A n o t h e rm e t h o dw ec a nu s et os 0 1 v et h eO l k n a p s a c kp r o b l e 巾ist h ed i s t r i b u t e dc o m p u t em e t h o d I nt h i sp a p
14、 e r ，t oc o m m u n i c a t ea m o n gm a n yc o m p u t e r s ，w eh a V eu s e dt h eW i n s o c ka n do t h e rt e c h n 0 1 0 9 yi 九t h eW i n d o w sp l a t f O r W et r i e dt h ee n u m e r a t em e t h o da n d t h e D F Si na d i s t r i b u t e de n V i r o n 巾e n t T h ee x p e r i m e n
15、ti n d i c a t e dt h a tw ec a nc l e a r l ya c c e l e r a t et h ee n u m e r a t e 爪e t h o db u tw ec a nn o ta c c e l e r a t et h eD F S 。K E Y W O R D SN Pc o m p l e t ep r o b l e m，O l k n a D s a c kp r o b l e m ， a p p r o x i m a t ea l g o r i t h ，G r e e d ym e t h o d ，d e p t h
16、 f i r s ts e a r c h t i m ec o m p l e x i t y ，w i n s o c k ，d i s t r i b u t e dc o m p u t e ，c o m p u t e rn e t w o r k ，I n t e r n e t ，e s t i m a t eo ft h ea p p r o x i m a t ea n s w e r 。第一章、O ，1 背包问题一，前言在算法研究过程中，有很多有实际背景的重要问题，它们是否有有效的算 法，是计算机科学家们非常感兴趣的问题。1 9 7 1 年库克( s c o o k ) 发表了“T h ec o m p l e x i t yo fT h e o r e mP r o v i n gP r o c e d u r e s ”和1 9 7 2 年卡普( RK a 叩) 发表的“R e d u c i b i l i t y
