之前我们介绍了用动态规划的方法来解决一些最优化的问题。但对于有些最优化问题来说，用动态规划就是“高射炮打蚊子”，采用一些更加简单有效的方法就可以解决。贪心算法就是其中之一。贪心算法是使所做的选择看起来是当前最佳的，期望通过所做的局部最优选择来产生一个全局最优解。

一、 活动选择问题

【问题】对几个互相竞争的活动进行调度：活动集合S = {a1, a2, ..., an}，它们都要求以独占的方式使用某一公共资源（如教室），每个活动ai有一个开始时间si和结束时间fi ，且0 ≤ si < fi < ∞，一旦被选择，活动ai就占据半开时间区间[si, fi)，如果区间[si, fi)和[sj fj)互不重叠（si ≥ fj 或sj ≥ fi ），称活动ai和aj是兼容的。

【目标】找出一个最大的（活动数目最多的）相互兼容活动集合。

1、 动态规划的解法：

a、 最优子结构： 

Sij 是S中活动的子集，其中每个活动都在活动ai结束之后开始，且在活动aj开始之前结束。它们与ai和aj兼容，也与任何不迟于ai结束和不早于aj开始的活动兼容。

不妨假设活动已按照结束时间的单调递增顺序排序：f0≤ f1≤ f2≤ …≤ fn< fn+1，其中f0 = 0 and sn+1 = ∞.

显然，当i ≥ j时Sij = ?。

子问题空间就是从Sij中选择最大兼容活动子集，其中0 ≤ i < j ≤ n + 1

b、 递归定义最优解

考虑某个非空子问题Sij，并假设它的解包含某活动ak，其中fi ≤ sk < fk ≤ sj，于是可以用活动ak生成两个子问题：Sik, Skj。

假设Sij的最优解Aij包含活动ak，则包含在Sij最优解中的针对Sik的解Aik和针对Skj的解Akj必定也是最优的。

于是：Aij =Aik∪{ak}∪Akj

设c[i, j]为Sij中最大兼容子集中的活动数，当Sij = ?，有c[i, j] = 0；当i ≥ j. 有c[i, j] = 0；如果ak在Sij的最大兼容子集中被使用，则子问题Sik和Skj的最大兼容子集也被使用，于是有递归式：c[i, j ] = c[i, k] + c[k, j ] + 1。

2、 贪心算法：将动态规划解转化为贪心解

【定理】对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动：fm = min {fk : ak ∈ Sij}.那么：

1） 活动am在Sij的某最大兼容活动子集中被使用；

2） 子问题Sim为空，所以选择am将使子问题Smj成为唯一可能非空的子问题。

由上面的定理可知：只需要考虑一个子问题（另一个子问题一定为空），在解决子问题Sij时，我们只需考虑一种选择：在Sij中有着最早结束时间的那个活动，可以自顶向下解决每一个子问题：为解决子问题Sij，选择Sij中具有最早结束时间的活动am，并将子问题Smj的最优解中的活动集合加入到Sij的解中。

a、 递归贪心算法：

Recursive-Activity-Selector(s, f, i, j)
1 m<--i+1
2 while m < j and sm < fi
3 	do m<--m+1
4 if m < j
5 	then return {am}∪Recursive-Activity-Selector(s, f, m, j)
6 else return nil

Greedy-Activity-Selector(s, f)
1 n<--length[s]
2 A<--{a1}
3 i<--1
4 for m<-- 2 to n
5 	do if sm >= fi //活动与选择的上一个活动兼容
6 		then A<--A∪{am}
7 		i<--m
8 return A

二、 贪心策略的基本内容

原理： 贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时最佳的选择。

1、 上一节，我们开发一个贪心算法经历了如下的步骤：

a）、 决定问题的最优子结构；

b）、 设计出一个递归解；

c）、 证明在递归的任一阶段，最优选择之一总是贪心选择。那么，做贪心选择总是安全的；

d）、 证明通过做贪心选择，只有一个子问题非空；

e）、 设计出一个实现贪心策略的递归算法；

f）、 将递归算法转换成迭代算法

2、 上面的步骤过于繁琐，可以简化为：

a）、将优化问题转化成这样的一个问题，即先做出选择，再解决剩下的一个子问题；

b）、 证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择是安全的；

c）、 说明贪心选择后满足最优子结构，所以将子问题的最优解和我们所做的贪心选择联合起来，可以得出原问题的一个最优解。

3、 贪心算法的使用条件：贪心选择性质和最优子结构是两个关键的特点。如果我们能够证明问题具有这些性质，那么就可以设计出它的一个贪心算法。

a、 贪心选择性质： 一个全局最优解可以通过局部最优（贪心）选择来达到。

这一点是贪心算法不同于动态规划之处。动态规划中，每一步做出选择，这些选择依赖于子问题的解，先解子问题再做选择！我们必须证明在每一步所做的贪心选择最终能产生一个全局最优解。在证明中先考察一个全局最优解，然后证明可对该解加以修改，使其采用贪心选择，仍然是最优解。

贪心选择往往由某个值进行选择：固定的优先级；变化的优先级。

b、 最优子结构：对一个问题来说，如果它的一个最优解包含了其子问题的最优解，则称该问题具有最优子结构。

对比：

三、 Bellman-Ford算法

【问题】给出一个带权有向图G = (V, E)，加权函数w : E → R为从边到实数权值的映射，求从给定点s到所有定点的单源最短路径（权值之和）。

1、 最短路径的最优子结构： 最短路径的子路径是最短路径。

2、 负边权值：如果图G=(V,E)不包含从源s可达的负权回路，则对所有v ∈V，最短路径的权的定义δ(s,v)依然正确。后面可以看到Dijkstra算法假设所有边权值非负，Bellman-Ford算法允许输入图中存在负权边。

