4贪心算法教材课程.ppt

4.4 单源最短路径 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 1.算法基本思想 Dijkstra算法是解单源最短路径问题的贪婪技术。 * 第4章 贪婪技术 第4章 贪婪技术 顾名思义，贪婪技术总是作出在当前看来最好的选择。也就是说贪婪技术并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪婪技术得到的最终结果也是整体最优的。虽然贪婪技术不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪婪技术不能得到整体最优解，其最终结果却是最优解的很好近似。 第4章 贪婪技术 例子： 学校只有一个打气筒，给三轮打气需7分钟，给自行车打气需4分钟，给平板车打气需5分钟。同时来了三种车各一辆，如果每辆车打完气就走，怎样安排三辆车的打气顺序，使三种车共需的时间最省（包括打气和等待的时间），且最小要花多少时间？ 第4章 贪婪技术 例子： 找硬币 有四种硬币 2角5分 1角 5分 1分 找6角3分→2个 2角5分 1个 1角 3个 3分 （先找不超过6角3分的最大硬币） 第4章 贪婪技术 不是所有问题都有最优解 找硬币 有三种硬币 1分 5分 1角1分 找1角5分→ 贪婪技术：一个 1角1分 四个 1分 最优： 三个 5分 4.1 活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪婪技术有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪婪技术提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 4.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相容。 活动安排问题： 要在所给的活动集合中选出最大的相容活动子集合。 4.1 活动安排问题 采用贪婪技术实现： 各个活动的起始时间和结束时间存储于数组s和f中，且按结束时间的非递减排序： f1≤f2 ≤… ≤ fn 集合A存储所选择的活动，活动i在集合A中，当且仅当A[i]的值为true,变量j用以记录最近一次加入到A中的活动。 4.1 活动安排问题 例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下： i 1 2 3 4 5 6 7 8 9 10 11 S[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14 A[1]=true j=1 A[4]=true j=4 A[8]=true j=8 A[11]=true j=11 4.1 活动安排问题 public static int greedySelector(int [] s, int [] f, boolean a[]) { int n=s.length-1; a[1]=true; int j=1; int 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; } 4.1 活动安排问题 由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 算法greedySele