贪心法
(Greedy Approach)
基本思想
算法设计
设计要素
与动态规划法的比较
正确性证明
得不到最优解的处理办法
应用实例
1
基本思想
实例：最小生成树的Kruskal算法,活动选择问题
适用问题：组合优化问题，满足优化原则
设计方法：多步判断，解为判断序列
选择依据：
是否满足约束条件
局部优化测度
使用贪心法要解决的问题:
是否可以得到最优解?
不能得到最优解,解与最优解的误差估计
2
例1活动选择问题
S={1, 2, …, n}为n项活动的集合
s i, f i分别为活动i 的开始和结束时间
≥f j或s j≥f i
活动i 与j相容当且仅当s
i
求最大的两两相容的活动集
思路：
按结束时间递增顺序将活动排列为1,2,…,n, ≤f2≤…≤f n
使得f
1
按照标号从小到大选择
3
定理1 算法Select 执行到第k步, 选择k项活
动i
1= 1, i
2
, …, i
k
, 那么存在最优解A包含
i 1=1,i
2
, …, i
k
正确性证明
根据定理：算法至多到第n步得到最优解
6
7
?证明存在最优解包含活动1
?假设按照算法前k 步选择都导致最优解，证明第k +1步选择也导致最优解
1. 第k 步：选择活动i 1=1, i 2, …, i k
2. 归纳假设：存在最优解
A ={i 1=1, i 2, …, i k }∪B
B 是剩下的待选活动集S ’的一个最优解
3. 由归纳基础，存在S ’的最优解B’包含i k +1
4. 由|B’|=|B | 知A’={i 1=1, i 2, …, i k }∪B’最优
5. A’={i 1=1, i 2, …, i k , i k +1}∪(B’-{i k +1})最优. 对步数进行归纳的证明思路
贪心算法的设计
适用：
满足优化原则的组合优化问题
问题求解表示成多步判断
整个判断序列对应问题的最优解
子序列对应子问题的最优解
贪心选择：
确定一个优化测度
不考虑以前的选择，只与当前状态有关
以优化测度的极大（或极小）作为依据
10
贪心算法的设计（续）
确定是否满足贪心选择性质
具有贪心选择性质得到最优解，否则为近似解证明：贪心选择会导致最优解
一般采用归纳法加以证明
对算法步数归纳
对问题规模归纳
自顶向下计算
通过贪心选择，将原问题规约为子问题
线性表记录选择的结果
11
12
数学归纳法
叙述一个可以归纳证明的命题：
?对步数k 归纳
对于任意k ，k 步贪心选择得到i 1,i 2,…,i k , 那么存在最优解包含i 1,i 2,…,i k ?规模k 归纳：
对于任意k ,贪心法得到关于规模为k 的问题的最优解
归纳基础：k =1, 命题为真
归纳步骤：假设对 13 n i x c x w x i i n i i n i i ,...,2,11,0max 11 ==≤∑∑==贪心法：将集装箱按照从轻到重排序，轻者先装 例2最优装载Loading n 个集装箱1,2,…,n 装上轮船，集装箱i 的重量w i , 轮船装载重量限制为c ，无体积限制. 问如何装使得上船的集装箱最多？不妨设w i ≤c . 贪心选择性质证明思路 ?设集装箱标号按照从轻到重记为1, 2, …, n ?对问题规模n 进行归纳 ?n=1, 贪心选择得到最优解（只有一个箱子）?假设对于规模为n-1的输入得到最优解，证明对规模为n的输入也得到最优解 14 说明 Loading算法 复杂性T(n) = O(n log n) Loading问题是0-1背包问题的特例： = 1, i=1, 2, …, n. 即v i 该问题是O(n log n) 时间可解的 0-1背包问题是NP难的。 16 贪心法得不到最优解 的处理办法 讨论对于哪些输入贪心选择能够得到最优解输入应该满足的条件 讨论贪心法的解最坏情况下与最优解的误差绝对误差与相对误差估计 17 确定得到最优解的输入 所满足的条件 例3找零钱问题 设有n种零钱, 重量分别为w 1, w 2 , ... , w n , 价值分别为v 1=1, v 2 , ... , v n . 付的总钱数是y 如何付钱使得所付钱的总重最轻? 18
相关主题
文本预览