算法►算法设计技巧与分析

贪心

文章目录

贪心算法也用于求解最优化问题，不同的是贪心算法通常包含一个寻找局部最优解的迭代过程，在某些实例中 这些局部最优解转变为了全局最优解。而在另外的一些情况下，则无法转变为全局最优解。贪心算法在少量计算的基础上做出正确猜想而不急于考虑以后的情况，这样一步一步来构筑解，每一步均是建立在局部最优解的基础之上，每一步又扩大了部分解的规模。

设计贪心算法的困难部分就是要证明该算法确实求解了它所要解决的问题，而与之相比 递归算法拥有十分简单的归纳证明。考虑一下证明以下几个问题的难度，1）单源最短路径 2）最小耗费生成树 3）Huffman编码。

图中 G(V, E) 单源最短路径(迪杰斯特拉)

1
2
3
4
5
6
7
8
9
10
11
12
dijkstra alg
U = {v} # U是已经寻找到最短路径的节点 
S = V - {v} # 待寻找的节点
D 一个从源点到其他节点的最短距离
while S 不为空:
	从S中选择一个距离最小的节点 u
	U = U ∪ {u}
	S = S - {u}
	for u所有邻边 (u, w):
		if w∈S and D[u]+length(u, w) < D[w]:
			D[w] = D[u] + length(u, w)
return D