算法设计与-第4章贪心算法案例分析.ppt

第4章 贪心算法 4.1 什么是贪心法 4.2 贪心法的典型示例 本章小结 4.1 什么是贪心法 4.1.1 复杂问题的求解方法 4.1.2 贪心法的设计思想 4.2.3 几个例子 4.2.4 小结 4.1.1 复杂问题的求解典型方法 分治法 将复杂问题分成若干个相互独立的子问题，通过求解子问题，并将子问题的解合并得到原问题的解。 动态规划法 将一个复杂问题分解为若干个相互重叠的子问题，通过求解子问题形成一系列决策得到原问题的解。 动态规划是对分治的改善，在发现有重叠问题时，使用自底向上的策略避免重复计算，从而提升了算法的效率。 但仅有动态规划是不够的！！ 4.1.1 复杂问题的求解典型方法 贪心法（Greedy Method） 将一个复杂问题分解为一系列较为简单的局部最优选择，每一个选择都是对当前解的一个扩展，直到获得问题的完整解。 有哪些信誉好的足球投注网站法 4.1.2 贪心法的设计思想 基本思想 将问题的求解过程看作是一系列选择，每次选择都是当前状态下的最好选择(局部最优解)。 每作一次选择后，所求问题会简化为一个规模更小的子问题，从而通过每一步的最优解逐步达到整体的最优解。 4.1.2 贪心法的设计思想 特点 贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。 换言之： 贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。 4.2.3 几个例子 例1：数字三角形问题 例2：渴婴问题 例3：找零钱问题 例1：数字三角形问题 数字三角形问题 穷举法 动态规划法 89：13-11-26-15-24 贪心法 63：13-11-12-14-13 例2：渴婴问题 问题描述 已知： 饮料类型： n 饮料满意度： s1 , s2, …, si , …, sn 饮料总量 ： a1 , a2, …, ai , …, an 需求： t 问： 需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求，而且能达到最大的满意程度呢？ 例2：渴婴问题 问题分析： 令：xi 为婴儿将要饮用的第i 种饮料的量 则：需要解决的问题是找到一组实数xi （1≤i≤n） 例2：渴婴问题 解决方案： 分步获取饮料，每次喝一种饮料，且需要考虑选用哪种饮料； 根据这种思想，利用如下的贪心准则： 从余下的饮料中，选择满意度最高的饮料，直到达到解渴的需要，或者全部饮料被喝完为止。 例3：找零钱问题 问题描述 假如售货员需要找给小孩98元的零钱，售货员手中有1、2、5、10、20、50元的零钱若干。 在小孩的催促下，售货员想尽快将钱找给小孩。 分析： 贪心准则： 每一次选择应使零钱数尽量增大。 为保证解法的可行性 98＝50＋20 ＋ 20 ＋5＋2 ＋1 4.1.4 小结 贪心法的基本思想 由一系列步骤构成 每步满足 可行 ：满足问题的约束条件 局部最优 ：当前状况下的最优解 不可取消 ：一旦作出选择，不可更改 求解问题的类型 局部最优导致全局最优（最优解） 局部最优接近全局最优（近似解），但速度极快 优点 求解速度快，时间复杂性有较低的阶 。 4.1.4 小结 贪心法的基本要素: 具备贪心选择性质和最优子结构性质的最优化问题。 4.2 贪心法的典型应用 组合问题中的贪心法 图问题中的贪心法 其他问题 应用专题一 组合问题中的贪心法 例1：活动安排问题 例2：最优装载问题 例3：0－1背包问题 例4：背包问题 贪心法与动态规划法的异同点 例5：多机调度问题 例1：活动安排问题 问题提出： n个活动的集合E={1,2,…,n} 每个活动i 要求使用资源的时间：[si, fi) 活动i与活动j是相容的： 若区间[si, fi)与区间[sj, fj)不相交，称活动i与活动j是相容的。 活动安排问题：在所给的活动集合中选出最大的相容活动子集合。即：要求高效地安排一系列争用某一公共资源的活动。 例1：活动安排问题 活动安排问题的贪心选择方案 具有最短时段的相容活动 覆盖未选择活动最少的相容活动 在未安排的活动中挑选结束时间最早的活动安排 例1：活动安排问题 例如： 例1：活动安排问题 算法描述： int greedySelector(int s [ ], int f [ ], bool a[ ]){ a[1]=true; int j=1,count=1; for (int i=2;i=n;i++) if (s[i]=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; return count; } 例1：活动安排问题 算法时间分析： 算法gre