计算机算法设计与分析.DOC

1、 计算机算法设计与分析 0/1 背包问题研究报告 目 录 1. 问题的定义 . 1 2. 问题的应用背景 . 1 3. 求解 0/1 背包问题的常用算 法 . 2 3.1 遗传算法 . 2 3.2 模拟退火算法 . 3 3.3 蚁群算法 . 3 3.4 贪心算法 . 4 3.5 动态规划法 . 5 3.6 回溯法 . 6 3.6.1 算法描述 . 6 3.6.2 算法设计基本思想 . 6 3.6.3 实例分析 . 7 3.6.4 程序代码及实验结果 . 7 3.7 分支限界法 .10 3.7.1 算法描述 .10 3.7.2 算法设计基本思想 .10 3.7.3 算法求解过程 . 11 3.7

2、.4 分支限界法求解 0/1 背包问题 . 11 3.7.5 程序代码及实验结果 .13 4. 常用几种算法比较 .18 5. 展望 .19 1 0/1背包问题 及其 求解 算法研究 背包问题（ Knapsack Problem, KP） 又称为子集合问题，最早由 Dantzing 于 20 世纪 50 年代提出， 是计算机算法中的一 类 经典问题，也是运筹学 中的一类经典的 NP 完全 组合优化问题，在资金分配、货物装载 、项目选择等问题上有着广泛的应用。根据 物品特性及约束条件的不同， KP 问题可分为 0/1 背包问题和多背包问题两大类 ， 前者又可依据维数的不同，进一步分为一维 0/1

3、 背包问题、二维 0/1 背包问题及多维0/1 背包问题 。本文主要研究简单的 0/1 背包问题，即一维 0/1 背包问题。 1. 问题的定义 给定 n 种 重量为 wi ，价值为 pi 的 物品 Wi（ i=1, 2,., n） 和 1 个 容量为 c 的 背包，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 在选择装入背包的物品时 ，对每种物品 Wi 只有两种选择，即 装入 背包或不装入背包。不能将物品 Wi装入背包多次，也不能只装入部分的物品 Wi。因此，该问题称为 0/1 背包问题。 此问题更形式化的描述为：给定 c0， wi0， pi0， i=1, 2,., n，要求

4、找出一个 n 元 0/1 向量 (x1, x2, , xi, , xn)， xi 0,1， i=1, 2,., n， 使得 cxwni ii 1，且 ni ii xp1达到最大。 因此， 0/1 背包问题是一个特殊的整数规划问题 ，其数学模型表示如下 ： Maxni iixp1s.t. ,1,1,01 nixcxwini ii2. 问题的应用背景 0/1 背包问题是当前组合优化领域研究的一个热点和难点问题，其实质就是组合优化问题，即如何在有效的空间内装载更多的物品，实现背包中物品价值的最大化。 0/1 背包问题是一个 特殊的整数规划问题 ， 其 最终 目标 是 寻 求一种最优的分配策略以 获得

5、物品 最大的价值量 。形象化说， 给出一系列可以进行的操作 P， 每种操作都可以获得相应的价值 V， 但是进行每一种操作都必须付出相应的代价 C， 然后求 出 在总代价不超过 给定阈值 时可以获取的最大价值。 0/1 背包问题在 现实 生活 中 有着广泛的应用，如下料问题、贷款组合优化问题、项目选择问题等 都可以转换为 0/1 背包问题，即这些问题都可以转换为 整数线性规划问题。因此，研究 0/1 背包问题高效求解算法，无论是在理论上还是在实际 应用中都具有一定的价值和意义。 2 3. 求解 0/1 背包问题的常用算法 目前，求解 0/1 背包问题的算法主要有确定性算法和 近似 算法两大类，确

6、定性算法有分支限界法、动态规划法 、回 溯法 等； 近似 算法有贪心算法、遗传算法 、蚁群算法 等。一般来讲，确定性算法只能在短时间内求解小规模的 0/1 背包问题，而不能快速地求解大规模的 0/1 背包问题，因此其实用性常常受到问题规模的限制；而 近似 算法往往只能求解问题的近似解，有时所求得的解的质量不如人意。 本节首先对求解0/1 背包问题的常用算法进行简要的阐述，然后重点对回溯法 和分支限界法 求解一维 0/1 背包问题 进行着重分析，并用 Java 语言在 MyEclipse8.0 平台下编程实现。 3.1 遗传算法 遗传算法（ Genetic Algorithms, GAs） 是由

