12.2 贪心回顾：每步做当前最优选择

核心问题：局部最优能否推出全局最优？
直觉：像登山时只看眼前最陡的路——希望一路走到顶峰，但可能只是走到一个小山坡。

一、问题情境：如何找到单源最短路径？

想象你是一个外卖骑手，需要从餐厅（起点）到多个客户地址（多个终点）。你希望：

先去最近的客户
然后从那个客户去下一个最近的
依次类推...

朴素方案：你先枚举所有可能的路径，然后找最短的。

python

# 朴素方案：枚举所有路径（时间爆炸）
def naive_shortest_path(graph, start, end):
    all_paths = enumerate_all_paths(graph, start, end)  # O(V!) 枚举所有路径
    shortest = min(all_paths, key=len)  # 找最短的
    return shortest

这个方案时间复杂度是O(V!)——图有20个节点时，需要2.4万亿次枚举！

思考：有没有更聪明的方法？

一个直觉浮现：每次选择当前距离最短的节点，先确定它的最短路径。

这就是贪心思想——Dijkstra算法的核心。

二、直觉引入：登山的智慧与陷阱

2.1 什么是贪心？

**贪心（Greedy）**的核心直觉是：

每一步都做当前最优的选择，希望累积成全局最优。

想象你在登山：

贪心策略：每步走眼前最陡的路（局部最优）
期望：一路走到顶峰（全局最优）
风险：可能走到局部山顶，而非最高峰

2.2 贪心成功与失败的对比

场景	贪心策略	结果
Dijkstra最短路径	每步选距离最小的未访问节点	✅ 成功找到最短路径
0-1背包问题	每次选性价比最高的物品	❌ 失败，可能非最优
分数背包问题	每次选性价比最高的物品（可分割）	✅ 成功找到最优解
找零钱（特殊币值）	每次选最大的不超过余额的硬币	✅ 成功
找零钱（一般币值）	同上	❌ 可能失败

关键差异：贪心何时成功？何时失败？

三、算法定义：贪心正确性条件

3.1 贪心成功的两个必要条件

贪心算法能保证最优解，需要两个条件同时成立：

条件	名称	含义
条件1	贪心选择性质	当前最优选择必然属于某个全局最优解
条件2	最优子结构	剩余问题的最优解 + 当前贪心选择 = 全局最优解

直观理解：

贪心选择性质：
"我现在选最好的，不会堵死更优解的路"

最优子结构：
"选完这个后，剩下的问题还是同样的问题，最优解的组合就是全局最优"

3.2 Dijkstra为何成功？

让我们用这两个条件分析Dijkstra：

条件1：贪心选择性质

当前最短距离的节点，其最短路径已经确定，不会再有更短路径。

证明：
设当前最短节点u，距离dist[u]。
假设存在更短路径到达u：
这条更短路径必然经过某个未访问节点v。
但dist[u] ≤ dist[v]（u是当前最短），矛盾。
所以dist[u]已是最短，贪心选择不会错。

条件2：最优子结构

确定了u的最短路径后，剩下的节点问题仍是最短路径问题。

形式化：
设S是已确定最短路径的节点集合。
对于未确定节点v：
dist[v] = min(dist[v], dist[u] + weight(u, v))
这仍是同样的最短路径问题，只是起点集合扩展了。

3.3 0-1背包为何失败？

问题：有n个物品，每个有价值和重量，背包容量有限，如何装入最大价值？

错误贪心策略：每次选性价比（价值/重量）最高的物品。

反例构造：

物品：
A：价值60，重量10，性价比6
B：价值100，重量20，性价比5
C：价值120，重量30，性价比4
背包容量：30

贪心选择：先选A（性价比最高）
剩余容量：20
再选B（性价比次高）
总价值：60 + 100 = 160

最优解：选C（性价比最低）
总价值：120

差距：160 > 120？不对！
重新检查：容量30
贪心：A(10) + B(20) = 30，价值160
最优：C(30) = 30，价值120

等等，贪心更好？再构造一个：
物品：
A：价值60，重量100，性价比0.6
B：价值100，重量200，性价比0.5  
C：价值120，重量300，性价比0.4
背包容量：300

