第一章 人工智能基础
第三部分：算法分析与设计
第四节：贪心算法
内容：贪心选择性质，常见贪心算法（如活动选择问题、最小生成树）的分析。
一、贪心算法的定义
贪心算法是一种在每一步选择中都采取当前状态下最优解（即最有利）的策略，从而希望通过局部最优达到全局最优。
二、贪心算法的两个核心性质
-
贪心选择性质
—— 全局最优解可以通过一系列局部最优选择构成。 -
最优子结构性质
—— 问题的最优解包含其子问题的最优解。
并非所有问题都适合用贪心算法求解，通常需先证明这两个性质是否成立。
三、常见贪心算法实例
1. 活动选择问题（Activity Selection Problem）
问题描述：
给定 n 个活动，每个活动有起始时间 start[i] 和结束时间 end[i]，要求在时间上互不重叠的前提下，选择最多数量的活动。
贪心策略：
按照结束时间从早到晚排序，每次选择第一个结束时间最早且与当前已选活动不冲突的活动。
示例代码：
def activity_selection(activities):# activities: [(start, end), ...]activities.sort(key=lambda x: x[1]) # 按结束时间排序selected = [activities[0]]last_end = activities[0][1]for act in activities[1:]:if act[0] >= last_end:selected.append(act)last_end = act[1]return selected
2. 最小生成树（Minimum Spanning Tree，MST）
构建一棵连接图中所有节点、边权和最小的树。经典贪心算法：
-
Prim算法：每次选择连接“已选顶点”与“未选顶点”之间的最小边。
-
Kruskal算法：将边按权值升序排序，逐条加入图中，若不构成环则保留。
Kruskal 示例代码：
def kruskal(n, edges):parent = list(range(n))def find(u):while u != parent[u]:parent[u] = parent[parent[u]]u = parent[u]return umst = []edges.sort(key=lambda x: x[2]) # edges: (u, v, weight)for u, v, w in edges:ru, rv = find(u), find(v)if ru != rv:parent[ru] = rvmst.append((u, v, w))return mst
四、贪心算法的适用场景
适合满足以下条件的问题：
-
子问题结构相互独立
-
总体最优包含局部最优
-
每一步的最优选择不影响后续结果最优性
典型应用包括：
-
区间调度
-
Huffman编码
-
零钱找零（在某些币值组合中不适用）
-
网络连通优化（最小生成树）
总结
| 特点 | 内容 |
|---|---|
| 思想 | 每一步都选择当前最优策略 |
| 优点 | 简单、效率高（常为 O(n log n)） |
| 缺点 | 不一定总是最优解 |
| 适用场景 | 具有贪心选择性质和最优子结构的问题 |
| 常见算法 | 活动选择、最小生成树、区间覆盖、任务调度、背包问题（部分） |