3、 关于回路：最短路径不能包含正权、负权回路，可以包含0权回路，但是没有必要。

4、 最短路径的表示： 前驱子图。算法结束时，Gπ就是最短路径树。最短路径并不唯一，因此最短路径树也是一样。

5、 松弛技术： 对每个顶点v ∈ V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计。

初始化最短路径估计：

Initialize-Single-Source(G, s)
1 for each vertex v in V[G]
2 	do d[v]<--INF
3 		Pi[v]<--nil
4 d[s]<--0

  松弛一条边(u,v)的过程中，测试是否可以通过u，对迄今找到的到v的最短路径进行改进，如果可以，则更新d[v]和π[v]。

Relax(u, v, w)
1 if d[v] > d[u] + w(u, v)
2 	then d[v]<--d[u] + w(u, v)
3 <span style="white-space:pre">	</span>Pi[v]<--u

a、 三角不等式：对任意边(u,v) ∈E，有δ(s, v) <= δ(s, u)+w(u.v)；

b、 上界性质： 对任意顶点v ∈V，有d[v] >= δ(s, v),而且一旦d[v]达到δ(s, v)值就不再改变。

c、 无路径性质： 如果从s到v不存在路径，则总有d[v]= δ(s, v)=INF

d、 收敛性质： 如果s-->u-->v是图G某u，v ∈V的最短路径，而且松弛边(u,v)之前的任何时间d[u]= δ(s, u),则操作过后总有d[v]= δ(s, v)。

e、 路径松弛性质： 如果p=<v0,v1,…,vk>是从s=v0到vk的最短路径，而且p的边按照(v0,v1),(v1,v2),…,(vk-1,vk)的顺序进行松弛，那么d[vk]=δ(s, vk)。这个性质的保持不受其他松弛操作的影响，即使它们与边p的边上的松弛操作混合在一起也是一样的。

6、 Bellman-Ford算法： 能在一般情况下（存在负边权的情况），解决单源最短路径问题。

Bellman-Ford(G, w, s)
1 Initialize-Single-Source(G, s)
2 for i <--1 to |V[G]|-1
3 	do for each edge (u, v) in E[G]
4 		do Relax(u, v, w)
5 for each edge (u, v) in E[G]
6 	do if d[v] > d[u] + w(u, v)
7 		then return False
8 return True

四、 Dijkstra算法

1、 Dijkstra算法解决了有向图G=(V,E)上带权的单源最短路径问题，但要求所有边的权值非负。

a、 假定对每条边(u,v)∈E，有w(u, v) ≥ 0；

b、 顶点集合S，从源点s到集合中的顶点的最短路径的权值均已确定。

c、 算法反复选择具有最短路径估计的顶点u∈ V-S，并将u加入到S中，对u的所有边进行松弛。

d、 Q是顶点的最小优先队列，排序关键字为顶点的d值。

Dijkstra(G, w, s)
1 Initialize-Single-Source(G, s)
2 S<--Nil
3 Q<--V[G]
4 while Q != nil
5 	do u<--Extract-Min(Q)
6 	S<--S ∪ {u}
7 	for each vertex v ∈ adj[u]
8 		do Relax(u, v, w)

2、 定理：已知一带权有向图G=(V,E)，其加权函数w的值为非负，源点为s。对该图运行Dijkstra算法，则在算法终止时，对所有u ∈ V有d[u]=δ(s,u)。

3、 Dijkstra算法运行时间分析：

a、 其中调用了三种优先级队列操作： INSERT（第3行）|V|次， EXTRACT-MIN（第5行） |V|次， DECREASE-KEY（第8行调用的RELAX中）所有的for循环中有共计|E|次迭代。

b、 算法运行时间依赖于最小优先级队列的具体实现： 简单的将d[v]存入一个数组的第v项，INSERT和DECREASE-KEY操作都是O(1)时间，EXTRACT-MIN操作是O(V)时间。总的时间为O(V^2+E+V) = O(V^2).

选用不同的优先级队列操作：

Time = n X ( T(insert )+ T(extract-min)) + m x T(decrease-key)，其中（|v| = n,  |E| = m）

五、 贪心算法的理论基础： 拟阵

贪心方法可解的问题当中有一部分是可以通用“拟阵”来解的， 虽然拟阵没有覆盖贪心方法所适用的所有情况（例如活动选择问题和赫夫曼编码问题），但是它覆盖了许多具有实际意义的情况， 并且发展很快，并正在覆盖更多的应用。

1、 拟阵： 

满足下列条件的一个序对M = (S,?)：

1） S是有限非空集合；

2） ?是S的一个非空子集族，称为S的独立子集，使得如果B ∈?且A ? B，那么A ∈?。我们说?是遗传的，如果它满足这个性质。（空集?必为?的一个成员）

3） 如果A ∈?, B ∈?，且|A| < |B|，则有某个元素x ∈ B - A使得A∪{x} ∈?。我们称M满足交换性质。

2、 加权拟阵的贪心算法：

Greedy(M, w)
1 A<--nil
2 sort S[M] into monotonically decreasing order by weight w
3 for each x in S[M], taken in monotonically decreasing order by weight w
4 	do  if A∪{x}∈l[M]
5 		then A<--A∪{x}
6 return A

1） GREEDY的排序阶段的时间为O(n lgn)；

2） 第4行中对S中的每个元素执行一次，共n次；

3） 在第4行的每次执行中要检查A∪{x}是否独立；

4） 如果每次检查的时间为O(f(n))，则整个算法的运行时间为O(n lg n + nf (n))。

适宜用贪心方法来获得最优解的许多问题，都可以归结为在加权拟阵M = (S,?)中，找出一个具有最大权值w(A)的独立子集A∈?的问题。