贪心：A(100) + B(200)？容量不够A+B=300，价值160
或者：A(100) + C(300)？容量不够A+C=400
贪心实际：A(100) + 无法装B或C = 价值60

最优：B(200) + C(300)？容量500，不行
最优实际：C(300) = 价值120

差距：60 < 120，贪心失败！

失败原因：
贪心选了性价比最高的A，但A占用了100容量，
剩余200容量无法装性价比更低的B+C的组合（需要500容量）
但如果不选A，直接装C，价值更高。

失败分析：

贪心选择性质不成立：
选择性价比最高的物品，可能堵死更优组合的可能。

最优子结构不成立：
选完一个物品后，剩余问题不再是"同样的问题"
因为：背包容量减少，物品集合减少，且物品不可分割
 → 剩余问题依赖已选物品，不是独立的子问题

四、实现示例：Dijkstra教学化代码

4.1 Dijkstra完整实现

python

import heapq

def dijkstra(graph, start):
    """
    Dijkstra算法：贪心思想的经典实现
    
    思路：
    1. 维护已确定最短路径的节点集合S
    2. 每次选择距离最小的未确定节点加入S
    3. 更新其邻居的距离
    """
    # 初始化
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()
    # 优先队列：存储(距离, 节点)
    pq = [(0, start)]
    
    while pq:
        # 贪心选择：当前距离最小的节点
        current_dist, current_node = heapq.heappop(pq)
        
        # 已访问过则跳过
        if current_node in visited:
            continue
        
        # 加入已确定集合
        visited.add(current_node)
        
        # 更新邻居距离
        for neighbor, weight in graph[current_node]:
            if neighbor not in visited:
                new_dist = current_dist + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))
    
    return distances

# 测试
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 3, 'C': 2, 'D': 8}

4.2 代码背后的贪心思想

代码段	对应贪心步骤
`pq = [(0, start)]`	初始化：起点距离0
`heapq.heappop(pq)`	贪心选择：取当前最小距离节点
`visited.add(current_node)`	确定最短路径
`new_dist = current_dist + weight`	更新邻居距离
`heapq.heappush(pq, (new_dist, neighbor))`	加入候选集合

五、复杂度分析：时间与空间

5.1 时间复杂度

Dijkstra（优先队列实现）：O(V log V + E)

计算过程：
- 初始化：O(V)
- 每个节点加入S一次：O(V log V)（优先队列插入）
- 每条边更新一次：O(E log V)（优先队列插入）
总计：O(V log V + E log V) = O((V + E) log V)

简化：通常E > V，所以O(E log V)

对比朴素方案：

算法	时间复杂度	1000节点耗时
枚举所有路径（朴素）	O(V!)	天文数字（宇宙年龄级别）
Dijkstra（贪心）	O(E log V)	秒级

贪心让效率提升不可估量！

5.2 空间复杂度

Dijkstra：O(V)

空间使用：
- distances数组：O(V)
- visited集合：O(V)
- 优先队列：O(V)
总计：O(V)

六、与前章节关联：贪心在哪里出现过？

6.1 贪心前章节应用

章节	贪心应用	说明
Ch4	Dijkstra最短路径	贪心的经典成功案例
Ch7	Prim最小生成树	每步选最小边
Ch7	Kruskal最小生成树	每步选最小边（不形成环）
Ch3	Huffman编码	每步选最小频率合并
Ch8	近似算法	NP问题的贪心近似解

6.2 Huffman编码：贪心的另一成功案例

问题：给定字符频率，设计最优前缀编码。

贪心策略：每次选两个最小频率节点合并。

python

import heapq

def huffman_encode(frequencies):
    """
    Huffman编码：贪心构建最优编码树
    
    思路：
    1. 每次选两个最小频率节点
    2. 合并成新节点（频率=两节点之和）
    3. 重复直到只剩一个节点（根）
    """
    # 初始化优先队列
    heap = [(freq, char) for char, freq in frequencies.items()]
    heapq.heapify(heap)
    
    # 贪心合并
    while len(heap) > 1:
        freq1, char1 = heapq.heappop(heap)  # 贪心选择：最小频率
        freq2, char2 = heapq.heappop(heap)  # 贪心选择：次小频率
        new_freq = freq1 + freq2
        new_node = (new_freq, (char1, char2))  # 合并
        heapq.heappush(heap, new_node)
    
    return heap[0]  # 返回编码树根

