Greedy Technique

A Stellar Hiker

2015-01-28

Algorithm, C++, Greedy Technique, leetcode

贪婪技术

贪婪技术建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。这个技术的核心是，所做的每一步选择都必须满足可行、局部最优和不可取消原则。

**可行的：**即它必须满足问题的约束。
**局部最优：**它是当前步骤中所有可行选择中最佳的局部选择。
**不可取消：**即选择一旦做出，在算法的后面步骤中就无法改变了。

贪婪技术并不能保证一定得到最优解。但如果我们关心的是近似解，或者我们只能满足于近似解，贪婪算法仍然是有价值的。

Prim算法

Prim算法是一种为加权连通图构造最小生成树的贪婪算法。它的工作原理是向前面构造的一棵子树中添加离树中顶点最近的顶点。

详细分析与实现见这里。

Kruskal算法

Kruskal算法是另一种最小生成树问题的算法。它按照权重的升序把边包含进来，以构造一棵最小生成树，并使得这种包含不会产生一条回路。为了保证这种检查的效率，需要应用一种所谓的并查算法。

详细分析与实现见这里。

Dijkstra算法

Dijkstra算法解决了单起点最短路径问题，该问题要求出从给定的顶点(起点)出发通向加权图或者有向图的其他所有顶点的最短路径。它的工作过程和Prim算法是一样的，不同点在于它比较的是路径的长度而不是边的长度。对于不含负权重的图，Dijkstra算法总是能够产生一个正确的解。

详细分析与实现见这里。

哈夫曼树

哈夫曼树是一棵二叉树，它使得从根出发到包含一组预定义权重的叶子之间的加权路径长度达到最小。哈夫曼树的最重要的应用是哈夫曼编码。
哈夫曼编码是一种最优的自由前缀边长编码方案，它基于字符在给定文本中的出现频率，把比特串赋给字符。这是通过贪婪地构造一棵二叉树来完成的，二叉树的叶子代表字母表中的字符，而树中的边则标记为0或者1。

详细分析与实现见这里。

[1] 算法设计与分析基础(第2版)
[2] leetcode

贪婪技术

Prim算法

Kruskal算法

Dijkstra算法

哈夫曼树

leetcode相关题目