文档介绍：算法设计与分析
——贪心法
贪心算法
主要内容:
介绍贪心法的基本原理,贪心算法设计的基本方法和应用例子。
贪心算法

贪心法是一种算法设计技术,通常用于求解最优化问题。
1. 一个例子
例1. 找钱问题:设有4种硬币,面值分别为25分,10分,5分和1分,要找出63分钱,问如何找钱可使得找出的硬币个数最少?
是否所有找钱问题都可用贪心法解?
贪心算法
一. 贪心法的基本原理
2. 贪心法的基本思想
基本思想:
通过一系列选择步骤来构造问题的解,每一步都是对当前部分解的一个扩展,直至获得问题的完整解。所做的每一步选择都必须满足:
1)可行的:必须满足问题的约束。
2)局部最优:当前所有可能的选择中最佳的局部选择。
3)不可取消: 选择一旦做出,在后面的步骤中就无法改变了。
贪心算法
一. 贪心法的基本原理
2. 贪心法的基本思想
贪心算法的几个经典例子:
Dijkstra算法:求有向图的单源最短路径()
Kruskal算法:求最小生成树()
Prim算法:求最小生成树()
Huffman树、Huffman编码的算法()
贪心算法
一. 贪心法的基本原理
2. 贪心法的基本思想
贪心法不能保证总能得到最优解(一系列的局部最优选择不能保证最后得到整体最优解)
例2. 另一个找钱问题:设有3种硬币,面值分别为25分,10分和1分,要找出30分钱,问如何找钱可使得找出的硬币个数最少?
按贪心法解得: 25分 1个, 1分5个, 共6个
问题的最优解:10分3个
贪心算法
一. 贪心法的基本原理
2. 贪心法的基本思想
贪心算法的关键:贪心选择策略的确定。
例3. 活动安排问题:设有n个活动a1, a2, …, an , 每个活动都要求使用同一资源,而同一时间内只允许一个活动使用这一资源。已知活动ai要求使用该资源的起始时间为si,结束时间为fi,且si<= fi 。要求在a1, a2, …, an中选出最大的相容活动子集。
两活动ai , aj (i≠j)相容是指:
贪心算法
一. 贪心法的基本原理
2. 贪心法的基本思想
例:n=4 , 活动: a1 a2 a3 a4
si: 4 2 1 8
fi : 7 4 5 10
贪心选择策略:按结束时间从早到晚安排活动,每次选择与已选出的活动相容的结束时间尽可能早的活动。
局部最优性:每次为资源留下尽可能多的时间以容纳其它活动。
i
si
fi
1
1
4
2
3
5
3
0
6
4
5
7
5
3
8
6
5
9
7
6
10
8
8
11
9
8
12
10
2
13
11
12
14
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
结果:最大相容子集A={1,4,8,11}
贪心算法
贪心算法