青少年编程与数学 02-016 Python数据结构与算法 16课题、贪默算法

课题择要:
贪默算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而渴望导致效果是全局最优的算法。贪默算法并不总是能得到最优解，但它在许多题目上都能得到较好的近似解，而且通常具有较高的服从。
    关键词：贪默算法
  

---

一、贪默算法的根本概念

界说

贪默算法在每一步选择中都采取当前状态下最优的选择，从而渴望导致效果是全局最优的。这种“最优”通常是根据某种局部标准来权衡的。
构成部分

• 贪婪选择性子：题目标团体最优解可以通过一系列局部最优的选择来到达。这是贪默算法可行的根本要素。
  
• 最优子结构：题目标最优解包罗其子题目标最优解。贪默算法通太过解题目为更小的子题目来渐渐构建全局最优解。
  
• 贪婪策略：一种用于选择局部最优解的策略，通常基于某种特定的规则或标准。
  

二、贪默算法的工作原理

• 贪婪选择：在每一步选择中，根据某种贪婪策略选择当前状态下最优的选项。比方，在找零题目中，每次选择面值最大的硬币。
  
• 构建解：通过一系列的贪婪选择渐渐构建解。每一步的选择都是基于当前状态的最优选择，而不考虑后续步调。
  
• 验证：在某些环境下，必要验证通过贪婪选择得到的解是否满意题目标约束条件。假如满意，则该解是全局最优解；假如不满意，则必要重新考虑贪婪策略。
  

三、贪默算法的长处

• 简朴直观：贪默算法的逻辑通常比力简朴，容易明白和实现。
  
• 服从高：贪默算法通常具有较高的服从，由于它不必要像动态规划那样存储大量的子题目解。
  
• 实用性广：贪默算法可以应用于多种题目，尤其是在组合优化题目中。
  

四、贪默算法的缺点

• 不能包管全局最优：贪默算法只能包管在每一步选择中是局部最优的，但不能包管最闭幕果是全局最优的。比方，在某些背包题目中，贪默算法大概无法找到最优解。
  
• 实用范围有限：贪默算法只能应用于具有贪婪选择性子和最优子结构的题目。对于不满意这些条件的题目，贪默算法大概无法得到精确的解。
  

五、贪默算法的应用实例

（一）找零题目

题目形貌：给定一组硬币面值和一个金额，求用最少的硬币数凑成该金额。
贪婪策略：每次选择面值最大的硬币。
示例代码：

1. def coin_change(coins, amount):
2.     coins.sort(reverse=True)
3.     count = 0
4.     for coin in coins:
5.         while amount >= coin:
6.             amount -= coin
7.             count += 1
8.     return count if amount == 0 else -1

复制代码

表明：每次选择面值最大的硬币，直到金额为0。
（二）活动安排题目

题目形貌：给定一组活动的开始时间和竣事时间，求最多可以安排多少个不辩说的活动。
贪婪策略：每次选择竣事时间最早的活动。
示例代码：

1. def activity_selection(start, finish):
2.     activities = sorted(zip(start, finish), key=lambda x: x[1])
3.     count = 0
4.     last_finish = 0
5.     for activity in activities:
6.         if activity[0] >= last_finish:
7.             count += 1
8.             last_finish = activity[1]
9.     return count

复制代码

表明：每次选择竣事时间最早的活动，确保后续活动不辩说。
（三）霍夫曼编码

题目形貌：给定一组字符及其频率，求一种最优的编码方式，使得编码后的字符串长度最短。
贪婪策略：每次选择频率最小的两个字符归并。
示例代码：

1. import heapq
3. class Node:
4.     def __init__(self, char, freq):
5.         self.char = char
6.         self.freq = freq
7.         self.left = None
8.         self.right = None
10.     def __lt__(self, other):
11.         return self.freq < other.freq
13. def huffman_encoding(frequencies):
14.     heap = [Node(char, freq) for char, freq in frequencies.items()]
15.     heapq.heapify(heap)
16.     while len(heap) > 1:
17.         left = heapq.heappop(heap)
18.         right = heapq.heappop(heap)
19.         merged = Node(None, left.freq + right.freq)
20.         merged.left = left
21.         merged.right = right
22.         heapq.heappush(heap, merged)
23.     return heap[0]
25. def build_codes(root, prefix="", code={}):
26.     if root is None:
27.         return
28.     if root.char is not None:
29.         code[root.char] = prefix
30.     build_codes(root.left, prefix + "0", code)
31.     build_codes(root.right, prefix + "1", code)
32.     return code
34. frequencies = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
35. root = huffman_encoding(frequencies)
36. codes = build_codes(root)
37. print(codes)

复制代码

表明：通过构建霍夫曼树，为每个字符分配最优的编码。
（四）最小天生树（Kruskal算法）

题目形貌：给定一个加权无向图，求一个最小天生树。
贪婪策略：每次选择权重最小的边，确保不形成环。
示例代码：

1. class UnionFind:
2.     def __init__(self, n):
3.         self.parent = list(range(n))
5.     def find(self, x):
6.         if self.parent[x] != x:
7.             self.parent[x] = self.find(self.parent[x])
8.         return self.parent[x]
10.     def union(self, x, y):
11.         rootX = self.find(x)
12.         rootY = self.find(y)
13.         if rootX != rootY:
14.             self.parent[rootX] = rootY
16. def kruskal(edges, n):
17.     edges.sort(key=lambda x: x[2])
18.     uf = UnionFind(n)
19.     mst = []
20.     for u, v, weight in edges:
21.         if uf.find(u) != uf.find(v):
22.             uf.union(u, v)
23.             mst.append((u, v, weight))
24.     return mst
26. edges = [(0, 1, 2), (1, 2, 3), (2, 3, 1), (3, 0, 4), (0, 2, 5)]
27. n = 4
28. print(kruskal(edges, n))

复制代码

表明：通过选择权重最小的边，渐渐构建最小天生树。
总结

贪默算法是一种简朴而高效的算法计划策略，实用于具有贪婪选择性子和最优子结构的题目。它通过在每一步选择中采取当前状态下最优的选择，渐渐构建解。固然贪默算法不能包管总是得到全局最优解，但在许多现实题目中都能得到较好的近似解。在利用贪默算法时，必要仔细分析题目标性子，确保贪婪策略的有效性。