第5章：贪心的诱惑（局部最优）
兔狲教授的亲切开场
在探索了彻底搜索与智能搜索之后，我们面对一个新的问题：如何做连续的决策？ 当我们面对一系列选择时，应该步步为营还是放眼全局？今天，我们探索贪心的智慧与局限。
核心议题：连续决策的策略是什么？
康乐园的午后，珠江的微风吹进黑石屋书房，带着夏初的温热。窗外的榕树新叶已经变得深绿，知了开始断断续续地鸣叫。兔狲教授正在整理茶具，准备泡一壶新的凤凰单丛。
小小猪从钱包里掏出几枚硬币，在桌上摆弄着。"教授，如果我要付8块钱，有1元、3元、5元的硬币，怎么用最少的硬币凑出来？"
小海豹放下手中的《博弈论导论》，"这个问题很有意思。如果每次都选最大面额，5+1+1+1=8，用了4个硬币。但3+3+1+1也用了4个硬币，3+5也是8元，只要2个硬币！"
兔狲教授微笑道："你们提出了一个很好的问题。当我们面对一系列决策时——无论是凑零钱、安排活动，还是规划路线——应该采用什么策略？"
小小猪不假思索，"每次选最大的硬币呗！这样用的硬币最少！"
"这就是贪心算法的思想，"兔狲教授点头，"在每一步都做出当前看起来最好的选择。但你们的例子已经显示了问题：有时候，局部最优并不导向全局最优。"
小海豹思考片刻，"所以贪心算法是短视的？只看到眼前利益，不考虑长远后果？"
"可以这么说，"兔狲教授说，"但今天我们要探索的核心议题是：连续决策的策略是什么？ 更具体地说：局部最优的选择何时能导向全局最优？"
他走到白板前，写下两个概念：
局部最优 —— 全局最优
"贪心算法的核心假设是，"兔狲教授解释，"一系列局部最优选择能导向全局最优解。但这个假设并不总是成立。今天我们要探索：它何时成立？为何成立？何时失败？为何失败？"
贪心算法的形式：选择与证明
"让我们先形式化贪心算法，"兔狲教授在白板上写出一般框架：
def greedyAlgorithm(problem):
solution = emptySet()
while problem not solved:
# 选择当前最优的候选
candidate = selectBestCandidate(problem.candidates)
# 检查候选是否可行（满足约束）
if feasible(solution + candidate):
solution.add(candidate)
problem.update(candidate) # 更新问题状态
return solution"贪心算法有四个关键组件，"兔狲教授解释：
- 候选集：每一步可供选择的选项
- 选择函数：从候选集中选择"最好"的选项
- 可行性检查：检查选择是否满足约束
- 问题更新：选择后更新问题状态
小小猪问："'最好'怎么定义？不同的选择函数会导致不同的结果吧？"
"正是，"兔狲教授说，"选择函数的定义决定了贪心算法的行为。比如在凑零钱问题中：
- 最大面额优先：总是选不超过剩余金额的最大面额硬币
- 最小硬币优先：总是选最小的硬币
- 价值密度优先：如果硬币有不同价值（如收藏价值）
"不同的选择函数可能导致不同的结果，有的导向全局最优，有的则不然。"
活动安排问题：贪心成功案例
小海豹说："我记得活动安排问题中，贪心算法是有效的。选择结束时间最早的活动，总能得到最大兼容活动集。"
"是的，"兔狲教授在白板上写出活动安排问题：
问题：有n个活动，每个活动有开始时间sᵢ和结束时间fᵢ。选择最大数量的互不重叠活动。
贪心算法：
1. 按结束时间升序排序活动
2. 选择第一个活动（结束最早）
3. 对于后续每个活动：
如果开始时间 ≥ 当前选中活动的结束时间：
选择该活动"这个算法的正确性需要证明，"兔狲教授说，"证明贪心选择性质：总是存在一个最优解包含结束最早的活动。"
兔狲教授的评语
活动安排问题的贪心算法成功，是因为它具有贪心选择性质和最优子结构。这两个性质是贪心算法正确性的关键。当一个问题同时具备这两个性质时，贪心策略是有效的。
背包问题的失败：贪心的局限
"现在看一个贪心失败的例子，"兔狲教授说，"0-1背包问题。"
问题：有n件物品，每件物品有重量wᵢ和价值vᵢ，背包容量为W。选择物品使得总价值最大，总重量不超过W。
小小猪尝试："贪心策略：每次选价值最大的物品？"
"试试看，"兔狲教授举例，"假设背包容量W=50，物品：
- 重量50，价值100（价值密度2）
- 重量30，价值60（价值密度2）
- 重量30，价值60（价值密度2）
"如果贪心选价值最大：先选物品1（价值100），但重量已满，总价值100。 "但最优解是选物品2和3：总重量60（超重？等等需要调整）……"
小海豹纠正："重量30+30=60超重了。应该：物品2重量30价值60，物品3重量30价值60，总重量60超了。"
兔狲教授重新举例："设W=50，物品：
- 重量30，价值60（密度2）
- 重量20，价值40（密度2）
- 重量20，价值39（密度1.95）
"贪心选价值密度最高：先选物品1（密度2），再选物品2（密度2），总重量50，总价值100。 "但最优解是：物品2+物品3，总重量40，总价值79？不对，应该比100小……"
小小猪说："等等，这个例子中贪心好像是最优的？"
兔狲教授点头："我需要一个更好的例子。经典的反例是：W=6，物品：
- 重量5，价值5（密度1）
- 重量3，价值4（密度1.33）
- 重量3，价值4（密度1.33）
"贪心选密度最高：先选物品2（价值4，剩余容量3），再选物品3（价值4，总价值8）。 "但最优解是：只选物品1（价值5）。等等，8>5，贪心更好？"
小海豹思考："W=6，物品2+3重量6价值8，物品1重量5价值5。贪心确实更好。经典反例需要物品价值不是按密度单调的……"
兔狲教授微笑："你们发现了关键。0-1背包问题的贪心策略（按价值密度排序）不是总能得到最优解，但需要精心构造反例。这也是贪心算法有趣的地方：它经常得到近似最优解，但不是绝对最优。"
进阶科普：贪心算法的正确性证明
贪心算法的正确性通常需要证明两个性质：
贪心选择性质（Greedy Choice Property）： 存在一个最优解包含当前的贪心选择。
证明方法：假设存在最优解不包含贪心选择，可以修改这个解，用贪心选择替换某个元素，得到另一个至少同样好的解。
最优子结构（Optimal Substructure）： 问题的最优解包含其子问题的最优解。
证明方法：如果原问题的最优解可以分解为子问题的最优解的组合，则问题具有最优子结构。
以活动安排问题为例：
- 贪心选择性质：总是存在一个最优解包含结束最早的活动
- 最优子结构：选择活动a后，剩余问题是在a结束后开始的活动集合中选择最大兼容集
当一个问题同时具备这两个性质时，贪心算法能得到全局最优解。否则，贪心只能得到近似解。
正交计算图：看见贪心的决策流
兔狲教授打开投影仪，一幅规整的计算图出现在屏幕上。
"这是贪心算法的正交计算图，"兔狲教授指着图说，"输入问题实例，经过选择函数、可行性检查、问题更新，循环直至问题解决。"
小小猪盯着图，"这个图是循环的！选择→检查→更新→再选择……像一个决策循环。"
"正是，"兔狲教授说，"贪心算法的核心是一个决策循环：在每一步，基于当前状态选择最优候选，更新状态，继续下一轮选择。这个循环结构反映了贪心算法的短视性——它只看到当前状态，不回头修改之前的选择。"
小海豹仔细观察图的层级结构，"教授，这个图的设计……选择函数、可行性检查、问题更新在同一循环层级，但每次循环后问题状态改变，候选集更新。"
"这就是贪心算法的动态性，"兔狲教授解释，"虽然算法结构是循环的，但每次循环面对的是更新的问题状态。这种状态依赖的选择是贪心算法的特点，也是其局限——一旦做出选择，就不能撤销。"
思想模型：局部最优与全局最优的张力
兔狲教授回到座位，喝了口茶。"让我们总结今天最重要的思想模型：局部最优与全局最优的张力。"
他在白板上画出对比表：
| 特征 | 局部最优（贪心视角） | 全局最优（优化视角） |
|---|---|---|
| 决策视野 | 短视，只看当前步骤 | 长远，考虑所有步骤 |
| 计算代价 | 低，每步简单选择 | 高，可能需要穷举或复杂优化 |
| 解的质量 | 可能次优，但通常不错 | 保证最优（如果可计算） |
| 适用场景 | 大规模问题、实时决策 | 小规模问题、关键决策 |
| 哲学意涵 | 满意即可，接受不完美 | 追求完美，不惜代价 |
"这两种视角不是对立的，"兔狲教授解释，"而是连续谱上的两个端点。实际问题中，我们常常在两者之间寻找平衡。"
贪心策略的适用条件
小海豹问："教授，什么样的问題适合用贪心算法？"
兔狲教授在白板上列出条件：
适合贪心算法的问题通常具有：
1. **贪心选择性质**：局部最优选择导向全局最优
2. **最优子结构**：问题可分解为相似子问题
3. **无后效性**：当前选择不影响未来选择的可行性（或影响可预测）
4. **计算效率要求**：需要快速决策，可接受近似解
常见贪心适用问题：
├── 活动安排问题（结束时间最早）
├── 霍夫曼编码（频率最小优先）
├── 最小生成树（Kruskal/Prim算法）
├── 单源最短路径（Dijkstra算法，非负权重）
└── 分数背包问题（价值密度最高优先）"理解这些条件，"兔狲教授说，"帮助我们判断何时可以'贪心'，何时需要更复杂的策略。"
兔狲教授的评语
贪心算法的哲学是满意原则（Satisficing）而非最优原则（Optimizing）。它不追求绝对的最好，而是在可接受时间内找到足够好的解。这种思维方式在许多现实决策中很有用——无论是个人生活规划、商业策略制定，还是算法设计。
关键要点
兔狲教授的总结：连续决策的贪心智慧
- 贪心算法框架：在每一步选择当前最优候选，循环直至问题解决，体现短视但高效的决策风格
- 正确性条件：贪心选择性质 + 最优子结构 = 全局最优保证；缺少任一条件则只能得到近似解
- 适用场景识别：活动安排、最小生成树、霍夫曼编码等问题适合贪心；背包问题、旅行商问题等需要更复杂策略
- 局部与全局的张力：贪心算法体现了局部最优与全局最优之间的永恒张力，提醒我们决策视野的重要性
- 实践智慧：当问题具有贪心性质时，贪心算法是简洁优美的解；当不具备时，贪心是快速但可能次优的启发式
代码实践：贪心算法的Python实现
"让我们用代码来探索贪心算法的魅力与局限，"兔狲教授说，"从硬币找零到活动安排，从成功案例到失败反例。"
贪心算法通用框架
def greedy_algorithm_template(candidates, selection_rule, feasibility_check):
"""贪心算法通用模板
问题描述:
从候选集合中选择一个子集，满足某些约束条件，并优化某个目标。
算法思路（贪心策略）:
1. 初始化空解
2. 当候选集合非空时循环：
a. 使用选择规则从候选集中选出当前最优的候选
b. 检查该候选加入当前解是否可行
c. 如果可行，将其加入解中
d. 从候选集中移除该候选
3. 返回最终解
关键特点:
- 每一步都做出局部最优选择
- 不回溯，不重新考虑已做的选择
- 高效但可能不是全局最优
- 适用于具有贪心选择性质的问题
贪心选择性质:
一个问题的全局最优解可以通过一系列局部最优选择得到。
即：每一步的局部最优选择能导向全局最优解。
参数:
candidates: 候选集合（列表、集合等可迭代对象）
selection_rule: 选择函数，接收候选集合，返回当前最优候选
feasibility_check: 可行性检查函数，接收当前解和候选，返回布尔值
返回:
贪心解（列表形式）
时间复杂度: 取决于选择规则和可行性检查的复杂度
空间复杂度: O(n) - 存储解和候选集合
示例（活动安排问题）:
>>> activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
>>> # 选择规则：选择结束时间最早的活动
>>> def select_earliest_end(candidates):
... return min(candidates, key=lambda x: x[1])
>>> # 可行性检查：活动开始时间不早于上一个活动的结束时间
>>> def is_feasible(solution, candidate):
... if not solution:
... return True
... return candidate[0] >= solution[-1][1]
>>> greedy_algorithm_template(activities, select_earliest_end, is_feasible)
[(1, 4), (5, 7), (8, 11), (12, 16)]
适用问题类型:
- 活动安排问题（选择最多互不冲突的活动）
- 霍夫曼编码（构建最优前缀码）
- 最小生成树（Prim、Kruskal算法）
- 硬币找零问题（特定面额下）
- 任务调度问题
"""
solution = []
remaining_candidates = candidates.copy()
while remaining_candidates:
# 选择当前最优候选
best_candidate = selection_rule(remaining_candidates)
# 检查是否可行
if feasibility_check(solution, best_candidate):
solution.append(best_candidate)
# 移除已处理的候选
remaining_candidates.remove(best_candidate)
return solution硬币找零问题
def greedy_coin_change(amount, coins):
"""贪心硬币找零算法
问题描述:
给定一个金额和一组硬币面额，找出使用最少硬币凑出该金额的方法。
假设每种硬币数量无限。
算法思路（贪心策略）:
1. 将硬币面额按降序排列（确保每次选择最大面额）
2. 对于每种面额的硬币：
a. 计算最多可以使用多少个这种硬币（不超过剩余金额）
b. 使用尽可能多的这种硬币
c. 更新剩余金额
3. 如果最终金额减为0，返回硬币列表；否则返回None
关键特点:
- 每次选择当前可用的最大面额硬币
- 对于某些面额组合（如[1, 5, 10, 25]）能得到最优解
- 对于某些面额组合（如[1, 3, 4]）可能得不到最优解
- 需要验证贪心选择性质是否成立
贪心选择性质验证:
对于硬币面额系统，贪心算法能得到最优解的条件是：
每个较大面额都是较小面额的整数倍。
例如：[1, 5, 10, 25]满足条件，[1, 3, 4]不满足。
参数:
amount: 需要凑出的金额（正整数）
coins: 硬币面额列表（正整数列表，如[25, 10, 5, 1]）
返回:
使用的硬币列表（按面额从大到小），如果无法凑出则返回None
时间复杂度: O(n)，其中n是硬币种类数
空间复杂度: O(k)，其中k是使用的硬币数量
示例:
>>> greedy_coin_change(63, [25, 10, 5, 1])
[25, 25, 10, 1, 1, 1] # 使用6个硬币
>>> greedy_coin_change(6, [4, 3, 1])
[4, 1, 1] # 贪心解使用3个硬币，但最优解是[3, 3]使用2个硬币
注意:
- 此算法不保证总是得到最少硬币数
- 对于不满足贪心选择性质的面额系统，需要使用动态规划
- 实际应用中需要检查面额系统的性质
扩展:
- 0-1硬币问题：每种硬币最多使用一次
- 有限数量硬币：每种硬币有数量限制
- 最小硬币数问题：动态规划解法保证最优
"""
coins.sort(reverse=True) # 降序排列，确保每次选最大面额
result = []
for coin in coins:
while amount >= coin:
amount -= coin
result.append(coin)
if amount == 0:
return result
else:
return None # 无法凑出
def optimal_coin_change_dp(amount, coins):
"""动态规划硬币找零（对比贪心算法）
参数:
amount: 需要凑出的金额
coins: 硬币面额列表
返回:
使用的最少硬币列表
时间复杂度: O(amount * n)
"""
# dp[i]表示凑出金额i所需的最少硬币数
dp = [float('inf')] * (amount + 1)
dp[0] = 0
# 记录选择的硬币
coin_used = [-1] * (amount + 1)
for i in range(1, amount + 1):
for coin in coins:
if i >= coin and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
coin_used[i] = coin
# 如果无法凑出
if dp[amount] == float('inf'):
return None
# 回溯构造解
result = []
current = amount
while current > 0:
coin = coin_used[current]
result.append(coin)
current -= coin
return result硬币找零实验：贪心vs最优
def coin_change_experiment():
"""硬币找零问题实验：展示贪心算法的成功与失败"""
print("硬币找零问题实验")
print("=" * 50)
# 测试用例
test_cases = [
("标准货币系统（贪心最优）", 63, [100, 50, 20, 10, 5, 2, 1]),
("贪心失败的经典例子", 6, [4, 3, 1]),
("另一个失败案例", 30, [25, 10, 1]),
("复杂案例", 40, [25, 20, 10, 5, 1]),
]
for name, amount, coins in test_cases:
print(f"\n{name}:")
print(f" 金额: {amount}, 硬币面额: {coins}")
# 贪心算法
greedy_result = greedy_coin_change(amount, coins.copy())
if greedy_result:
print(f" 贪心算法: {greedy_result} (使用{greedy_result}个硬币)")
else:
print(f" 贪心算法: 无法凑出")
# 动态规划（最优解）
optimal_result = optimal_coin_change_dp(amount, coins)
if optimal_result:
print(f" 最优算法: {optimal_result} (使用{len(optimal_result)}个硬币)")
else:
print(f" 最优算法: 无法凑出")
# 比较
if greedy_result and optimal_result:
if len(greedy_result) == len(optimal_result):
print(f" 结果: 贪心算法是最优的！")
else:
print(f" 结果: 贪心算法使用了{len(greedy_result)-len(optimal_result)}个额外硬币")
# 运行硬币找零实验
coin_change_experiment()活动安排问题
def greedy_activity_selection(activities):
"""贪心活动安排算法（选择结束时间最早的活动）
问题描述（活动安排问题）:
给定n个活动，每个活动有开始时间start和结束时间end。
选择最大的互不冲突的活动集合（即任意两个活动时间不重叠）。
假设活动已经按结束时间排序。
算法思路（贪心策略）:
1. 将所有活动按结束时间升序排序
2. 选择第一个活动（结束时间最早）
3. 对于后续每个活动：
a. 如果该活动的开始时间 ≥ 上一个选择活动的结束时间
b. 选择该活动，更新上一个选择活动的结束时间
贪心选择：每次选择结束时间最早且不与已选活动冲突的活动。
正确性证明:
1. 贪心选择性质：存在一个最优解包含结束时间最早的活动
2. 最优子结构：选择某个活动后，剩余问题是最优子问题
3. 归纳证明：通过数学归纳法证明贪心算法能得到最优解
关键特点:
- 经典贪心算法成功案例
- 贪心选择能得到全局最优解
- 时间复杂度主要来自排序
- 需要活动按结束时间排序
参数:
activities: 活动列表，每个活动为(start, end)元组
start和end应为数值，且end > start
返回:
选择的活动列表（按选择顺序）
时间复杂度: O(n log n) - 排序时间复杂度
空间复杂度: O(n) - 存储排序后的活动和结果
示例:
>>> activities = [(1, 4), (3, 5), (0, 6), (5, 7),
... (3, 9), (5, 9), (6, 10), (8, 11),
... (8, 12), (2, 14), (12, 16)]
>>> greedy_activity_selection(activities)
[(1, 4), (5, 7), (8, 11), (12, 16)]
解释：
1. 按结束时间排序后：[(1,4), (3,5), (0,6), (5,7), ...]
2. 选择(1,4)，最后结束时间=4
3. 下一个开始时间≥4的是(5,7)，选择，最后结束时间=7
4. 下一个开始时间≥7的是(8,11)，选择，最后结束时间=11
5. 下一个开始时间≥11的是(12,16)，选择
共选择4个活动
注意:
- 活动时间应为半开区间[start, end)，即end时刻可以开始下一个活动
- 如果活动未排序，需要先排序
- 此算法选择的是最大数量的活动，不一定是最大总时长的活动
变体问题:
- 带权活动选择：每个活动有权重，求最大权重和
- 资源受限：有多个资源（房间），求最多安排的活动
- 时间区间重叠：允许一定重叠
应用场景:
- 会议室安排
- 课程表安排
- 任务调度
- 电视节目安排
"""
# 按结束时间排序
sorted_activities = sorted(activities, key=lambda x: x[1])
selected = []
last_end_time = 0
for start, end in sorted_activities:
if start >= last_end_time: # 活动不冲突
selected.append((start, end))
last_end_time = end
return selected
def greedy_activity_selection_alternative(activities, key='end'):
"""不同选择标准的贪心活动安排
参数:
activities: 活动列表
key: 排序标准，'start'(开始时间最早), 'duration'(持续时间最短), 'end'(结束时间最早)
返回:
选择的活动列表
"""
if key == 'start':
# 按开始时间排序
sorted_activities = sorted(activities, key=lambda x: x[0])
elif key == 'duration':
# 按持续时间排序
sorted_activities = sorted(activities, key=lambda x: x[1] - x[0])
else: # 'end'
sorted_activities = sorted(activities, key=lambda x: x[1])
selected = []
last_end_time = 0
for start, end in sorted_activities:
if start >= last_end_time:
selected.append((start, end))
last_end_time = end
return selected活动安排实验
def activity_selection_experiment():
"""活动安排问题实验：比较不同贪心策略"""
print("\n" + "=" * 50)
print("活动安排问题实验")
print("=" * 50)
# 测试数据
activities = [
(1, 4), (3, 5), (0, 6), (5, 7),
(3, 8), (5, 9), (6, 10), (8, 11),
(8, 12), (2, 13), (12, 14)
]
print(f"活动列表: {activities}")
print(f"活动数量: {len(activities)}")
# 不同策略比较
strategies = ['start', 'duration', 'end']
for strategy in strategies:
selected = greedy_activity_selection_alternative(activities, strategy)
print(f"\n按'{strategy}'排序选择的活动:")
print(f" 选择的活动: {selected}")
print(f" 活动数量: {len(selected)}")
# 最优性验证（结束时间最早策略是最优的）
print("\n" + "=" * 50)
print("贪心选择性质验证")
print("=" * 50)
print("定理证明思路:")
print("1. 贪心选择性质: 第一个选择结束时间最早的活动一定在某个最优解中")
print("2. 最优子结构: 选择第一个活动后，剩余问题与原问题结构相同")
print("3. 数学归纳法: 结合1和2，贪心算法得到全局最优解")
# 可视化证明
sorted_by_end = sorted(activities, key=lambda x: x[1])
print(f"\n活动按结束时间排序: {sorted_by_end}")
print("\n贪心算法步骤:")
last_end = 0
for i, (start, end) in enumerate(sorted_by_end):
if start >= last_end:
print(f" 步骤{i+1}: 选择活动({start}, {end})，因为开始时间{start} >= 上一个活动结束时间{last_end}")
last_end = end霍夫曼编码（贪心构造最优前缀码）
import heapq
class HuffmanNode:
"""霍夫曼树节点"""
def __init__(self, char=None, freq=0):
self.char = char # 字符（叶子节点）
self.freq = freq # 频率
self.left = None
self.right = None
def __lt__(self, other):
# 用于堆排序，比较频率
return self.freq < other.freq
def build_huffman_tree(frequencies):
"""构建霍夫曼树（贪心算法）
参数:
frequencies: 字典，字符->频率
返回:
霍夫曼树的根节点
算法步骤:
1. 为每个字符创建叶子节点，放入最小堆
2. 当堆中有超过一个节点时:
a. 弹出两个频率最小的节点
b. 创建新节点，频率为两者之和，左右子节点为这两个节点
c. 将新节点压入堆中
3. 堆中剩下的唯一节点就是霍夫曼树的根
"""
# 创建叶子节点堆
heap = [HuffmanNode(char, freq) for char, freq in frequencies.items()]
heapq.heapify(heap)
while len(heap) > 1:
# 弹出两个频率最小的节点
left = heapq.heappop(heap)
right = heapq.heappop(heap)
# 创建新节点
merged = HuffmanNode(freq=left.freq + right.freq)
merged.left = left
merged.right = right
# 压入堆中
heapq.heappush(heap, merged)
return heap[0] if heap else None
def generate_huffman_codes(root, current_code="", codes={}):
"""生成霍夫曼编码
参数:
root: 霍夫曼树根节点
current_code: 当前路径编码
codes: 编码字典
返回:
字符->编码的字典
"""
if root is None:
return codes
# 叶子节点，记录编码
if root.char is not None:
codes[root.char] = current_code
return codes
# 递归遍历左右子树
generate_huffman_codes(root.left, current_code + "0", codes)
generate_huffman_codes(root.right, current_code + "1", codes)
return codes
def huffman_coding_example():
"""霍夫曼编码示例"""
print("\n" + "=" * 50)
print("霍夫曼编码（贪心构造最优前缀码）")
print("=" * 50)
# 示例：英文文本中字母频率
frequencies = {
'a': 45, # 最高频率
'b': 13,
'c': 12,
'd': 16,
'e': 9,
'f': 5,
}
print(f"字符频率: {frequencies}")
# 构建霍夫曼树
root = build_huffman_tree(frequencies)
# 生成编码
codes = generate_huffman_codes(root)
print("\n生成的霍夫曼编码:")
for char, code in sorted(codes.items()):
print(f" '{char}': {code} (频率: {frequencies[char]})")
# 计算平均编码长度
total_freq = sum(frequencies.values())
avg_length = sum(frequencies[char] * len(code) for char, code in codes.items()) / total_freq
print(f"\n平均编码长度: {avg_length:.2f}比特/字符")
print(f"固定长度编码需要: {len(bin(len(frequencies)-1))-2}比特/字符")
# 贪心性质验证
print("\n贪心性质验证:")
print("合并频率最小的两个节点总是最优的，因为:")
print("1. 频率低的字符应该编码长，频率高的字符应该编码短")
print("2. 合并最小频率节点相当于给它们分配最长的编码路径")
print("3. 数学归纳法可以证明这个贪心策略得到全局最优前缀码")
# 运行霍夫曼编码示例
huffman_coding_example()兔狲教授总结道，"我们不仅理解了贪心算法的实现，更理解了连续决策的策略。贪心算法教给我们：有时候，最好的长期策略是一系列好的短期决策；但有时候，短视会导致灾难。知道何时贪心、何时规划，是算法思维也是生活智慧。"
兔狲教授的思考题
实践探索（适合小小猪）
算法实现：实现活动安排问题的贪心算法。测试不同排序标准（开始时间最早、持续时间最短、结束时间最早）的结果。哪个标准能得到最优解？为什么？
贪心失败构造：构造一个使贪心算法严重失败的问题实例。例如：设计一组硬币面额，使得贪心凑零钱算法使用的硬币数远多于最优解。
现实观察：观察生活中的贪心决策。超市结账时选择最短队伍是贪心策略吗？什么时候会失败？（提示：考虑队伍中顾客购物车内容）
历史探究（适合小海豹）
思想溯源："贪心"（Greedy）这个概念在计算机科学中何时出现？最早是谁提出并分析了贪心算法？查阅早期算法文献（如Kruskal 1956, Prim 1957, Dijkstra 1959）。
跨学科联系：贪心算法与经济学中的"边际决策"、心理学中的"即时满足"有什么相似之处？这些领域如何研究短视决策的利弊？
哲学反思：功利主义的"最大幸福原则"是贪心思维吗？边沁和密尔的功利主义与贪心算法有什么相似和不同？
综合思考
伦理考量：自动驾驶汽车在紧急情况下的决策可以用贪心算法吗？（例如：总是选择最小化立即伤害的转向）这种短视决策可能有什么问题？
算法比较：贪心算法与动态规划（下章内容）有什么根本区别？为什么有些问题贪心有效而动态规划需要？有些则相反？
创造练习：设计一个"贪心寓言"——用故事解释贪心算法的优点和局限。（提示：可以比喻为登山者总是选择最陡的上坡路）
极限挑战：证明霍夫曼编码的贪心算法最优性。理解为什么合并频率最小的节点总是最优的。
下一步预告
傍晚的珠江泛起金色的波光，游船缓缓驶过，留下长长的水痕。康乐园的钟声再次响起，提醒着时间的流逝。
小小猪正在电脑上模拟不同贪心策略的效果，屏幕上显示着各种问题实例和算法表现。小海豹则在白板上推导贪心选择性质的证明，试图理解那看似直觉的选择背后的数学必然。
"今天我们从'连续决策的策略'开始，"兔狲教授收拾着茶具，"探索了贪心算法的智慧与局限，理解了局部最优与全局最优的张力。"
小海豹放下粉笔，"教授，如果贪心算法可能失败，我们有什么方法能保证得到全局最优解呢？"
兔狲教授微笑："好问题。这就需要更强大的工具了——启发式。"
小小猪的笔记：我测试了不同硬币系统的贪心算法。对于常见面额（1,2,5,10,20,50,100），贪心总是最优！但对于奇怪的面额（1,3,4），要付6元时贪心选4+1+1（3个硬币），最优是3+3（2个硬币）。原来我们用的货币系统是精心设计的！
小海豹的笔记：查了贪心算法的历史，发现Kruskal和Prim在1950年代独立提出最小生成树算法，都用了贪心思想。有时，简单的直觉需要时间才能形式化证明。
兔狲教授的结语：记住，贪心算法教给我们决策的重要一课：有时候，最好的长期策略是一系列好的短期决策；但有时候，短视会导致灾难。知道何时贪心、何时规划，是算法思维也是生活智慧。我们慢慢来，理解了最重要。