7、 John H. Holland 及其学生于 20 世纪 60 年代末 70 年代初提出 的 一种通过模拟生物进化和遗传选择过程来搜索最优解的智能优化方法。 基本 GAs 算法的步骤一般为：确定编码方式及取值范围；初始化染色体的个数，并随机产生所有的染色体；计算个体的适应度；经过遗传算子操作，进行遗传迭代求解。 0/1 背包问题的遗传算法求解策略如下： 将物品 Wi 按单位重量价值（ pi /wi）由大到小排序； 依据 0/1 背包问题的定义（见第 1 节），则放入背包的总重量为 w=ni iixw1，总价值为 p=ni iixp1； fn存放目标函数值，即个体的适应度， tn存放每个个体的约

8、束条件值。 (1) 产生 初始种群，并计算每个 个体的 适应度值和其对应的约束条件值（即为在染色体中选取的物品的重量），比较初始种群中各个个体的适应度。选择最大者所对应的个体作为第一代最优个体，并记录该个体以及它的适应度和约束条件值 ； (2) 计算每个个体的选择概率 nii ififP 1 /； (3) 利用轮盘赌法进行个体选择； (4) 进行交叉运算，随即选择一对个体产生一对有效交叉位置进行交 叉运算，并计算新产生的个体的适应度值和约束条件值。如果新产生的个体重量大于背包容量，则对新产生的个体进行修正，放弃在一个个体中的一个物品，增加另一个个体的一个物品使其重量小于背包重量 ； (5) 进

9、行变异操作，如果一个个体的一个基因为 1，则变为 0；如果是 0 则变为 1，重新计算该个体的适应度值和约束条件值 ； (6) 选取具有最大值的适应度个体，如果其适应度大于当前的最优值的适应度，则更新当前的最优值为选取的个体，更新当前最优值的约束条件和迭代次数 ； (7) 循环迭代直到迭代次数超过设定最大值。 分析可知， 算法的时 间复杂度为 O(t*n2)， 其中 t 为迭代次数， n 为种群大小。 在众多 近似算法中，遗传算法是 求解 0/1 背包问题的一个较好算法： 在求解 0/1 背包问题时，由于遗传算法的进化特性， 使得 它在解的搜索 过程 中不需要了解 0/1 背包问题的内在性质，

10、遗传算法可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的，甚至是混合的搜索空 间 ； 遗传算法在选择、交叉和变异的过程中，都存在对每一个体进行处理的可能 。 若遗传算法每一代对群 体规模为 n 的个体进行操作，实际上处理了大约 O(n3)个模式，具有很高的并行性，因 而具有显著的搜索效率 ； 遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的 近似 ，从而保证算法的有效性 ； 遗传算法的基本思想简单，运行和实现步骤规范，便于具体使用 。 3 3.2 模拟退火算法 模拟退火 （ Simulated Annealing, SA） 算法 是一种随机 的全局

