贪心算法培训材料.ppt

贪心算法
清华大学计算机系徐持衡
xuchiheng@
1
理解贪心算法的概念
与动态规划算法的区别
学习几个经典贪心的算法
哈夫曼编码
单源最短路Dijkstra算法
最小生成树Kruskal算法和Prim算法
贪心算法
2
给出2个序列A={a[1],a[2],…,a[n]},B={b[1],b[2],…,b[n]},从A、B中各选出n个元素进行一一配对(可以不按照原来在序列中的顺序),并使得所有配对元素差的绝对值之和最大。
配对(match)——练习2
3
最大的a[i]和最小的B[j]配对
为什么?
配对(match)——练习2
4
顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。
贪心算法的基本概念
5
设有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相容。
要求安排尽可能多的活动并保证它们相容。
活动安排问题
6
活动安排问题(算法)
先将所有活动按照结束时间从小到大排序
依次检查第1,2,……,n个活动,如果活动i与已安排的活动相容(其实只需要判断与上一个被安排的活动是否相容即可),则安排活动i,否则不安排活动i。
7
活动安排问题(算法分析)
算法每次总是选择具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。
一开始的排序需要O(nlogn)的时间,之后的扫描只需O(n)的时间,效率是很高的。
如何证明贪心能得到全局最优解?
数学归纳法
10