# 测试
freqs = {'A': 45, 'B': 13, 'C': 12, 'D': 16, 'E': 9, 'F': 5}
tree = huffman_encode(freqs)
print(tree)  # (100, ((45, 'A'), ((25, ((12, 'C'), (13, 'B'))), (30, ((5, 'F'), (9, 'E'), (16, 'D'))))))

七、设计反思：贪心的失败模式

7.1 失败案例1：0-1背包问题（详细分析）

已在3.3节详细分析。

总结：贪心失败的本质原因是**"当前最优选择堵死了更优解的可能"**。

7.2 失败案例2：找零钱问题（一般币值）

问题：给定币值集合和目标金额，找最少硬币数。

贪心策略：每次选最大的不超过余额的硬币。

特殊币值时成功：

币值：1, 5, 10, 25（美币）
金额：67
贪心：25 + 25 + 10 + 5 + 1 + 1 = 6个硬币
最优：6个硬币（贪心正确）

一般币值时失败：

币值：1, 3, 4
金额：6
贪心：4 + 1 + 1 = 3个硬币
最优：3 + 3 = 2个硬币
贪心失败！

失败原因：

贪心选择性质不成立：
选最大的4，堵死了用3+3的可能性。

正确解法：动态规划

python

def coin_change_dp(coins, amount):
    """
    找零钱的DP解法
    
    状态：dp[i] = 凑成金额i的最少硬币数
    转移：dp[i] = min(dp[i - coin] + 1) for all coin <= i
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

7.3 失败案例总结：贪心的三陷阱

陷阱	现象	正确范式
当前最优堵死全局最优	贪心选择性质不成立	DP或回溯
子问题不独立	最优子结构不成立	DP
无法证明正确性	举出反例说明贪心失败	换范式

八、知识卡片

C12-09 贪心正确性证明

直觉解释：证明"每步局部最优"能保证"最终全局最优"。

核心内容：

证明方法	思路
交换论证	假设存在更优解，用贪心解替换必更优
归纳论证	归纳证明每步选择不劣

关键特征：贪心选择性质 + 最优子结构 = 贪心正确。

常见误解：

❌ 贪心能求最优解——需要严格证明！
✅ 正确理解：贪心正确需要两个条件成立

实例：活动选择问题——贪心选最早结束，用交换论证证明正确。

C12-10 贪心失败模式

直觉解释：每步选最好的，结果可能是最差的。

核心内容：失败原因——局部最优 ≠ 全局最优。

关键特征：当"当前最优"会"堵死后路"时，贪心失败。

常见误解：

❌ 能举出贪心失败的例子就说明贪心不行——要看具体问题
✅ 正确理解：贪心适用有严格条件，失败反例帮助理解边界

实例：0-1背包问题——贪心按性价比选可能非最优。

C12-11 贪心适用条件

直觉解释：贪心能用的两个"必须"。

核心内容：

贪心选择性质（局部最优必属于全局最优）
最优子结构（剩余问题的最优解组合成全局最优）

关键特征：无后效性——当前选择不影响未来选择的可能性。

常见误解：

❌ 满足一个条件就够了——两个条件必须同时成立
✅ 正确理解：两个条件缺一不可

实例：Dijkstra——满足贪心选择性质和最优子结构。

C12-12 贪心 vs DP

直觉解释：贪心是"不回头"，DP是"回头看所有可能"。

核心内容：

维度	贪心	DP
后效性	无后效性（当前不影响未来）	有后效性（需考虑所有状态转移）
选择	每步唯一选择	每步考虑所有可能转移

关键特征：贪心每步唯一选择；DP每步考虑所有可能转移。

常见误解：

❌ 贪心是DP的特例——错！贪心需要更强的条件
✅ 正确理解：贪心条件更严，但效率更高

实例：活动选择——贪心 O(n log n)；DP O(n²)，贪心更快但条件更严。

C12-13 贪心近似算法

直觉解释：NP-hard问题求精确解太难，贪心能给"差不多对"的解。

核心内容：贪心常用于NP问题近似解，保证近似比。

关键特征：近似比 = 贪心解 / 最优解（衡量偏离程度）。

常见误解：

❌ 近似算法就是贪心——还有其他方法（线性规划松弛）
✅ 正确理解：贪心是近似算法的一种

实例：集合覆盖问题——贪心近似比O(log n)，是目前最好的多项式算法。

C12-14 Huffman编码贪心

直觉解释：频率高的字符用短编码，频率低的用长编码。

核心内容：每次选两个最小频率节点合并，自底向上构建编码树。

关键特征：贪心策略——选最小频率节点优先合并。

常见误解：

❌ Huffman编码总是最优前缀码——对固定长度编码块是最优
✅ 正确理解：Huffman是固定块长度的最优前缀码

实例：字符频率A(45%), B(13%), C(12%)，贪心建树得最优编码。

C12-15 贪心直觉建立

直觉解释：看到"每步选当前最好"，想贪心能否成立。

核心内容：判断贪心适用的直觉问题——每步最优能推导全局最优吗？

关键特征：关键是"无后效性"——当前选择不限制未来最优解的可能性。

常见误解：

❌ 贪心简单所以先试贪心——应该先判断是否满足条件
✅ 正确理解：先验证贪心条件，再应用贪心

实例：Dijkstra的直觉——已确定的最短路径不会再更新（无后效性）。

C12-16 贪心反例构造

直觉解释：构造让贪心"翻车"的例子，理解贪心的边界。

核心内容：反例构造技巧——找到让局部最优≠全局最优的情况。

关键特征：让"贪心选择"堵死"更优解"的可能。

常见误解：

❌ 贪心失败要随机找反例——反例构造有技巧
✅ 正确理解：系统性地构造"堵死更优解"的情况

实例：0-1背包反例——物品性价比高但占用容量堵死更优组合。

九、练习设计

基础练习（理解贪心）

练习 12.2-1：用交换论证证明活动选择问题的贪心正确性。

提示：

活动选择问题：
给定n个活动（开始时间、结束时间），选最多不重叠的活动。

贪心策略：每次选结束时间最早的活动。

交换论证：
设贪心解G选了活动{g₁, g₂, ..., gₖ}，按结束时间排序。
设最优解OPT选了活动{o₁, o₂, ..., oₘ}，m ≥ k。

Step 1: g₁是结束最早的，所以g₁ ≤ o₁（结束时间）
Step 2: 将OPT的o₁替换为g₁
        → OPT仍可行（因为g₁结束更早，不冲突）
Step 3: 重复替换，每次都将OPT的当前活动替换为G的对应活动
最终：OPT = G，且G也是最优解 ✓

练习 12.2-2：分析为何Dijkstra不能处理负边。

答案：

反例：
图：A→B(权重-2)，A→C(权重4)，C→B(权重1)

Dijkstra从A出发：
- 先选B（距离-2，贪心认为已确定）
- 但实际存在A→C→B路径，距离4+1=5 > -2？

问题：负边破坏了"当前最短节点已确定"的前提。
因为存在负边时，可能通过未访问节点找到更短路径。

正确解法：Bellman-Ford（DP），复杂度O(VE)

进阶练习（贪心应用）

练习 12.2-3：设计贪心算法解决区间调度问题（选最多不重叠区间）。

思路：

贪心策略：按结束时间排序，每次选第一个不与已选区间重叠的。

证明：
交换论证（同活动选择问题）。

复杂度：
排序：O(n log n)
选择：O(n)
总计：O(n log n)

设计练习（贪心 vs DP）

练习 12.2-4：对比贪心和DP在"分数背包问题"上的解法。

分析：

分数背包问题：物品可分割。

贪心解法：
按性价比排序，优先选性价比高的，装满为止。
正确！因为物品可分割，不存在"堵死更优解"的问题。

DP解法：
dp[i][w] = 前i个物品容量w的最大价值
转移：dp[i][w] = max(dp[i-1][w], dp[i-1][w-k] + k*value[i])
其中k是装入物品i的量（0≤k≤weight[i]）

贪心O(n log n)优于DP O(nW)，且正确性有保证。

开放练习

练习 12.2-5：LLM的token-by-token生成是否是贪心过程？

思考方向：

LLM生成：
每步选择概率最高的token（贪心）
或采样（引入随机性）

贪心生成的问题：
- 可能生成重复、枯燥的文本
- 可能陷入局部最优（如"我很开心很开心很开心..."）

改进：
- Beam Search：保留top-k候选（类似DP）
- Temperature采样：引入随机性
- Top-k/Top-p采样：限制候选集合

LLM生成展示了贪心的局限：
贪心追求"局部最优token"，但可能非"全局最优文本"

导航：上一节：12.1 分治回顾 | 下一节：12.3 动态规划回顾 →

12.2 贪心回顾：每步做当前最优选择 ​

一、问题情境：如何找到单源最短路径？ ​

二、直觉引入：登山的智慧与陷阱 ​

2.1 什么是贪心？ ​

2.2 贪心成功与失败的对比 ​

三、算法定义：贪心正确性条件 ​

3.1 贪心成功的两个必要条件 ​

3.2 Dijkstra为何成功？ ​

3.3 0-1背包为何失败？ ​

四、实现示例：Dijkstra教学化代码 ​

4.1 Dijkstra完整实现 ​

4.2 代码背后的贪心思想 ​

五、复杂度分析：时间与空间 ​

5.1 时间复杂度 ​

5.2 空间复杂度 ​

六、与前章节关联：贪心在哪里出现过？ ​

6.1 贪心前章节应用 ​

6.2 Huffman编码：贪心的另一成功案例 ​

七、设计反思：贪心的失败模式 ​

7.1 失败案例1：0-1背包问题（详细分析） ​

7.2 失败案例2：找零钱问题（一般币值） ​

7.3 失败案例总结：贪心的三陷阱 ​

八、知识卡片 ​

C12-09 贪心正确性证明 ​

C12-10 贪心失败模式 ​

C12-11 贪心适用条件 ​

C12-12 贪心 vs DP ​

C12-13 贪心近似算法 ​

C12-14 Huffman编码贪心 ​

C12-15 贪心直觉建立 ​

C12-16 贪心反例构造 ​

九、练习设计 ​

基础练习（理解贪心） ​

进阶练习（贪心应用） ​

设计练习（贪心 vs DP） ​

开放练习 ​

12.2 贪心回顾：每步做当前最优选择

一、问题情境：如何找到单源最短路径？

二、直觉引入：登山的智慧与陷阱

2.1 什么是贪心？

2.2 贪心成功与失败的对比

三、算法定义：贪心正确性条件

3.1 贪心成功的两个必要条件

3.2 Dijkstra为何成功？

3.3 0-1背包为何失败？

四、实现示例：Dijkstra教学化代码

4.1 Dijkstra完整实现

4.2 代码背后的贪心思想

五、复杂度分析：时间与空间

5.1 时间复杂度

5.2 空间复杂度

六、与前章节关联：贪心在哪里出现过？

6.1 贪心前章节应用

6.2 Huffman编码：贪心的另一成功案例

七、设计反思：贪心的失败模式

7.1 失败案例1：0-1背包问题（详细分析）

7.2 失败案例2：找零钱问题（一般币值）

7.3 失败案例总结：贪心的三陷阱

八、知识卡片

C12-09 贪心正确性证明

C12-10 贪心失败模式

C12-11 贪心适用条件

C12-12 贪心 vs DP

C12-13 贪心近似算法

C12-14 Huffman编码贪心

C12-15 贪心直觉建立

C12-16 贪心反例构造

九、练习设计

基础练习（理解贪心）

进阶练习（贪心应用）

设计练习（贪心 vs DP）

开放练习