文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 0_1背包问题算法分析与研究
侵权投诉

0_1背包问题算法分析与研究

0/1背包问题

研究与开发

变化。

它最初由美国的J.HHolland提出。遗传算法求解问题的过程为:

但是,对于有些问题,这两种算法时间复杂性无法忍受,所以也不可滥用,要根据实际情况进行优化。有时还采用近似算法、严格界限法,目的是为了减少搜索的时间复杂性。

而遗传算法是一种新生算法,它在大型背包问题求解中占有较大的优势,并利于向并行化扩展。

①首先生成一组初群体(假设为M个候选解个体),称为第0代;

②计算群体中各个候选解的适应值;

③如果有候选解满足算法终止条件,算法终止;否则继续④;

3结语

背包问题的研究在理论研究及应用领域都具有

④根据交配概率,将候选解群体中的个体随机两两配对,进行交配操作以生成新的候选解;

十分重要的意义。自20世纪50年代起就有人提出了该问题的解决方法,之后便有更多更好的算法层出不穷。通过以上的分析,我们可以总结:

⑤根据变异概率,对④中生成的候选解群中的每个个体进行变异操作;

⑥使用选择机制形成新一代候选解;转②。遗传算法有着其鲜明的特点:它在处理背包问题时借助了大自然的演化过程,与其他搜索方法的相异:GA不是直接作用在解空间上,而是利用解的某种编码表示;GA从一个群体即多个点而不是一个点开始搜索,这是它能以较大概率找到整体最优解的原因之一;GA只使用解的适应值信息(即目标函数),并在增加收益和减少开销之间进行权衡,而传统搜索算法一般要使用导数等其他辅助信息;GA使用随机转移规则而不是确定性的转移规则。

由此可知GA具有以下优点:适于大规模并行;不受其搜索空间限制条件(如连续、可微、单峰等)的约束;不需要其他辅助信息(如导数);具有较高的准确性。

●分支界限法:适合于问题规模很小,但协同系数改变,问题显得更困难的情况,不足是如果在最差情况下,时间复杂度增大;

●动态规划法:适合于问题规模很小,但协同系数改变,问题显得更困难的情况;缺点是解的状态少;空间消耗大;最好情况和最差情况下一样;

●近似算法:优点是时间消耗少,但损失了问题求解的正确性。

●遗传算法:适于大规模并行;不受其搜索空间限制条件的约束;不需要其他辅助信息;具有较高的准确率且简单、易于操作、通用;缺点是空间消耗大。

参考文献

[1]MichailG.Lagoudakis.The0-1KnapsackProblemAnIn-troductorySurvey.TheCenterforAdvancedComputerStudiesUniversityofSouthwesternLouisiana

[2]Stinson,R.D.AnIntroductiontotheDesignandAnalysisofAlgorithms,Winipeg,Manitoba,Canada

[3]Bellman,R.DynamicProgramming,PrincetonUniversityPress,Princeton,NJ,1957

[4]Kolesar,P.J.ABranchandBoundAlgorithmfortheKnap-sackProblem,inMangementScience13,723~735[5]Lbarra,O.H.&kim,C.E.FastApproximationAlgorithmsfortheKnapsackandSumofSubsetProblem,inJournalofACM22,1975,pp.463~468

[6]Chu,P.C.,&Beasley,J.E.(1998).GeneticAlgorithmfortheMultidimensionalKnapsackProblem.JournalofHeuristics4(1):63~86

[7]王晓东.计算机算法设计与分析.电子工业出版设,2007[8]王乐,王世卿,张静乐.基于MatLab的0-1背包问题的动

态规划方法求解[J].计算机技术与发展,2006(04)

2.2算法性能分析与比较

在解决实际情况时,我们必须分清楚各种策略的适用条件和相互间的联系区别,在考虑问题时才能够正确地选择算法策略。其中,最常用的算法策略应该是分支界限贪心算法和动态规划法这两种算法,它们在许多情况下可以在合理的时间内找到问题的最优解。

在大型背包问题上,分支界限法较动态规划法有效。一般来说,当pi与wi各自独立时,问题较简单,但当它们之间的协同系数改变时,问题将变得更困难。将复杂问题结构化的问题已有人进行,HungandRom研究了pi和wi间约束条件不定的一种情况,该情况下分支约束法的时耗为问题规模m的指数级。同时他们证明问题的难度不依赖于分支界限算法的约束机制。计算机测试表明即使在问题规模很小的情况下,该问题仍很难解,此情况下,动态规划法则优于分支界限法。

现代计算机(总第三

○

[9]王会颖,贾瑞玉,章义刚,齐平.一种求解0-1背包问题的

快速蚁群算法[J].计算机技术与发展,2007(01)

ODERNCTER2009.6

趹趦

九

期)

上一页第3页

你可能喜欢

  • 背包问题
  • 动态规划
  • 遗传算法
  • 动态问题
  • 贪心算法
  • 背包九讲
  • 最速下降法

热门文档

相关文档

  • 0-1背包问题算法分析与研究

    兰O1一 背包 问题 算法分 析 与研 究周 斌 ,张 莹 ,黄志军 (.南 民族大学 ,汉407 1中武304;2华 中科 学技术大学,汉407 .武304) // 摘 要:0/ ...

  • 0-1背包问题算法分析与研究

    0-1背包问题算法分析与研究_自然科学_专业资料。0-1背包问题算法分析与研究竺兰竺O一1背包问题算法分析与研究周 斌1 ,张莹2 ,,/ ,黄志军1 (1.中南民族...

  • 关于0_1背包问题的算法研究

    1 背包问题的算法研究李北斗 (中国地质大学信息工程学院 武汉 430074) 摘 0 /...下面对动态规划的算法进行一下相应的算法 分析 , 首先是时间复杂度 , 从上面...

  • 0_1背包问题之穷举_搜索_动态规划算法探讨

    +86-551-5690963 5690964 0-1 背包问题之穷举、搜索、动态规划算法探讨曹周进(...算法分析:为了得到能放进背包物品的最大总价值。 我们可以在 n 种物 品中,...

  • 求解0_1背包问题的算法综述

    并在 背包算法的时间复杂 , 度和空间复 杂度 两发面进行 简要 分析 关键 词...研究 表 明该 算 法具有 许 多优 良的性 质〔〕针对 0 优化设 计问题 ...

  • 0_1背包问题动态规划算法的探讨

    实践与经验 0/1 背包问题动态规划算法的探讨孙建中( 中国地质大学 (武汉 ) 信息工程学院, 武汉 430074)要: 0/1 背包问题是运筹学中的著名问题, 有重要的使用...

  • 0_1背包问题四种解法

    eduf@cccc.net.cn 0/1 背包问题及其解法研究黄波,蔡之华 (中国地质大学计算机...方法的基本原理,提出了求解 0/1 背包问题的算法思想,并对算法进行分析, 提出...

  • 求解0-1背包问题算法综述

    0-1背包问题 6页 免费 算法设计与分析实验报告... 6页 免费...研究多阶段 决策过程的优化问题时提出的,把多阶段决策过程转化为一系 列单阶段...

  • 0-1背包问题研究及算法策略比较分析

    0-1背包问题研究及算法策略比较分析_理学_高等教育_教育专区。0-1背包问题研究及算法策略比较分析成绩 数学与物理科学学院《算法分析与设计》课程考查论文 题专班...

  • 背包问题的算法设计与分析研究

    背包问题的算法设计与分析研究 答案是否定的, 还以上面的实例说明, 采用贪婪法求的解向量为( 1,0,0), 最大价值为 60, 很明显 ,(0,0,1)优于前者,最大...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email