Greedy Algorithms

算法导论

最优子问题的算法有一系列的步骤，用DP可以解决，但是贪心算法更加高效。贪心算法通常每一步都做最好的选择。

16.1An activity-selection problem

假设有一个序列S={a_1 a_2 a_3 ...a_n}代表要安排n个活动（而场地是有限的）。每一个活动都有一个开始时间s_i和一个结束时间f_i，而且0<=s_i<=f_i<无穷大。a_i这个活动就在一个半开区间里进行，[s_i,f_i).a_i a_j是不相干的，如果他们的时间没有重叠，一个事件的时间完全在另一个事件的后面。我们想要找到安排这样一些活动的最长的时间（对时间最充分的利用）。
我们仍然可以用动态规划的方法来解决问题。
先找到最优子结构。
可以把这个序列分成这样两个部分，S_ik 和S_j，中间还有一个事件k。只要两边的时间安排都是最优的，整个时间的时间安排就是最优的。（这样的解可以有很多个）
然后写出递归式c[i,j]=c[i,k]+c[k,j]+1(这是那个k了)。
同时我们要记忆子结构。

做贪心的选择

有什么办法不要算出所有子问题就得到最终结果吗？那就贪心吧。
我们只要找到在a_1完成后发生的事情，s_1

证明正确性

Theorem 16.1

设我们有一个非空的子问题S_k,a_m是S_k中的一个最早开始的活动，a_m被包含在一些最大的互相和谐的活动S_k里面。

proof

设A_k是S_k中最大的互相和谐的活动，让a_j是A_k中结束最早的活动。如果a_j=a_m,我们就完成了，因为我们表示a_m是S_k中的一些互相和谐的活动中的。如果a_j!=a_m让A_K'=A_K-{a_j}U{a__m}是A_K，而且用a_j替代a_m，A_k'里的问题是不相交的，因为A_k里的活动是不相交的，a_j是A_k里最早完成的时间，f_m<=f_j，因为|A_k'|=|A_k|,我们计算A_k‘是互相和谐活动S_k里的最大的子序列，包括了a_m.
因此我们不需要使用动态规划，只要我们一直选择最早完成的事件。
当然这个算法不一定是从底到顶，也可以是从顶到底的。

递归的贪心算法

迭代的贪心算法

12.2

16.2 Elements of the greedy stratrgy(策略)

Some general properties of greedy methods.
Some step:
1.Determine the optimal substructure of the problem.
2.Develop a recursive solution.
3.Show that if we make the greedy choice, then only one subproblem remains.
4.Prove that it is always safe to make the greedy choice.
5.Develop a recursive algorithm that implements the greedy strategy.
6.Convert the recursive algorithm to an iterative algorithm.
Design greedy algorithms:
1.Cast the problem to a subproblem, and we can solve only one problem.
2.Prove this is save.
3.Compute the solvetion.

Greedy-choice property

Differ from dynamic programming: DP can solve a problem button-up or top-down(记忆的), it must to solve subproblem before solve the problem. But greedy algorithm makes its first choice before solving any subproblems.

Optimal substructure

12.3

16.3 Huffman codes

一种压缩方法，比如有一个100000000000000字的文档全部由abcdef组成，a占了百分之几(最多的)，b占了百分之几......如果用三位的而精致编码表示这些字母，编完这个文档要300000000000000bit，但是如果a是0， b是101......用变化长度的编码表示这些数字，就可以节约。根据百分比可以算出到底用了几个bit，计算压缩率......

Prefix(前缀) codes

建一个二叉树，用这个树来编码（这样译码为什么不会译出多种结果？这样建的话从编码开始走，一定是找到一个才找下一个，不会编错）

12.5
Optimal code is a full binary tree.
We have a set of characters "C".
We have |C| characters.
The tree has |C| leaves and |C|-1 internal nodes.
c.freq(c出现的频率)
d_T(c) c所在的节点的深度（also the length of codeword）
The cost of tree T
B(T)=c.freq*dT(c)a..f

Constructing a Huffman code C.

C :a set of n characters
use bottom-up manner
|C|-1 merging operations(指的是合并节点)
a min priority queue(每次都找频率最小的合并，然后再放在队列里)
keyed on the freq attribute(随意) indentify the two least- frequent objrcts to merge together
事实上伪代码里的yx可以不用，直接用左右孩子表示

Correctress of Haffman's algorithm

x y have the same length and differ only in the last bit
appear as sibling leaves
let a.freq<=b.freq
x.freq<=y.freq
x.freq<=a.freq
y.freq<=b.freq

Lemma 16.3

C' be the alphabet C with the characters x and y remored and a new character z added
C'=C-{x,y}U{z}
z.freq=x.freq+y.freq
T' any tree representing an optimal prefix code for the alphabet C'
T obtained from T'(after replacing)
书上公式

Lemma 16.4

12.7

16.4 Matroids and greedy methods

A matroid is an ordered pair M=(S,I) satisfying the following confitions.
1 S is a finite set.
2 I is a nonempty family of subsets of S.
3 If A belong to I, B belong to I, and |A|<|B|,then there exitsts some element x belong to B-A such that Au{x}belong I.We say that M satisfies the exchange property.

Theorem 16.5

If G=(V,E) is an undirected graph, then M_G=(S_G,I_G) is a matroid.

Theorem 16.6

All maximal independent subsets in amatroid have the same size.

Greesy algorithms on a weighted matroid