算法设计与分析课程复习笔记8——贪婪算法

贪婪算法

• 与动态规划方法相似，是更简单的解决优化问题的方法，通常用于求解优化问题
• 如有选择，选择眼下看起来最优的那个（局部最优→全局最优）
• 贪婪算法不能保证一定得到最优解
• 对于具有某些特征的问题，贪婪算法有最优解

作业选择问题

对n个作业进行排程，这些作业在执行期间需要专用某个共同的资源
$S=\{a_1,a_2,……a_n\}$S={a1​,a2​,……an​}作业集合
$a_i$ai​在$[s_i,f_i)$[si​,fi​)需要专用资源【$s_i$si​:起始时间，$f_i$fi​:结束时间，$0≤s_i&lt;f_i&lt;\infty$0≤si​<fi​<∞】

$a_i$ai​与$a_j$aj​没有冲突：$a_i$ai​在$a_j$aj​发生前结束或$a_i$ai​在$a_j$aj​结束后发生。

选出最多个不冲突作业

i	1	2	3	4	5	6	7	8	9	10	11
$s_i$si​	1	3	0	5	3	5	6	8	8	2	12
$f_i$fi​	4	5	6	7	8	9	10	11	12	13	14

作业按完成的先后顺序排列
$｛a_3,a_9,a_{11}｝$｛a3​,a9​,a11​｝是一组可协调作业集合
最多可协调作业集合：$｛a_1,a_4,a_8,a_{11}｝$｛a1​,a4​,a8​,a11​｝,$｛a_2,a_4,a_9,a_{11}｝$｛a2​,a4​,a9​,a11​｝

优化基础
定义子问题空间：$S_{ij} = { a_k ∈ S : f_i ≤ s_k &lt; f_k ≤ s_j }$Sij​=ak​∈S:fi​≤sk​<fk​≤sj​【在$a_i$ai​结束之后和$a_j$aj​开始之前的所有作业】
完整问题：$S_{0,n+1}$S0,n+1​
$a_0 = [-\infty,0)$a0​=[−∞,0)
$a_{n+1}= [\infty,\infty+1)$an+1​=[∞,∞+1)

问题空间$S_{ij}$Sij​，其中的作业按照完成时间递增的顺序排列
$f_0≤f_1≤f_2≤……≤f_n≤f_{n+1}$f0​≤f1​≤f2​≤……≤fn​≤fn+1​

解的组成
Solution to $S_{ij}$Sij​ = (Solution to $S_{ik}$Sik​) ∪ {$a_k$ak​} ∪ (Solution to $S_{kj}$Skj​)
|Solution to $S_{ij}$Sij​| = |Solution to $S_{ik}$Sik​| +1+ |Solution to $S_{kj}$Skj​|
$S_{ij}$Sij​的最优解由子问题$S_{ik}$Sik​和$S_{kj}$Skj​的最优解组成

用c[i,j]表示$S_{ij}$Sij​的最优解集合中作业的数目
if $S_{ij}$Sij​=空集，c[i,j]=0

c[i,j]=c[i,k]+c[k,j]+1

