算法之贪默算法

贪默算法

核心头脑

贪默算法（Greedy Algorithm）是一种在每一步选择中都接纳在当前状态下最优的选择，从而渴望以这种方式能够到达全局最优解的一种算法头脑。贪默算法并不总是能得到全局最优解，但在一些问题中，它能产生出充足好的解，而且相对简单高效。
贪默算法的基本头脑是通过一系列局部最优的选择，渴望终极到达全局最优。在每一步，贪默算法会选择当前状态下的最优解，而不思量当前选择对以后的影响。这与动态规划的头脑不同，动态规划思量到每一步的选择对于团体解的影响，而做出相应的决议。
贪默算法通常实用于满意两个条件的问题：

• 最优子布局性质： 当一个问题的最优解包罗其子问题的最优解时，称该问题具有最优子布局性质。
  
• 贪心选择性质： 通过局部最优选择，期望能够到达全局最优。
  

一旦一个问题可以通过贪默算法求解，那么贪默算法一样平常会比其他算法更加高效。然而，需要留意的是，并非全部问题都满意贪心选择性质和最优子布局性质。
常见应用场景

• 霍夫曼编码：用于数据压缩，为高频字符分配短编码、低频字符分配长编码，淘汰团体数据量。
  
• 运动选择问题：选择一组互不相容的运动，使得到场的运动数最大。
  
• 最小天生树：如Kruskal和Prim算法，用于在加权连通图中找到权值之和最小的天生树。
  
• Dijkstra最短路径算法：求解单源最短路径问题，从起始点开始，每次遍历到间隔近来且未访问过的极点的邻接节点。
  
• 货仓选址问题：在一维数轴上为多个市肆选择货仓位置，使得总间隔最小。
  

在利用贪默算法时，必须确保贪心选择的局部最优解能够推导出全局最优解，否则大概得不到最优解。
范例案例

案例一：找零问题

问题描述：假设你是柜台售货员，需要给客户找零n元钱。你拥有无穷数目的1元、2元、5元、10元、20元、50元面额的硬币/纸币。怎样用最少数目的硬币/纸币来找零？
贪心战略：每次只管用面额最大的硬币来找零。
示例：
假设要找零的金额为 n = 36 元。
可用的硬币面额为 1、2、5、10、20 和 50。

• 起首，找零最大的面额，即 50 元。但由于 50 元大于 36 元，以是不能利用。
  
• 接下来，只管利用次大面额的硬币，即 20 元。36 元中能用一个 20 元，剩下 16 元。
  
• 然后利用次次大面额的硬币，即 10 元。16 元中能用一个 10 元，剩下 6 元。
  
• 继续利用 5 元的硬币，6 元中能用一张 5 元，剩下 1 元。
  
• 末了，用 1 元的硬币找零 1 元。
  

如许，用 20 元、10 元、5 元和 1 元的硬币一共找零 36 元，共需要 4 枚硬币，是最少数目的硬币。
在这个案例中，贪默算法的贪心战略是每次都选择当前环境下的最优解，即选择当前可用的最大面额的硬币。这种战略在这个特定问题中得到了最优解。但需要指出的是，对于不同的面额组合和要求找零的金额，贪默算法并不总是能够得到最优解。
代码实现：

1. #include <stdio.h>
2. void findChange(int amount) {
3.     int money[] = { 50, 20, 10, 5, 2, 1 };
4.     int num = sizeof(money) / sizeof(money[0]);
5.     printf("找零 %d :\n", amount);
6.     for (int i = 0; i < num; ++i) {
7.         int current = money[i];
8.         int numNotes = amount / current;
9.         if (numNotes > 0) {
10.             printf("%d 张 %d 块\n", numNotes, current);
11.             amount = amount % current;
12.         }
13.     }
14. }
15. int main() {
16.     int amount = 46;
17.     findChange(amount);
18.     return 0;
19. }

复制代码

复杂度分析：

• 时间复杂度：O(1)，由于面额种类有限。
  
• 空间复杂度：O(1)。
  

