《算法设计与分析》-第四章 贪心法.ppt

第四章 贪心算法(Greedy Method) 4.1 贪心算法的基本思想 4.2 活动安排问题 4.3 贪心算法的基本要素 4.4 应用举例－最优装载 4.5 应用举例－单源最短路径问题 4.1 贪心算法的基本思想 贪心算法采用逐步构造最优解的方法。它所作出的每一步决策都是当前状态下的局部最优选择。决策一旦作出，就不可更改。 贪心算法不能对所有问题都能得到整体最优解，但对许多问题它能产生整体最优解。 4.1 贪心算法的基本思想 例：找零钱问题 设有4种硬币，面值分别是25美分、10分、5分、1分。现找给顾客67美分，而且要使总的硬币数最少。 蛮干法：穷举所有可能 贪心法：每次加入一个面值不超过零钱数的最大硬币：25+25+10+5+1+1 4.1 贪心算法的基本思想 例：找零钱问题 贪心法并不能保证任何情况下都能得到最优解。 如硬币面值改为1分、5分、11分；现在须找15分。 若按贪心算法：11+1+1+1+1 而实际最优解为：5+5+5 4.2 活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子 4.2 活动安排问题 1 问题描述： 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。 若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。 活动安排问题就是在所给的集合中选出最大的相容活动子集合。 int greedySelector(int [ ] s, int n, int [ ] f, bool a [ ]) { a[1]=true; j=1; count=1; for ( i=2;i=n;i++) { if (s[i]=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } 4.2 活动安排问题 由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 4.2 活动安排问题 例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下： 4.2 活动安排问题 算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。 4.2 活动安排问题 正确性证明（用数学归纳法证明） 1 贪心选择性质 即证明活动安排问题总存在一个最优解从贪心选择开始。 4.2 活动安排问题 正确性证明（用数学归纳法证明） 1 贪心选择性质 设E={1,2,…,n}为所给的活动集合。由于E中的活动按结束时间的非递减排序，故活动1具有最早完成时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1. 4.2 活动安排问题 正确性证明（用数学归纳法证明） 1 贪心选择性质 设A?E是所给活动安排问题的一个最优解，且A中的活动也按结束时间非递减排序，A中的第一个活动是k。 4.2 活动安排问题 正确性证明（用数学归纳法证明） 1 贪心选择性质 若k＝1,则A就是以贪心选择开始的最优解。 若k1,设B=A-{k}∪{1}。因为f1=fk且A中的活动是相容的。故B中的活动也是相容的。又由于B中的活动个数与A中的活动个数相同，故A是最优的，B也是最优的。即B是以选择活动1开始的最优活动安排。 由此可见，总存在以贪心选择开始的最优活动安排方案。 4.2 活动安排问题 正确性证明（用数学归纳法证明） 2 最优子结构性质 在作出了贪心选择，即选择了活动1后，原问题简化为对E中所有与活动1相容的活动进行活动安排的子问题。即若A是原问题的最优解，则A’=A-{1}是活动安排问题的E’={i∈E:Si≥f1}的最优解。 4.2 活动安排问题 正确性证明（用数学归纳法证明） 2 最优子结构性质