织梦模板

VIP

几种背包问题的算法分析与比较

来源:未知 时间:2019-09-07 13:18

摘 要: 背包问题是算法设计分析中的经典问题 ,本文主要通过对回溯法 、动态规划 、贪心算法和遗传算法的研究 ,比较这四种方法在求解背包问题时的优缺点。

关键词:背包问题;回溯法;动态规划;贪心算法;遗传算法
1.问题描述
背包问题 :给定 n种物品和一个背包。物品 i 的重量是 W i,其价值为 V i,背包的容量为 C。应如何选择装入背包的物品 ,使得装入背包中物品的总价值最大 ? 在选择装入背包的物品时 ,对每种物品 i只有两种选择,即装入背包为 1 或不装入背包为 0。不能将物品i装入背包多次 ,也不能只装入部分的物品 i。
2.求解 背包问题的常用算法
1. 回溯法 。
回溯法在包含问题的所有解的解空间树中 ,按照深度优先的策略 ,从根结点出发搜索解空间树 。回溯算法搜索至解空间树的任一结点时 ,总是先判断该结点是否肯定不包含问题的解 。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索 ,逐层向其祖先结点回溯 。否则 ,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根 ,且根结点的所有子树都已被搜索遍才结束 [ 1 ] 。
用回溯法求解背包问题的算法思路 [ 7 ] 是按照物品的单位价值从大到小排序 ,计算当前节点的上界,搜索左子树。只有当右子树包含可行解时才搜索右子树。剪去右子树的条件是当前价值加上剩余物品的总价值小于当前的最优总价值时 ,不需搜索右子树 ,可将右子树剪去。回溯法用一定的剪枝进行优化,算法的时间复杂度为O ( n*2n),n为物品个数 。
2. 动态规划 。
动态规划 ( dynamic programming)是运筹学的一个分支 ,是求解决策过程( decision process)最优化的数学方法 。二十世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程 (multistep decision process)的优化问题时 ,提出了著名的最优化原理( p rinciple of optimality) ,把多阶段过程转化为一系列单阶段问题 ,利用各阶段之间的关系逐个求解,创立了解决这类过程优化问题的新方法———动态规划 [ 6 ] 。
动态规划算法的基本思想是把原问题分解成一系列子问题 ,然后从这些子问题中求出原问题的解。对一个负重能力为 m 的背包 ,如果选择装入一个第 i种物品 ,那么原背包问题就转化为负重能力为 m-w的子背包问题 。动态规划算法的时间复杂度为O ( n*m ),其中n为物体的个数,m为背包负重。
3. 贪心算法 。
贪心算法是一种改进了的分级处理算法 ,根据某个优化目标保证每一步都有局部最优解。贪心算法每次只考虑一步,每一步数据的选取都必须满足局部最优条件 。枚举剩下的数据与当前已经选取的数据组合获得的解中,提取其中能获得最优解的唯一的一个数据,加入结果集合中,直到剩下的数据不能再加入为止。
在求解背包问题时 ,对贪心算法可以使用一些策略,使其得到的解更接近最优解。具体方案如下 :
( 1 ) 价值优先策略 [ 5 ] : 从剩余的物品中 ,选取价值最大的可以装入背包的物品 。此时 ,价值最大的优先被装入背包 ,然后装入下一个价值最大的物品,直到不能再装入剩下的物品为止 。
( 2 ) 重量优先策略 [ 5 ] :从剩余的物品中选取重量最小的物品装入背包中,这种策略一般不能得到最优解 。
( 3 ) 单位价值优先策略 [ 5 ] : 根据价值/重量的比值,按照每次选取剩下的物品中比值最大的物品装入背包 ,直到不能再装入为止。
在贪心算法时间复杂度的估算中,由于需要对重 量或价值或两者的比值进行排序 ,所以贪心算法的时间复杂度为O( n*logn)。
4. 遗传算法 。
遗传算法 ( Genetic A lgorithm )是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型 ,是一种通过模拟自然进化过程搜索最优解的方法 [ 2 ] 。遗传算法的一般步骤 : 确定二进制编码取值范围 ,初始化染色体的个数 ,并随机产生所有的染色体 ,计算个体的适应度 ,经过交叉运算和变异操作,进行遗传迭代求解。
背包问题的遗传算法求解策略 [ 8 ] :
将物品根据单位重量价值从大到小排序 。
用0和1分别表示物品i放入背包和物品i不放入背包 ,如果Xi表示物品i是否放入背包,则 :
放入背包的总重量为
w = w1 * x1 + w2*x2 + ? + wn*xn
放入背包的物品的总价值为
P = p1*x1 + p2*x2 + ? + pn*xn
F[n]存放目标函数值就是个体的适应度,T[n]存放每个个体的约束条件值。
(1)初始种群产生,并计算每个适应度值和其对 应的约束条件值 (即为在染色体中选取的物品的重量) ,比较初始种群中各个个体的适应度。选择最大者所对应的个体作为第一代最优个体 ,并记录该个体以及它的适应度和约束条件值 。
(2)计算每个个体的选择概率Pi = F[i]/∑(F[i] ) 。
(3)根据轮盘赌法进行个体选择 。
(4)进行交叉运算 ,随即选择一对个体产生一对有效交叉位置进行交叉运算 ,并计算新产生的个体的适应度值和约束条件值。如果新产生的个体重量大于背包容量 ,则对新产生的个体进行修正 ,放弃在一个个体中的一个物品 ,增加另一个个体的一个物品使其重量小于背包重量 。
(5)进行变异操作 ,如果一个个体的一个基因为1 ,则变为0;如果是0则变为1 ,重新计算该个体的适应度值和约束条件值。
(6)选取具有最大值的适应度个体,如果其适应度大于当前的最优值的适应度 ,则更新当前的最优值为选取的个体 ,更新当前最优值的约束条件和迭代次数。
(7)循环迭代直到迭代次数超过设定最大值。
算法的时间复杂度为O( T*n2 ) ,其中T为迭代次数,n为种群个数。
3.算法比较
表 1 求解背包问题的算法比较
算法时间复杂度优点缺点改善回溯法O(n*2n )最优解速度慢剪枝动态规划O( n*m)最优解速度慢递归方程求解贪心算法O( n*logn )速度快不一定是最优解启发式方法遗传算法O( T*n2 )近似最优解速度慢,可能造成局部最优解惩罚方法和
译码方法
4.结束语
从计算复杂性理论看,背包问题是一个经典难解问题 。通过对背包问题的几种算法分析可以看出 ,回溯法能够精确地得到问题的最优解 ,可是付出了时间的代价 ; 动态规划算法也可以得到最优解 ,但当 m > 2n 时 ,算法需要 O ( n*2n ) 的计算时间 ,这与回溯法存在着一样的缺点———计算速度慢;采用贪心算法和遗传算法,虽然耗费上优于前者,但不一定能够得到最优解。目前,以上四种方法都广泛地应用到不同的实际问题中,并在应用中不断地根据实际情况改进和完善。
参考文献 :
[1]曾国清. 0-1背包问题的遗传算法求解 [ J ]. 科技信息 ,2006 ( 3 ) : 242 2243.
[2]黄与林. 0-1背包问题的贪心算法 [ J ]. 鄂州大学学报 , 2006 , 13 ( 6 ) : 38240.
[3]林鑫. 基于0-1背包问题的讨论 [ J ]. 微机发展 , 2005 , 15( 10 ) : 41243.
[4]史今驰.背包问题的实用求解算法研究 [ D ]. 济南:山东大学硕士学位论文, 2005.

收缩