贪婪算法（Greedy Algorithm）

1. 基本思想

• 每一步都做当前看来最优的选择（即局部最优），希望通过一系列局部最优，达到整体最优。

• 特点是只顾眼前（每次选择最优），不回溯。

2. 贪婪问题分类

• 绝对贪婪问题：

每一步的局部最优选择，最终一定得到全局最优解。

• 例子：活动安排问题、最小生成树问题。

• 相对贪婪问题：

贪婪算法得到的解不是全局最优，但通常是一个近似最优（有时足够好了）。

• 例子：一些NP问题的贪婪近似，比如旅行商问题的贪婪解。

贪婪算法与问题复杂性

• P问题：可以在多项式时间内求解的问题（即存在有效算法）。

• NP问题：能在多项式时间内验证一个解是否正确，但不一定能快速求解。

• 贪婪算法通常用于P问题或NP问题的近似解。

• 有效算法：

运行时间是问题规模的多项式函数，比如 O(n^2), O(nlog⁡n)。

• 相对的，指数时间 O(2^n)算法就不是有效算法。

经典例题

1. 工资分发问题（类似找零问题）

• 题意：用最少数量的钱币发工资。

• 解法：每次选面额最大且不超过剩余金额的钱币。

• 注意：有些面额组合下贪心策略不一定最优（比如奇怪的硬币系统）。

2. 活动安排问题

• 题意：给定若干活动，每个活动有开始、结束时间，要求安排最多不重叠活动。

• 贪心策略：优先选结束时间最早的活动。

3. 多机调度问题

• 题意：n个任务分配到k台机器，使得最晚完成时间最早。

• 贪心策略：每次将任务分配到当前负载最轻的机器上。

重要贪婪算法

1. Huffman树构造（最优编码问题）

• 题意：给定字符及其出现频率，设计编码使总编码长度最短。

• 方法：

每次选取出现频率最小的两个节点合并。

• 最后生成哈夫曼树。

2. 单源最短路径：Dijkstra算法

• 适用于边权非负的图。

• 思路：

维护一张最短距离表。

• 每次选取当前未访问、距离源点最短的点，更新它的邻居。

3. 最小生成树

• Prim算法：

从任意点开始，逐步将最近的点连入生成树。

• Kruskal算法：

把边按权值从小到大排序，逐条选边，如果不会成环就加入生成树。

• 用并查集快速判断成环。