【漫话机器学习系列】066.贪心算法（Greedy Algorithms）
贪心算法（Greedy Algorithms）
贪心算法是一种逐步构建解决方案的算法，每一步都选择当前状态下最优的局部选项（即“贪心选择”），以期望最终获得全局最优解。贪心算法常用于解决最优化问题。
核心思想
-
贪心选择性质
在每一步选择中，通过选择当前的局部最优解，能够保证最终得到的解是全局最优解。 -
无后效性（No Backtracking）
当前步骤的选择不会影响之后的选择，即一个问题的解决可以通过局部的选择逐步逼近全局最优。 -
最优子结构性质
一个问题的全局最优解可以通过其子问题的最优解组合得到。
贪心算法的一般步骤
- 问题分解：将问题分解为若干个子问题。
- 选择策略：为每一步定义贪心选择规则（如最大化或最小化）。
- 验证解的可行性：每一步选定的解需满足问题的约束条件。
- 检查最优性：选择的局部解是否能保证全局最优。
- 重复直到完成：重复贪心选择直至问题结束。
常见应用场景
-
活动选择问题（Activity Selection Problem）
给定多个活动的开始和结束时间，选择最大数量的活动使得它们互不重叠。 -
背包问题（Knapsack Problem, 分数背包）
在分数背包问题中，按单位重量价值排序，并优先选择单位价值最高的物品。 -
最小生成树（Minimum Spanning Tree）
- Prim 算法
- Kruskal 算法
-
最短路径问题（Shortest Path Problem）
- Dijkstra 算法
-
哈夫曼编码（Huffman Encoding）
用于生成最优前缀编码，减少数据压缩的存储空间。
优点
- 简单直观：易于实现，且解决问题的过程清晰。
- 高效：通过贪心选择，通常只需线性或接近线性的时间复杂度。
- 适用范围广：许多经典问题都能用贪心算法求解。
缺点
- 局部最优≠全局最优
在某些问题中，贪心算法无法保证全局最优解。- 例如：0-1 背包问题的全局最优解通常无法通过贪心法获得。
- 适用性有限
只有具有最优子结构性质和贪心选择性质的问题才能用贪心算法。
代码示例：活动选择问题
给定活动的开始和结束时间，选择最多数量的活动，使其不重叠。
def activity_selection(start_times, end_times):
activities = sorted(zip(start_times, end_times), key=lambda x: x[1]) # 按结束时间排序
selected = []
last_end_time = 0
for start, end in activities:
if start >= last_end_time: # 当前活动的开始时间不早于上一个选择活动的结束时间
selected.append((start, end))
last_end_time = end
return 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)]
总结
贪心算法通过逐步构建解决方案，在每一步都选择当前状态下的最优选项，是解决许多经典最优化问题的强大工具。但在应用贪心算法时，需要验证问题是否满足最优子结构和贪心选择性质，否则可能无法得到正确结果。