留意：对于某些面额组合，贪默算法不一定能得到最优解。
案例二：运动选择问题

问题描述：有n个运动，每个运动有开始时间和竣事时间，要求选择最多数目的互不重叠运动。
贪心战略：每次选择竣事时间最早且不与已选运动辩论的运动。
伪代码：

1. 1. 按活动结束时间从小到大排序
2. 2. 依次选择与已选活动不冲突的下一个活动

复制代码

代码实现：

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义活动结构体，包含开始时间和结束时间
5. typedef struct {
6.     int start;  // 活动开始时间
7.     int end;    // 活动结束时间
8.     int index;  // 活动编号（可选，用于标识活动）
9. } Activity;
11. // 比较函数，用于按活动结束时间排序
12. int cmp(const void *a, const void *b) {
13.     return ((Activity*)a)->end - ((Activity*)b)->end;
14. }
16. // 贪心算法选择活动函数
17. void selectActivities(Activity acts[], int n) {
18.     // 按活动结束时间从小到大排序
19.     qsort(acts, n, sizeof(Activity), cmp);
20.    
21.     // 选择第一个活动（结束时间最早的活动）
22.     int count = 0;  // 记录选择的活动数量
23.     int lastEnd = -1;  // 上一个选择的活动的结束时间，初始为-1
24.    
25.     printf("选择的活动：\n");
26.     for (int i = 0; i < n; ++i) {
27.         // 如果当前活动的开始时间大于等于上一个选择的活动的结束时间，则选择该活动
28.         if (acts[i].start >= lastEnd) {
29.             count++;
30.             printf("活动%d: [%d, %d]\n", acts[i].index, acts[i].start, acts[i].end);
31.             lastEnd = acts[i].end;  // 更新最后选择的活动的结束时间
32.         }
33.     }
34.     printf("共选择了 %d 个活动\n", count);
35. }
37. // 主函数，演示活动选择问题
38. int main() {
39.     // 示例活动集合，每个活动有开始时间、结束时间和编号
40.     Activity activities[] = {
41.         {1, 4, 1},   // 活动1：开始时间1，结束时间4
42.         {3, 5, 2},   // 活动2：开始时间3，结束时间5
43.         {0, 6, 3},   // 活动3：开始时间0，结束时间6
44.         {5, 7, 4},   // 活动4：开始时间5，结束时间7
45.         {3, 9, 5},   // 活动5：开始时间3，结束时间9
46.         {5, 9, 6},   // 活动6：开始时间5，结束时间9
47.         {6, 10, 7},  // 活动7：开始时间6，结束时间10
48.         {8, 11, 8},  // 活动8：开始时间8，结束时间11
49.         {8, 12, 9},  // 活动9：开始时间8，结束时间12
50.         {2, 14, 10}, // 活动10：开始时间2，结束时间14
51.         {12, 16, 11} // 活动11：开始时间12，结束时间16
52.     };
53.    
54.     int n = sizeof(activities) / sizeof(activities[0]);
55.     printf("共有 %d 个活动\n\n", n);
56.    
57.     // 调用贪心算法选择活动
58.     selectActivities(activities, n);
59.    
60.     return 0;
61. }

复制代码

复杂度分析：

• 时间复杂度：O(nlogn)，重要是排序的时间复杂度。
  
• 空间复杂度：O(1)，除了存储运动的数组外，只需要常数级的额外空间。
  

贪心战略精确性证明：
运动选择问题的贪心战略是选择竣事时间最早的运动，这一战略的精确性可以通过反证法证明：
假设最优解聚集为S，包罗k个运动，按竣事时间排序后为{a₁, a₂, …, aₖ}。如果a₁不是全部运动中竣事时间最早的运动，那么存在运动b，其竣事时间早于a₁。
我们可以用b更换S中的a₁，得到新的解聚集S’ = {b, a₂, …, aₖ}。由于b的竣事时间早于a₁，b不会与a₂, …, aₖ辩论，因此S’也是一个可行解，且|S’| = |S|。这分析选择竣事时间最早的运动不会导致最优解的丢失。
通过归纳法，可以证明每次选择当前竣事时间最早的、与已选运动不辩论的运动，终极能得到最优解。
应用场景：
运动选择问题在现实中有广泛应用，比方：

