贪心策略.doc

贪心策略 贪心策略的定义 贪心策略特点 典型例题与习题在众多的计算机解题策略中,贪心策略可以算得上是最接近人们日常思维的一种解题策略, 正基于此, 贪心策略在各级各类信息学竞赛、尤其在对 NPC 类问题的求解中发挥着越来越重要的作用。 贪心策略的定义贪心策略是: 指从问题的初始状态出发, 通过若干次的贪心选择而得出最优值( 或较优解) 的一种解题方法。其实,从“贪心策略”一词我们便可以看出, 贪心策略总是做出在当前看来是最优的选择, 也就是说贪心策略并不是从整体上加以考虑, 它所做出的选择只是在某种意义上的局部最优解, 而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。例1 :在 n行m 列的正整数矩阵中,要求从每一行中选一个数,使得选出的 n 个数的和最大。本题可用贪心策略:选 n 次,每一次选相应行中的最大值即可。例2: 在一个 N×M 的方格阵中,每一格子赋予一个数(即为权)。规定每次移动时只能向上或向右。现试找出一条路径,使其从左下角至右上角所经过的权之和最大。本题用贪心策略不能得到最优解, 我们以 2×4 的矩阵为例。 3461210 若按贪心策略求解,所得路径为: 1,3,4,6 ; 若按动态规划法求解,所得路径为: 1,2, 10,6。例 3: 设定有 n 台处理机 p1, p2, ......pn, 和m 个作业 j1,j2,...jm, 处理机可并行工作, 作业未完成不能中断, 作业 ji 在处理机上的处理时间为 ti, 求解最佳方案, 使得完成 m 项工作的时间最短? 本题不能用贪心算法求解: 理由是若 n=3,m=6 各作业的时间分别是 1175547 用贪心策略解( 每次将作业加到最先空闲的机器上)time=15, 用搜索策略最优时间应是 14, 但是贪心策略给我们提供了一个线索那就是每台处理上的时间不超过 15, 给搜索提供了方便。总之: 1. 不能保证求得的最后解是最佳的; 2. 只能用来求某些最大或最小解问题; 3. 能确定某些问题的可行解的范围,特别是给搜索算法提供了依据。 贪心策略的特点贪心算法有什么样的特点呢?我认为,适用于贪心算法解决的问题应具有以下 2 个特点: 1、贪心选择性质: 所谓贪心选择性质是指应用同一规则 f ,将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择, 但不依赖于未做出的选择。从全局来看, 运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质, 读者可在后文给出的贪心策略状态空间图中得到深刻地体会。 2、局部最优解: 我们通过特点 2 向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解, 但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解,但贪心策略比动态规划时间效率更高站用内存更少,编写程序更简单。 典型例题与习题例4 :背包问题: 有一个背包,背包容量是 M=150 。有 7 个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。物品 ABCDEFG 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析: 目标