资源描述：
《求解0_1背包问题的算法综述.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第卷增刊黑龙江大学自然科学学报4678.9::;<7:=6:?,卫!∀年#∃月%&∋()∗+&,)∗−∋(∗+./01)/1&,210+&)3%0∗)3∋)041(.0−56>《≅】∀求解&Α#背包问题的算法综述,苏中,姜宇滨郑萍,东北农业大学工程学院哈尔滨#Β∃Χ∃!,Δ&Α#)Ε一Φ摘要背包问题是实际当中经常遇到的一类经典
2、间复杂关键词∃Α背包问题算法度ΔΔΔ一一一中图分类号−刃∀#文献标志码∗文章编号#∃∃#Ι∃##∃∃∀!.!∃∃∀∃Χ∃前言。,:背包问题是在#∀Ιϑ年由Κ?Λ:7和2:7Μ<Ν提出的它的主要思路是假定某人拥有大量物品重量各不。。,同此人通过秘密地选择一部分物品并将它们放到背包中来加密消息背包中的物品中重量是公开的所,。,,有可能的物品也是公开的但背包中的物品是保密的附加一定的限制条件给出重量而要列出可能的物,。,,。品在计算上是不可实现的背包问题是熟知的不可计算问题背包体制以其加密解密速度快而其人注目,算法∗7ΟΠ?;=ΦΜ!是一系列解决问题的清晰指令一个算法的优劣可以用
3、空间复杂度与时间复杂度来衡。量川算。法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤或者看成按照要求设计好的,。,有限的确切的计算序列并且这样的步骤和序列可以解决一类问题本文选择其中适用的几种算法对∃Α7,。背包问题的求解方法进行分类介绍并对各种算法的复杂度进行分析#求解方法分类。,,背包问题是算法设计分析中的经典问题目前随着计算机算法的不断发展涌现出大量可用于解决∃,。一Δ#背包问题的算法和思想背包问题的建模与求解有着广泛的应用前景其求解方法主要有三类第一,、,回溯一Η类是精确方法如动态规划法和分枝限界法等第二类是近似方法启发式算法!如贪心算法,,、Ρ:ΓΘ∗7Ο
4、6?;=ΦΜ!Η第三类是全局优化方法如遗传算法3:Ν:=;:∗7Ο6?;=ΦΜ3∗!蚁群算法∗Ν=/676ΝΘ∗03?:,、,。Ο6?;=ΦΜ∗/∗!遗传退火进化算法::Ν:=;/∗ΝΝ:欲;ΝΟ1Σ67Π=;6Ν∗一即“=ΦΜ3∗1∗!〔’%下面将针对这三娜等。类求解方法进行分析和比较精确方法8#动态规划法ΓΘΝ<Μ;Τ9?6Ο?<ΜΜ;ΝΟ!,Δ动态规划算法的基本思想把目标问题分解为若干个可解决或可以再分解的子问题通过对这些子问题,。,的求解进而得到目标问题的解动态规划法是采用最优子结构从下到上的方法从不可再分的子问题中得,。,到最优解来逐步构造出整个目标问题的解在构造
5、解的过程中可能会得到一系列的解但有些解可能会耗,。时过长或过分占用系统资源还需要针对可能解进行筛选来得到最优解动态规划算法每一步的状态参数Δ∃一一收稿日期∃∀∃Υ8,,,,Δ一!硕士研究生主要研究方向Δ1一ΜΔςΦΠ<;;<ΝΟΘΠΞς;Ν<Τ作者简介姜宇#∀ϑΒ男计算机科学与技术司ς:Ω6Μ8Δ#∀Β一,,,1一Μ<ΔςΠΨ/6Μ通讯作者苏中滨!男教授;7>以!7Ξ#ΧΔ增刊姜宇等求解∃Α7背包问题的算法综述,“”。,是通过调用上一步的状态参数来设置的也可以说上一步的状态参数对将来是未知的也就是说从初,,,始状态到最终状态将经过多个过程每个过程对应不同的状态不断地调
6、用上一步状态来决策下一状态从而,,。得到一个决策序列最终得到目标问题的解这些都是典型的多段决策的特性,,通过对动态规划算法的介绍当设计&Α7背包问题的解决方案时将整个物品放到背包中这一过程可以。Ν被看成是将物品分块后尽可能多的将物品放人背包中这一问题的求解假设目标问题被分解成个子问,,,,题每一个不可再分的子问题最多需要Μ次决策那么求解过程中的计算频率为ΜΝ回溯的频率为Ν则动。态规划算法的时间复杂度为&ΜΝ!8回溯法><:Λ=?<:Λ;ΝΟ!,,回溯法的基本思想是Δ首先应确定解空间其次建立解空间树再用深度优先搜索算法递归遍历解空间树,同,,时将不符合条件的树枝剪掉一旦定义了
7、解空间的组织方法这个空间即可按照深度优先的方法从开,。始结点进行搜索利用限界函数避免移动到不可能产生解的子空间,,,。回溯其实是一种择优算法在择优范围确定的条件下不断向前搜索所有节点解为叶子节点当搜索,。到某一回溯点时发现此回溯点并不优或不符合条件时则向后回溯到该子树的根节点当发现此回溯点符,,。,回溯合择优条件时则进人该子树继续以深度优先搜索算法递归遍历该子树换句话说法就是在规定的,。,范围内穷举所有的解找出解中最优的值在利用回溯法求解目标问题的过程中何时剪枝这一问题显得至。回溯,,。关重
