算法分析与设计课程设计论文01背包问题研究及算法策略比较分析.docx

数学与物理科学学院算法分析与设计课程考查论文题目0-1背包问题研究及算法策略比较分析专业班级学号姓名任课教师完成日期2011/5/24摘要背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用回溯法对背包问题、OT背包问题及简单o-i背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决OT背包问题对这四种算法进行详细的比较，总结这种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。一、绪论1.1 问题的研究及意义0-1背包问题是计算机科学中的一个非常经典的优化问题。它的主要思路是假定某人拥有大量物品，重量各不同。通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。围绕这个问题的求解方法很多，比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见的一种求解方法。多年来，背包问题吸引了许多理论和实际工作者对此问题作深入的研究，在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。1.2 0-1背包问题的算法研究与分析0-1背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关问题的尽可能高效的算法并程序实现，而且能够分析算法的复杂性，通过实验进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高算法设计与分析的应用能力。OT背包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高的理论研究价值，而且由于它是许多实际工程应用问题的种通用化描述，在很多实际问题当中有着非常广泛的应用背景，例如项目决策等。他是最基本的背包问题，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的情况。它包含了背包问题中设计状态、方程的最基本思想,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。在计算理论中属于NP-C完全问题，其计算复杂度，传统上采用动态规划来求解。背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。L3课题的主要研究内容问题的一般描述是：旅行者背包登山，背包的最大承重为M,现有n个物品可供选择装入背包，第i个物品莺量为wi,价值为pi,假定物品i的一部分xi(Oxil)放人背包，获得价值为xipi,由于背包最大承重为M,要求装入物品总质量不过超过M,问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。背包问题的数学描述如下：要求找到一个n元向量(xl,x2-n),在满足约束条件：<Z七",”情况下，使得目标函数maxZQ,其中，lin;M>0；Owl''wi>0；pi>0o满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解O给定11种物品和1个背包。物品i的重量是Wi,其价值为pi,背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i装人背包多次，也不能只装入部分的物品io该问题称为0-1背包问题。OT背包问题的符号化表示是，给定M>0,Wi>0,pi>0,lin,要求找到一个n元OT向量向量(xl,x2xn),Xi=O或1,lin,使得ZXMM,而且Zy达到最大。二、0-1背包问题在动态规划中的实现2.1 动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下：分析最优解的结构：最有子结构性质；建立递归方程；计算最优值；构造最优解。2.2 0-1背包问题的实现最优子结构性质OT背包问题具有最优子结构性质。设(yl,y2yn)是所给OT背包问题的一个最优解，则(y2,y3yn)是下面相应子问题的一个最优解：nk=i< h7jJk=ixk0,l,z<k<n因若不然，设(z2,z3Zn)是上述问题的一个最优解，而(y2,y3yn)不是它的最优解，由此可见之>£匕,且wlyl+£吗2,c0因此i=2i=2z=2viyi+v.2.>Z匕i=2z=lwlyl+wzzzcz=2这说明(yl,z2Zn)是所给OT背包问题的一个更优解，从而(yl,y2yn)不是所给OT背包问题的最优解。此为矛盾。递归关系设所给0-1背包问题的子问题nmaxk=i'n< EMXkWjk=jxk0,l,zkn的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为Li+l,n时0-1背包问题的最优值。由OT背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下:maxm(z+1),7),m(+1,7-wz)+vz,7wim(,j)m(+1,7),07<jvnjwm(n,j)=.0j<wn算法描述基于以上讨论，当wi(lin)为正整数时，用二维数组m来存储m(i,j)的相应值，可设计解OT背包问题的动态规划算法Knapsack入下：template<classType>voidKnapsack(Typev,intw,intc,intn,Type*m)intjMax=min(wn-l,c);for(intj=0;j<=jMax;j+)mnj=0;for(intj=wn;j<=c;j+)mnj=vn;for(inti=11-l;i>l;i-)jMax=min(wi-l,c);for(intj=0;j<=jMax;j+)mij=mi+lj;for(intj=wi;j<=c;j+)mij=max(mi+lj,mi+lj-wi+vi);mlc=m2c;if(c>=wl)mlc=max(mlc,m2c-wl+vl);)template<classType>voidTraCebaCk(Type*m,intw,intc,intn,intx)for(inti=l;i<=n;i+)if(mic=mi+lc)xi=0;elsexi=1;c-=wi;xn=(mnc)?l:0;计算复杂性分析利用动态规划求解OT背包问题的复杂度为0(minnc,2n)。动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题。三、0-1背包问题在分枝-限界法中的实现3.1 分枝-限界法的基本原理与分析分枝限界发是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-结点(expansionnode)的扩充方式。每个活结点有且仅有一次会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出(最优)可行解的结点，其余结点加人活结点表,然后从表中选择一个结点作为下一个E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。有两种常用的方法可用来选择下一个E-结点：先进先出(FIFO)即从活结点表中取出结点的顺序与加人结点的顺序相同，因此活结点表的性质与队列相同。最小耗费或最大收益法在这种模式中，每个结点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活结点表可以最小堆来建立，下一个E-结点就是具有最小耗费的活结点，如果希望搜索一个具有最大收益的解，则可用最大堆来构造活结点表，下一个E-结点是具有最大收益的活结点由。3.2 0-1背包问题的实现0-1背包问题的最大收益分枝定界算法可以使用定界函数来计算活结点的收益上限Upprofit,使得以活结点为根的子树中的任一结点的收益值都不可能超过UPPrOfit,活结点的最大堆使用UPPrOfit作为关键值域。在子集树中执行最大收益分枝定界搜索的函数首先初始化活结点的最大堆，并使用一个数组bestx来记录最优解。由于需要不断地利用收益密度来排序，物品的索引值会随之变化，因此必须将函数所生成的结果映射回初始时的物品索引。函数中的循环首先检验E-结点左孩子的可行性，如它是可行的，则将它加入子集树及活结点队列(即最大堆)，仅当结点右子树的定界值指明可能找到一个最优解时才将右孩子加入子集树和队列中。则主要算法描述为：classObjectfriendintKnapsack(int*,int*,int,int,int*);public:intoperator<=(Objecta)constreturn(d>=a.d);private:intID;floatd;单位重量价值)；template<classTypew,classTypep>classKnap;classbbnodefriendKnap<int,int>friendintKnapsack(int*,int*,int,int,int*);private:bbnodearent;/指向父结点的指针boolLChild;/左儿子结点标志)；template<classTypew,classTypep>classHeapNodefriendKnap<Typew,Typep>public:operatorTypep()constreturnuprofit;private:Typepuprofit,/结点的价值上界profit;/结点所相应的价值Typewweight;结点所相应的重量intlevel