$c[i,j]=\left\{ \begin{aligned} 0,　if　S_{ij}=空集\\ max_{i&lt;k&lt;j,a_k∈S_{ij}}\{c[i,k]+c[k,j]+1\},　if　S_{ij}≠空集\\ \end{aligned} \right.$c[i,j]={0,　if　Sij​=空集maxi<k<j,ak​∈Sij​​{c[i,k]+c[k,j]+1},　if　Sij​̸​=空集​

定理
如果$S_ij$Si​j是非空的作业集，$a_m$am​是其中最先完成的一个，那么，$a_m$am​是某个最优解中的一个作
业,$S_{im}$Sim​为空集，$S_{mj}$Smj​是唯一的非空子问题。

定理用途

	动态规划	使用定理
子问题数目	2个，$S_{ik}$Sik​,$S_{kj}$Skj​	由于$S_{im}$Sim​为空，所以只有一个子问题$S_{mj}$Smj​
选择情况	j-i-1个选择	1个选择:$S_{ij}$Sij​中最先完成的一个

贪婪法

1. 从$S_{ij}$Sij​中选择不冲突的最多作业
   选择$S_{ij}$Sij​中最先完成的作业$a_m$am​,此即贪婪选择
   将$a_m$am​加入到最优解集合
   继续求解$S_{mj}$Smj​
2. 由定理保证选择$a_m$am​，是将其加入到了一个可能的最优解
   在作出选择时不必求解$S_{mj}$Smj​

递归贪婪算法
REC-ACT-SEL (s, f, i, n)
m ← i + 1
while m ≤ n and $s_m$sm​ < $f_i$fi​ ►在$S_{i,n+1}$Si,n+1​确定第一个与$a_i$ai​不冲突的事件
　　do m ← m + 1
if m ≤ n
　then return {$a_m$am​} ∪ REC-ACT-SEL(s, f, m, n)
else return 空集

作业按完成时间递增顺序排列
运行开销：$Θ(n)$Θ(n)
初始调用：REC-ACT-SEL (s, f, 0, n)

增量算法（迭代贪婪算法）
GreedyActivitySelector(s,f,n)
　A ← {$a_1$a1​}
　i ← 1
　for m ← 2 to n
　　do if $s_m$sm​ ≥ $f_i$fi​　　　►$a_m$am​和$a_j$aj​不冲突
　　　　then A ← A ∪ {$a_m$am​}
　　　　　　i ← m　　►$a_i$ai​是最近添加到A的
　return A

作业按完成时间递增顺序排列
运行开销：$Θ(n)$Θ(n)

贪婪算法步骤

1. 确定问题的优化结构
2. 得到递归解
3. 证明某个最优选择是贪婪选择
4. 贪婪选择将产生唯一 一个非空子问题
5. 用递归算法实现贪婪策略
6. 将递归算法转换为迭代算法

动态规划与贪婪算法的比较

• 动态规划
  每步选择
  选择与子问题解相关
  自底向上
• 贪婪算法
  首先做出贪婪选择
  求解贪婪选择后产生的唯一子问题
  后续贪婪选择与前面的选择有关，但与子问题的解无关
  自顶向下，问题规模逐步缩小

Huffman编码

利用字符出现的频率，建立表示每个字符的最优方法，用于文件压缩

	a	b	c	d	e	f
Frequency(thousands)	45	13	12	16	9	5

变长编码：
频率高的字符被赋予短编码，频率低的字符被赋予长编码
a = 0, b = 101, c = 100, d = 111, e = 1101, f = 1100

前缀码Prefix Codes
一个字符的编码必须不能是另一个字符编码的前缀
更准确的名字应该是“prefix-free codes”
利用前缀码可以进行文件压缩

通过合理的编码尽可能地压缩文件，标准的ASCII码用7位来表示每个字符

等长编码表示：

前缀码表示：

为什么要使用前缀码？
因为非前缀码会导致二义性。

前缀码表示
二分树，叶节点表示字符
0表示左，1表示右，从根到叶即为字符编码
从根到叶路径长度即是编码长度

最优编码
最优编码通过完整二分树表示，每个非叶节点都有两个子节点，定长编码不是最优的，变长是的。
编码一个文件需要多少位
C：字符集，f( c ):字符c的频率，$d_T(c)$dT​(c):字符编码长度

$B(T)=\displaystyle \sum_{c∈C}f(c)d_T(c)$B(T)=c∈C∑​f(c)dT​(c)

构造Huffman编码
贪婪算法
假设：
字符集C有n个字符
f(c)代表c的字符频率
自底向上构建完整二分树

想法：
从叶节点开始
每次合并频率最小的两个叶节点，生成的新节点的频率为两者之和
在新节点和其他节点中再找出两个频率最小的节点，合并生成新节点

算法：
Huffman(C)
　n ← |C|
　Q ← C　　　　　$O(n)$O(n)
　for i ← 1 to n-1　　　　　　　　　　　　　　　｜
　　do allocate a new code z　　　　　　　　　　｜
　　　left[z] ← x ← ExtractMin(Q)　　　　　　　　｜
　　　right[z] ← y ← ExtractMin(Q)　　　　　　　$O(nlgn)$O(nlgn)
　　　f[z]← f[x]+f[y]　　　　　　　　　　　　　　｜
　　　Insert(Q,z)　　　　　　　　　　　　　　　｜
　return ExtractMin(Q)

运行开销：$O(nlgn)$O(nlgn)

背包问题

0/1背包问题：要么拿走，要么放弃
部分背包问题：可部分拿走

0/1背包问题

背包的可容重量为W
n个物件，第i个的价值为$v_i$vi​,重量为$w_i$wi​
目标：不超重，价值最大

如果你作出贪婪选择，即装入平均价值最高的物件，你最终不可能获得最大化的价值总量
0/1背包问题需要通过动态规划来解决！

部分背包问题

背包的可容重量为W
n个物件，第i个的价值为$v_i$vi​,重量为$w_i$wi​
目标：不超重，价值最大

策略：

• 挑选出单位重量价值最高的物件
• 在容量许可下,尽量转载单位重量价值最高的物件，直至拿光
• 然后依次装载其余物件中价值最高的物件，物件价值递减排列

算法：
FractionalKnapsack(W,v[n],w[n])
　while w>0 and as long as there are items remaining(背包有容量）
　　pick item with maximum $v_i$vi​/$w_i$wi​(选择最有价值之物）
　　$x_i$xi​ ← min(1,w/$w_i$wi​)(拿走整个，还是部分）
　　remove item i from list(从其余物件中装载）
　　w ← w - $x_iw_i$xi​wi​(w:容量空余）

参考：任课教师邱德红教授的课件