计算机算法设计与分析(第2版)4贪心算法.ppt

1、 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi。如果选择了活动i，则它在半开时间区间si,fi)内占用资源。若区间si,fi)与区间sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。下面给出解活动安排问题的贪心算法GreedySelectorGreedySelector:各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按结束时间的非减中且按结束时

2、间的非减序排列序排列 所谓贪心选择性质贪心选择性质是指所求问题的整体最优解整体最优解可以通过一系列局部最优局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上自底向上的方式解各子问题，而贪心算法则通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。2 2、最优子结构性质、最优子结构性质3、贪心算法与动态规划算法的差异 在选择装入背包的物品时，对每种物

3、品在选择装入背包的物品时，对每种物品i i只有只有2 2种选择，即种选择，即装入背包或不装入背包。不能将物品装入背包或不装入背包。不能将物品i i装入背包多次，也不能只装入背包多次，也不能只装入部分的物品装入部分的物品i i。这2类问题都具有最优子结构最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤：算法算法knapsackknapsack的的主要计算时间在于将主要计算时间在于将各种物品依其单位重各种物品依其单位重量的价值从大到小排量的价值从大到小排序。因此，算法的计序。因此，算法的计算时间上界为算时间上界为O O（n

4、lognnlogn）。）。为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明背包问题具有贪心选择性问题具有贪心选择性质质。)()()(cdcfTBTCc Dijkstra算法的迭代过程：)(nO)(2nO)(2nO)(2nO)log(eeO)(2ne)(2noe 约定，每个作业均可在任何一台机器上加工处理，但未约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。完工前不允许中断处理。作业不能拆分成更小的子作业。mn mn),(GGGISMAxxWAW)()(GM)(log(nnfnnOidididiwiwidtNtN)(2nO)(nO)(log(nnfnnO)log(*nnO