第4章贪心算法1.ppt

◎Software College, NEU 第4章 贪心算法Greedy Algorithms 活动安排问题 An Activity-Selection Problem 贪心算法的基本要素 Elements of the greedy strategy 最优装载 Maximum Loading 单源最短路径 Single-Source Shortest Paths 多机调度问题 A task-scheduling problem 什么是贪心方法 假设有4种面值的钱币：２角、１角、5分和１分。 要找给某顾客5角3分钱。 通常是拿出2个2角，1个1角和3个1分的钱币交给顾客(把币值从大到小排序－量度标准)。 这种找钱的方法与其它的找法相比，所拿出的钱币个数是最少的。 什么是贪心方法 上面的找币算法是： 首先选出1个不超过5角3分的面值最大的钱币，即2角； 然后从5角3分中减去2角，剩下3角3分； 再选出1个不超过3角3分的面值最大的钱币，即又一个2角，如此一直做下去。 这个找钱币的算法就是贪心方法。 什么是贪心方法 对于一个问题把满足条件的任何一组解称为可行解。 如上面找钱币问题：拿出1个2角，3个1角和3个1分；五个1角和3个1分；10个五分和3个1分等等都是可行解。 使目标取极值（极大或极小）的可行解，称为最优解。 如上面找钱币问题：拿出2个2角，1个1角和3个1分的可行解就是最优解。 什么是贪心方法 求图着色问题近似解： 先用一种颜色给尽可能多的结点上色， 然后再用另一种颜色在未着色的结点中给尽可能多的结点上色，如此反复直到所有结点都被着色为止，这也是贪心法(greedy)。 什么是贪心方法 A greedy algorithm always makes the choice that looks best at the moment. 贪心方法是作出在当前看来最好的选择，即所作的选择只是局部最优选择。 That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. 希望从局部的最优选择得到整体最优解。 什么是贪心方法 如果硬币面值为1角1分、7分、5分、和1分。 要找给顾客2角6分钱， 按贪心方法找出的硬币个数是：2个1角1分和四个1分，共6枚， 这比1个1角1分和3个5分多了2枚；因此，从局部的最优选择得到的解并不总是问题的最优解。 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。 算法思想 采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。 4.1 活动安排问题An Activity-Selection Problem 已知n个活动 E = { 1, 2, … , n }要求使用同一资源，第k个活动要求的开始和结束时间为sk , fk , 其中sk fk , k = 1, 2, … , n 。如果sk ≥ fj 或者sj ≥ fk ，则称活动k与活动j为相容的。 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。 基本思路 在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。 贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。 例 设待安排的11个活动的开始时间和结束时间如下： 例 设待安排的11个活动的开始时间和结束时间按结束时间的非减次序排列如下： 在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组 start_time 和 fin_time存储。 使得数组中元素的顺序按结束时间非减排列：fin_time1 ? fin_time2 ? … ? fin_timen。 如果所给出的活从未按此序排列，我们可以用O(nlogn)的时间将它重排。 活动安排贪心算法伪代码 templateclass Type void GreedySelector(int n, Type starttime[ ], Type fintime[ ], bool A[ ] ) { } 算法的效率 当输入的活动已按结束时间的非减序排列时，算法只需