【漫话机器学习系列】066.贪心算法（Greedy Algorithms）

贪心算法（Greedy Algorithms）

贪心算法是一种逐步构建解决方案的算法，每一步都选择当前状态下最优的局部选项（即“贪心选择”），以期望最终获得全局最优解。贪心算法常用于解决最优化问题。

---

核心思想

1. 贪心选择性质
   在每一步选择中，通过选择当前的局部最优解，能够保证最终得到的解是全局最优解。

2. 无后效性（No Backtracking）
   当前步骤的选择不会影响之后的选择，即一个问题的解决可以通过局部的选择逐步逼近全局最优。

3. 最优子结构性质
   一个问题的全局最优解可以通过其子问题的最优解组合得到。

---

贪心算法的一般步骤

1. 问题分解：将问题分解为若干个子问题。
2. 选择策略：为每一步定义贪心选择规则（如最大化或最小化）。
3. 验证解的可行性：每一步选定的解需满足问题的约束条件。
4. 检查最优性：选择的局部解是否能保证全局最优。
5. 重复直到完成：重复贪心选择直至问题结束。

---

常见应用场景

1. 活动选择问题（Activity Selection Problem）
   给定多个活动的开始和结束时间，选择最大数量的活动使得它们互不重叠。

2. 背包问题（Knapsack Problem, 分数背包）
   在分数背包问题中，按单位重量价值排序，并优先选择单位价值最高的物品。

3. 最小生成树（Minimum Spanning Tree）

   • Prim 算法
   • Kruskal 算法

4. 最短路径问题（Shortest Path Problem）

   • Dijkstra 算法

5. 哈夫曼编码（Huffman Encoding）
   用于生成最优前缀编码，减少数据压缩的存储空间。

---

优点

1. 简单直观：易于实现，且解决问题的过程清晰。
2. 高效：通过贪心选择，通常只需线性或接近线性的时间复杂度。
3. 适用范围广：许多经典问题都能用贪心算法求解。

---

缺点

1. 局部最优≠全局最优
   在某些问题中，贪心算法无法保证全局最优解。
   • 例如：0-1 背包问题的全局最优解通常无法通过贪心法获得。
2. 适用性有限
   只有具有最优子结构性质和贪心选择性质的问题才能用贪心算法。

---

代码示例：活动选择问题

给定活动的开始和结束时间，选择最多数量的活动，使其不重叠。

def activity_selection(start_times, end_times):activities = sorted(zip(start_times, end_times), key=lambda x: x[1])  # 按结束时间排序selected = []last_end_time = 0for start, end in activities:if start >= last_end_time:  # 当前活动的开始时间不早于上一个选择活动的结束时间selected.append((start, end))last_end_time = endreturn selected# 示例
start_times = [1, 3, 0, 5, 8, 5]
end_times = [2, 4, 6, 7, 9, 9]
result = activity_selection(start_times, end_times)
print("选择的活动：", result)

运行结果 

选择的活动： [(1, 2), (3, 4), (5, 7), (8, 9)]

 

---

总结

贪心算法通过逐步构建解决方案，在每一步都选择当前状态下的最优选项，是解决许多经典最优化问题的强大工具。但在应用贪心算法时，需要验证问题是否满足最优子结构和贪心选择性质，否则可能无法得到正确结果。