• 集会室安排：在有限的集会室中安排尽大概多的集会
  
• 课程表筹划：在固定教室中安排尽大概多的课程
  
• 使命调理：在单处置处罚器上安排尽大概多的使命
  

案例三：货仓选址问题

问题描述：在一条数轴上有N家市肆，它们的坐标分别为A1∼AN。现在需要在数轴上创建一家货仓，每天清晨，从货仓到每家市肆都要运送一车商品。为了进步服从，求把货仓建在那里，可以使得货仓到每家市肆的间隔之和最小。
贪心战略：将货仓建在全部市肆坐标的中位数位置。
代码实现：

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 比较函数，用于排序
5. int compare(const void* a, const void* b) {
6.     return (*(int*)a - *(int*)b);
7. }
9. // 计算距离之和的函数
10. int sum(int warehouse, int* shops, int n) {
11.     int totalDistance = 0;
12.     for (int i = 0; i < n; ++i) {
13.         totalDistance += abs(warehouse - shops[i]);
14.     }
15.     return totalDistance;
16. }
18. // 找到货仓位置的函数
19. int find(int* shops, int n) {
20.     // 将商店坐标排序
21.     qsort(shops, n, sizeof(int), compare);
23.     // 中位数位置
24.     int warehousePosition = shops[n / 2];
26.     return warehousePosition;
27. }
29. int main() {
30.     int n;
31.     printf("输入商店的数量：");
32.     scanf("%d", &n);
34.     int* shops = (int*)malloc(n * sizeof(int));
36.     printf("输入商店的坐标：");
37.     for (int i = 0; i < n; ++i) {
38.         scanf("%d", &shops[i]);
39.     }
41.     int pos = find(shops, n);
42.     int total = sum(pos, shops, n);
44.     printf("把货仓建在坐标 %d 处，使得货仓到每家商店的距离之和最小，为：%d\n", pos, total);
46.     free(shops);
48.     return 0;
49. }

复制代码

复杂度分析：

• 时间复杂度：O(nlogn)，重要是排序的时间复杂度。
  
• 空间复杂度：O(n)，需要存储n个市肆的坐标。
  

留意：这个问题的贪心战略是选择中位数位置，这是由于在一维数轴上，到各点间隔之和最小的位置就是这些点的中位数。
贪默算法的应用详解

霍夫曼编码

霍夫曼编码是一种变长编码方式，它根据字符出现的频率来筹划编码长度，频率高的字符利用较短的编码，频率低的字符利用较长的编码，从而到达压缩数据的目的。
贪心战略：每次选择两个频率最低的节点合并，构建一棵哈夫曼树，然后根据从根到叶子的路径确定编码。
最小天生树

最小天生树是连通无向图的一个天生树，其权值之和最小。常用的算法有：
Prim算法：

• 从图中任选一个极点作为起始点，参加到最小天生树中
  
• 在全部与当前最小天生树中极点相邻的边中，选择权值最小的边，将其毗连的未访问极点参加到最小天生树中
  
• 重复步骤2，直到全部极点都参加到最小天生树中
  

Kruskal算法：

• 将图中全部边按权值从小到大排序
  
• 按照权值从小到大的次序选择边，如果该边不会与已选择的边构成环路，则将其参加到最小天生树中
  
• 重复步骤2，直到选择了n-1条边（n为极点数）
  

Dijkstra最短路径算法

Dijkstra算法用于求解单源最短路径问题，即从一个极点到其余各极点的最短路径。
贪心战略：每次选择当前未访问的间隔出发点近来的极点，然后更新与该极点相邻的其他极点的间隔。
总结

贪默算法通过每一步的局部最优选择，期望得到全局最优解。实用于满意最优子布局和贪心选择性质的问题。常见应用有找零、运动选择、最小天生树、最短路径、霍夫曼编码等。现实应用时需验证贪心战略的精确性，由于贪默算法并不总是能得到全局最优解。