11、寻优算法，其思想源于物理退火过程与组合优化问题之间的相似性，最早由 Metropolis 于 1953 年提出， 1983 年 Kirkpatrick 等将其应用于组合优化问题。 模拟退火算法求解 0/1 背包问题的过程如下： (1) 解空间 1,0)(,)()(|)(. . . ,),2(),1( 1 ixcixiwnxxxS ni (2) 目标函数 Max ni iixpf 1s.t. ,1,1,01 nixcxwini ii(3) 产生新解 随机选取物品 Wi，若 Wi 不在背包中 ， 则将其直接放入背包中，或同时从背包中随机取出另一物品Wj；若 Wi 已在背包中，则将其取出，并同时随机

12、装入另一物品 Wj。 (4) 背包的价值差和重量差 根据上述新解产生的 3 种可能，相应的背包价值差为： 取出装入背包且将将物品取出装入背包且将将物品直接转入背包将物品ijjiiWWicjcWWjcicWicp)()()()()( 相应的背包重量差为： 取出装入背包且将将物品取出装入背包且将将物品直接转入背包将物品ijjiiWWiwjwWWjwiwWiww)()()()()( 其中 w 为当前状态下背包重量 w 的增量。 (5) 接受准则 由于 0/l 背包问题是个有约束的最优化问题，所以通常采用扩充的 Metropolis 准则 .),/e x p (.0,1.,0e l s etffcww

13、cwwP 且 其中 t 为温度控制参数。 在算法实现过程中，其退火温度 t 控制着求解过程向最小值的优化方向进行，同时又以概率 P 来接收劣质解，因此模拟退火算法可以跳出局部极小值点。只要初始温度足够高、退火过程足够慢，算法就能收敛到全局最优解。 3.3 蚁群算法 蚁群算法 是 由 Dorigo M.等人 依据 模仿真实的蚁群 行为而提出的一种模拟进化算法。蚂蚁之间是通过4 一种称为信息素（ Pheromone） 的物质传递信息的，蚂蚁能够在经过的路径上留下该种物质，而且能够感知这种物质的存在及其强度，并以此来指导自己的运动方向。因此，由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象：某一条

14、路径上走过的蚂蚁越多，该路径上留下的信息素就越多，则后来者选择该路径的概率就越大。蚂蚁之间就是通过这种信息素的交流，搜索到一条从蚁巢到食物源的最短路径。将这一问题的核心思想运用到 0/1 背包问题求解中即是，在某一物品上聚集的信息素越多，则该物品被选择的 概率就越大。就蚁群算法而言，当处理的数据比较小时，其具有很快的收敛速度，而随着数据规模的增大，算法的收敛速度明显降低。 假设有 m 只蚂蚁， n+1 个城市，第 0 个城市代表背包，第 1n 个城市代表各个物品，把第 0 个城市看作 蚂蚁的寻优起点。令 nij=pi/wi 表示蚂蚁从城市 i 转移到城市 j 的期望程度，这样价值越高同时重量越

15、小的物品对蚂蚁的吸引就越大。令 ij表 示路径中留下的信息素强度任 ， 任 一只蚂蚁 k 由城市 i 转移到城市 j 的概率可设为： ,1,0,1njinnPnj ijijijijkij 其中 表示 路径上的信息量对蚂蚁选择路径 所起的作用 大小， 为吸引度的重要性。每只蚂蚁从寻优起点出发只需一步就可到达 1n 当中任意一个食物源，所以上式中有 (i=1, 2,., n)。寻优过程由多只蚂蚁进行，当每只蚂蚁以较大的概率选中食物源 i 时 ， 如果有 01 ni ii xwc， 则变量 xi 将加 1； 否则给从 i 到 j 的路径以罚值，以使后续的蚂蚁不再选择本路径。当所有节点都受罚以后将结束

16、一次求解过程 ， 然后记录最优解，更新信息素。更新的公式可为： 2,1,0,)(*)1()1( * jitt xwk ijijij jjij 上式中 k 为 正常数， 为挥发 系数， xj 为经过该 路径的蚂蚁数量。 蚁群算法求解 0/l 背包问题的过程如下 ： (1) 初始化 ： 即将任意两个城市之间的道路上的信息素赋一个初值； (2) 搜索 ： 让若干只蚂蚁根据信息素和距离选择城市； (3) 每到一个新城市进行信息素局部更新； (4) 所有蚂蚁完成回路后进行全局信息素更新； (5) 记录最优路径，返回步骤 (2)循环直到满足退出条件。 蚁群算法是近年来发展起来的一种随机算法，已经证明可以有

17、效解决背包问题。但是蚁群算法的收敛性证明尚处于初步阶段，缺乏完善的理论基础 ， 并且在减少寻优计算量和缩短算法运行时间方面，有待进一步改进。 3.4 贪心算法 贪心算 法 （ Greedy Algorithm, GA） 是一种改进了的分级处理算法，根据某个优化目标保证每一步都有局部最优解。贪心算法是从局部最优出发，最终得到整体最优。贪心算法每次只考虑一步，每一步数据的选取都必须满足局部最优条件。枚举剩下的数据与当前已经选取的数据组合获得的解中，提取其中能获得最优解的唯一的一个 数据，加入结果集合中，直到剩下的数据不能再加入 为止。 用 贪心法求解问题 时 应 考虑如下几个方面： (1) 候选集

18、合 P： 为了构造问题的解决方案 ，假设 有一个候选集合 P 可以 作为问题的可能解 ， 即问题的最终解均取自于候选 集合 P； 5 (2) 解集合 S： 随着贪心选择的进行 ， 解集合 S 不断扩展 ， 直到构成一个满足问题的完整解 ； (3) 解决函数 ： 检查解集合 S 是否构成问题的完整解 ； (4) 选择函数 ： 即贪心策略 ， 这是贪心法的关键 。 它指出哪个候选对象最有希望构成问题的解 ， 选择函数通常和目标函数有关 ； (5) 可行函数 ： 检查解集合 S 中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。 具体来说， 在求解 0/1 背包问题时，对贪心算法可以使用

19、如下三种 策略， 以 使其得到的解更接近最优解。具体方案如下： (1) 价值优先策略：从剩余的物品中选取 价值最大的可以装入背包的物品。此时，价值最大的优先被装入背包，然后装入下一个价值最大的物品，直到不能再装入剩下的物品为止。 (2) 重量优先策略：从剩余的物品中选取重量最小的物品装入背包中，这种策略一般不能得到最优解。 (3) 单位价值优先策略：根据价值重量的比值，按照每一次选取剩下的物品中比值最大的物品装入背包，直到不能再装入为止。 上述 三种策略都不能保证得到最优解 ， 但三种策略相比较而言，第三种策略与最优解相差较小。如果可以选择物品的一部分，用单位价值策略可以保证得到 问题的 最优

20、解。 在贪 心算法时间复杂度 的估算中，由于需要对 重量或价值或两者的比值进行排序，所以贪心算法的时间复杂度为 O(n*logn)， n 为物品数量 。 3.5 动态规划法 动态规划 （ Dynamic Programming, DP） 属于 运筹学 范畴 ，是 一种 求解 决策过程 最优化的数学方法 ， 20世纪 50 年代初 由 R. E. Bellman 等人在研究 多阶段决策过程 的优化问题时提出 ， 把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法 动态规划 法 。 动态规划算法是先把问题分成多个子问题（一般地 ， 每个子问题 都 是互相关联和影响的）

21、，再依 次研究逐个问题的决策 。 决策就是某个阶段的状态确定后，从该状态演变到下一阶段状态的选择。当全体子问题都解决时，整体问题也随之解决。用枚举的方法从所有可能的决策序列中去选取最优决策序列可能是较费时的笨拙方法，但利用最优性原理去找出递推关 系，再找最优决策序列就可能使得枚举数量大大下降，这就是动态规划方法设计算法的主要思路。 动态规划 法求解 0/1 背包问题的过程如下 ： (1) 将原问题 分解为若干个子问题（一般每个子问题是相互关联和影响的），再依次逐个研究问题的决策，也就是把整个问题的最优解与子问题的局部最优解用递推等 式联系起来； (2) 定义边界条件； (3) 把边界条件代入递

22、推公式，逐步求得最优解。 其数学描述为：设 fk(ww)代表背包只装入前 k 种物品，总重量不超过 ww 的情况下所具有的最大价值，即： fk(ww)=Maxwwi iixp1， 0wwn s.t. wwxwki ii 1， 0wwc 这两个式子分别为 0/1 背包问题子问题的目标函数和约束条件，不难看出其是满足优化原则的。当使用 DP 算法求解 0/1 背包问题时，可以推导出其递推公式和边界条件： 递推公式： fk(ww)=Max (fk-1(ww), f(ww-wk)+pk)， 6 边界条件： 1110)/(,0,0,0,0pwwwwwfnkwwwwfcwwwwwwfk分析可知， 动态规划

23、算法 的 时间复杂度为 O(n*c)， n 为物品个数， c 为背包容量。 动态规划算法是一种经典的 0/1 背包问题求解算法，其原理简单 、 思路清晰 、 易于实现 ， 但 对于 较大规模的问题 ， 它并不是一个理想的算法，最重要的原因就是它的维数障碍，即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系。这样惊人的增长速度是计 算机难以承受的，这就使得 独立使用 动态规划方法求解规 模 较大的背包问题发生了困难，且目前尚没有好的解决办法。 3.6 回溯法 3.6.1 算法描述 回溯法（ Backtracking Algorithm, BA）有“通用的解题法” 之称，用它可以

24、系统地搜索一个问题的所有解或任一解，是一个既带有系统性又带有跳跃性的搜索算法。在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按 照深度优先的策略进行搜索。 BA 在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而 BA 在用来求问题的任一解时，只要搜索到问题的一个解即可结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。 3.6

25、.2 算法设计基本思想 在对回溯法的描述过程中，已给出了算法设计的基本思想，于此，只是精炼提出算法的思想。 搜索：回溯法从根结点出发，按深度优先策略遍历解空间树，搜索满足约束条件的解。 剪枝：在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约 束条件，或者是否超出目标函数的界 ； 也即判断该结点是否包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即剪枝（ Pruning）；否则，进入以该结点为根的子树，继续按照深度优先 的 策略搜索。 一般来 讲，回溯法求解问题的基本步骤如下： (1) 针对所给问题，定义问题的解空间； (2) 确定易于搜索的解空间结构； (3) 以深度

26、优先方式搜索解空间，并在搜索过程中利用 Pruning 函数剪去无效的搜索。 具体到 0/1 背包问题，回溯法求解过程 为 ： (1) 根据 0/1 背包问题的数学描述，其解空间向量可表示为 (x1, x2, , xi, , xn)， xi 0,1。 xi=0 表示物品未放入背包中， xi=1 表示物品已放入背包中。 (2) 在定义了解空间后，还应将解空间很好地组织起来，以便可用回溯法搜索整个解空间，通常，我们将解空间组织成树或图的形式。 (3) 在确定了解空间的组织结构后，回溯法就从开始结点（ 根结点 ） 出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩

27、展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成 为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动， 则当前的扩展结点就成为死结点，即这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即是以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。 7 3.6.3 实例分析 考虑下面的具体实例： 3 个物品的重量 w=20, 15, 10，价值 p=20, 30, 25，背包容量 c=25。 对于 n=3的 0/1 背包问题， 其解空间树是一个完全二叉树，如

28、图 1 所示。 ABCD EH I J KF GL M N O101 01 0 1 01 01 01 0图 1 n=3 时， 0/1 背包树的解空间树 我们从图 1 的根结点 A 处开始搜索其解空间。 具体 搜索过程 （如图 2 所示） ：开始时 ， 根结点是唯一的活结点，也是当前的扩展结点。在这个扩展结点处，我们可以沿 纵深方向移至结点 B 或结点 C 处。假设我们选择先移至结点 B 处，此时结点 A 和结点 B 都是活结点，结点 B 成为当前的扩展结点。由于选取了w1=20，故在结点 B 处剩余背包容量 r=25-20=5，获取的价值 p=20。从结点 B 处，我们可以移至结点 D 或E。

29、由于移至结点 D 至少需要 w2=15 的背包容量 ，而此时背包仅有的剩余容量 r=5，故移至结点 D 导致一个不可行解 （见图 2 中深色标记） ，利用剪枝策略剪去该枝 。而搜索至结点 E 不需要背包容量，因而是可行的 ， 从而我们选择移至结点 E。此时，结点 E 成为新的扩展结点，结点 A、 B 和 E 是活结点。在结点 E处， r=5， p=20。从结点 E 处，可以沿纵深方向移至结点 J 或 K。移至结点 J 导致一个不可行解 （见图 2中深色标记） ，而移向结点 K 时是可行的，于是移至结点 K 而剪去结点 J 那枝 。此时，结点 K 成为一个新的扩展结点。由于结点 K 是一个叶结点

30、，故我们得到一个可行解，这个解 的 相应的价值为 p=20。 xi 的取值由根结点 A 到叶结点 K 的路径所唯一确定，即 x=(1, 0, 0)。由于在结点 K 处已不能再向纵深扩展，所以结点 K 成为了死结点，我们返回到结点 E 处，此时结点 E 也没可扩展的结点，即结点 E 也成了死结点。以此回溯，直至根结点 A 再次成为当前的扩展结点， 然后， 沿右子树 的 纵深方向移动，直至遍历整个解空间。算法搜索得到 的 最优值为 55，相应的最优解是从根结点 A 到结点 L 的路径 (0, 1, 1)， 即是相应 0/1 背包问题的最优解。程序验证结果如图 3 所示。ABCD EJ KF GL

31、M N O101 01 0 1 01 01 0P = 2 0 P = 5 5 P = 3 0 P = 2 5 P = 0图 2 n=3 时 ， 回溯法 求解 0/1 背包问题 搜索过程 图 3 回溯法求解算例结果 分析可知，回溯法 利用一定的剪枝策略 求解 0/1 背包问题 ，算法 的时间复杂度为 O(n*2n)， n 为物品的数量。 3.6.4 程序代码及 实验结果 依据上节对 n=3 时 0/1 背包问题搜索过程的分析 ，按照 重量优先策略 设计如下程序，并用两个算例进行验证。 8 3.6.4.1 程序代码 package CADA;/计算机算法设计与分析 (Computer Algori

32、thm Design /物品价值 private doublew;/物品重量 private int n;/物品数 private double c;/背包容量 private double bestp;/当前最优价值 private double cp;/当前价值 private double cw;/当前重量 private int x;/记录可选物品的重量 private int cx;/记录可选物品的价值 public Knapsack0_1_BT(double p, double w, double c) this.p = p; this.w = w; this.n=p.length

33、-1; this.c = c; this.bestp=0; this.cp=0; this.cw=0; x=new intw.length; cx=new intp.length; void Knapsack0_1_BT() backtrack(0); void backtrack(int i) / TODO Auto-generated method stub if(in) /判断是否到达了叶子节点 if(cpbestp) for(int j=0;jx.length;j+) xj=cxj; bestp=cp; return; if(cw+wi=c)/xi=1 搜索右子树 cxi=1; cw+=wi; cp+=pi; backtrack(i+1); cw-=wi; cp-=pi;