贪心算法
贪心算法
主要使用场景场景
注意事项
得不到最优解的处理方法
输入参数分析
考虑输入参数在什么取值范围内用贪心法可以得到最优解
误差分析
估计近视算法和最优解的误差,对所有的输入实例贪心法所得到的解和最优解的误差(误差上届)
结构
模板
结构模板
主体
实现
cpp
证明方法
贪心算法往往有多种策略,在选择策略时的排除手段主要是举反例
数学归纳法
第一数学归纳法
适用范围
适合证明设计自然数的命题P(n)
归纳基础
证明P(1)为真,(或P(0)为真)
归纳步骤
若对任意n有P(n)为真,证明P(n+1)为真
第二数学归纳法
适用范围
适合证明设计自然数的命题P(n)
归纳基础
证明P(1)为真,(或P(0)为真)
归纳步骤
证明对于任意小于n的k有P(k)为真,证明P(n)为真
经典问题
活动选择问题
问题描述
给一个集合两端[begin,end],给出n个活动,每个活动占用的集合是[ai,bi],要求在这个集合内占用不能重复的安排最多的活动(注意不是占用最多的资源,而是安排最多项活动)
算法设计
贪心设计
每次选择待选集合中满足相容性且结束时间最早的元素加入选择集合.
使用select函数每次从剩余待选集合中挑选符合相容性的结束时间最早的元素加入选择序列,最后没有选择的时候的选择序列就是最优解.
证明
数学归纳法
命题
算法select每次在未加入过的元素中选择结束时间最近且符合相容性的元素添加到选择序列末位.
算法Select执行到第k步,选择k项活动,
i1=1,i2,…ik
则存在最优解A包含活动i1=1,i2,…ik
(选择序列就是最优解,当前选择序列是最优解子集)
归纳基础
k=1,证明存在最优解包含活动1
任取最优解集A,A中活动按结束时间递增排列,如果A的第一个活动j不是1,那么用1替换j得到集合A’,
因为1的结束时间最近,即f1<fj<2号任务开始的时间,替换完成后符合相容性,
此时A’集合的元素个数和A集合相等,A’也是最优解,且含有1.
归纳步骤
假设命题对k为真,证明对k+1也为真
算法执行到第k步选择了活动i1,i2,…,ik,有最优解A包含i1,i2,…,ik,A剩余的元素从待选集合S’中选择.
- select算法的k+1步会从待选集合中选取一个starttime>fk,且endtime最小的元素Sfmin.
设此时Ak+1号元素为j,j不等于Sfmin,则有fj>fSfmin,sj>fk,此时用Sfmin替换j元素,满足sSfmin>fk,fSmin<fj,设替换后的集合是A’,A’元素个数显然等于A,则A’也是最优解. - 转化成子问题也能求解,待选数组S’和A抛去i1,i2,…,ik,的部分又重新组合成了一个归纳基础
例题演示
实现
cpp
最优装载问题
问题描述
n个集装箱,标号是1-n,集装箱i重量是wi,轮船装载重量限制是C,无体积限制,问如何装使得装载的集装箱最多?设对于任意i,wi<=C
这个问题是0-1背包问题的子问题,集装箱相当于物品,物品重量是wi,价值vi都是1,装载限制C相当于背包重量限制b.
建模
设<x1,…xn>表示解向量,xi=0或1代表不装/装
目标函数:
约束条件:
算法设计
贪心策略
轻者优先
贪心过程
将集装箱按照重量升序排列
按照标号从小到大装箱,知道下一个箱子使得总重超过轮船装载重量限制则停止.
证明
数学归纳法
命题
对于装载问题任何规模为n的实例,算法能得到最优解.
设集装箱重量升序标记是1-n
归纳基础
规模是1名题正确
对于任何只含有一个箱子的实例,贪心法有最优解
显然正确.
归纳步骤
规模是n正确,则规模是n+1也正确
总体来说还是假设最优解进行替换得到的解和最优解等效的方法.贪心有的证明时候考虑的就是这么简单,毕竟贪心自己也只能考虑一步.
例题演示
实现
最小延迟调度
问题描述
客户的属性是工作需要消耗的时间ti和要求完成的时间时间di.
f(i)是我们安排的客户开始的时间
那么单个客户的延迟就是f(i)+ti-di,小于0无延迟.
注意目标函数**不是总延迟最小,而是最大的延迟最小**.
建模
算法Schedule
输入:A客户,T单个客户用时,D客户要求结束时间
输出:f开始时间表.
算法设计
贪心策略
按照di从小到大排列逐个安排.
贪心设计
- 按照di升序排列客户
- 从0时刻开始安排f(1)=0;
- i++;
- while i<=n do
- f(i)=f(i-1)+ti-1
- i++;
证明
交换论证
- 分析一般解和最优解的区别
- 设计一种转换操作(替换成分或者交换次序)可以在有限步将任意一个普通最优解逐步转换成算法的解.
- 上述每一步转换都不降低解的最优性质.
贪心算法解的性质
- 没有空闲的时间
- 没有逆序:即i要求的结束时间在j前,但i开始在j后.
引理1
- 没有逆序,没有空闲时间的调度具有相同的最大延迟.
证明要点
从一个没有空闲的最优解出发,逐步转变成没有逆序的解,根据引理1这个解和算法解具有相同的最大延迟,
- 假设一个最优调度存在逆序,那么一定有一个相邻的逆序i,j.
- 交换这个相邻的逆序,则这对逆序被消除了,得到的解依然是最优.
- 交换i,j不影响其他工作的延迟(i,j看做一个整体)
- 交换后j的延迟不会增加,但是i的延迟可能会增加
- 证明i在交换后调度f2的延迟小于j在调度f1的延迟
设有di,ti,dj,tj,fs任务开始
对于调度f1只观察ij情况有- i延迟=fs+ti-di
- j延迟=fs+ti+tj-dj
对于调度f2有 - j延迟=fs+tj-dj
- i延迟=fs+tj+ti-di
又因为i,j是一组逆序,对于f1,f(i)<f(j),di>dj
所以:f2的i延迟=fs+tj+ti-di<f1的j延迟=fs+ti+tj-dj,所以最大延迟可能不变或缩小
- 每次交换之后逆序数-1,至多经过n(n-1)/2次交换得到一个没有逆序的最优调度,等价于算法的解.
例题演示
实现
cpp
参考文献
- P大算法设计分析