MCM520 ← 资料站首页 贪心算法 · 深度手册 打开交互阅读器 →

贪心算法 · 深度手册

分类：优化类 ｜ 难度：★☆☆ 入门 ｜ 编号：greedy

📊 数据视角

本资料站收录 343 篇 优秀范文，贪心算法共出现约 35 次，排名 第4（范文频次）。贪心是竞赛中最常用的基础算法，常作为其他复杂算法的子步骤或对比基线。

关键词覆盖："Greedy"、"贪心"、"局部最优"、"霍尔定理"、"活动选择"、" Huffman编码" 等。

一句话：贪心算法每次做出当前看起来最好的选择，希望最终得到全局最优解。它简单、快速，但不保证最优——关键是要证明贪心选择性质。

一、这是什么（一句话用途）

快速求解优化问题的局部最优策略（调度 / 覆盖 / 图论 / 哈夫曼编码）

二、核心思想

贪心算法（Greedy Algorithm）的核心是贪心选择性质：每一步都做出在当前状态下最优的选择，不考虑长远后果。如果问题的最优解能通过一系列局部最优选择构成，贪心算法就能得到全局最优解。

为什么用贪心？

  • 实现简单，代码量少
  • 运行速度快（通常 O(n log n) 或 O(n)）
  • 可作为复杂算法的近似或子模块

局限：

  • 不一定能得到全局最优解
  • 需要证明贪心选择的正确性
  • 不适用于所有问题

三、贪心正确性证明方法

3.1 贪心选择性质

证明：可以通过局部最优选择达到全局最优。

典型思路：

  1. 假设最优解包含非贪心选择
  2. 构造一个新解，用贪心选择替换非贪心部分
  3. 证明新解不劣于原最优解
  4. 矛盾！故最优解必含贪心选择

3.2 交换论证（Exchange Argument）

如果最优解 OO 与贪心解 GG 不同，找到一个位置 where OO 和 GG 不同，通过"交换"操作证明 OO 不劣于 GG，从而 OO 也是贪心解。

3.3 拟阵理论

某些优化问题具有"拟阵"结构，此时贪心算法必得最优解。经典例子：最小生成树（Kruskal/Prim）、任务调度。

四、经典贪心算法

问题 贪心策略 时间复杂度
活动选择 每次选结束最早的兼容活动 O(n log n)
Huffman编码 每次合并频率最小的两个节点 O(n log n)
最小生成树 Kruskal 按边权从小到大选，不形成环 O(E log E)
最小生成树 Prim 从起点扩展，每次选最短边 O(E log V)
Dijkstra最短路 每次选距离源最近的未确定点 O((V+E)log V)
区间覆盖 每次选覆盖最右端的最长区间 O(n log n)

五、Python 实现示例

5.1 活动选择问题

import numpy as np

def greedy_activity_selection(activities):
    """
    activities: list of (start, end, name)
    返回最大兼容活动子集
    """
    # 按结束时间排序
    sorted_acts = sorted(activities, key=lambda x: x[1])
    result = [sorted_acts[0]]
    last_end = sorted_acts[0][1]
    
    for start, end, name in sorted_acts[1:]:
        if start >= last_end:  # 兼容
            result.append((start, end, name))
            last_end = end
    
    return result

# 测试
activities = [(1,4,"A"), (3,5,"B"), (0,6,"C"), (5,7,"D"), (3,8,"E"), (5,9,"F"), (6,10,"G"), (8,11,"H"), (6,12,"I"), (9,13,"J")]
selected = greedy_activity_selection(activities)
print(f"最多可选择 {len(selected)} 个活动: {[a[2] for a in selected]}")

5.2 Huffman 编码

import heapq
from collections import Counter

def huffman_encoding(data):
    """构建 Huffman 编码"""
    freq = Counter(data)
    heap = [[weight, [symbol, ""]] for symbol, weight in freq.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

# 测试
data = "AAABBBCCCDDE"
codes = huffman_encoding(data)
print("Huffman 编码:")
for symbol, code in codes:
    print(f"  '{symbol}': {code}")

5.3 Kruskal 最小生成树

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

def kruskal(edges, n):
    """edges: list of (weight, u, v)"""
    edges = sorted(edges)
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    for w, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total_weight += w
            if len(mst) == n - 1:
                break
    
    return mst, total_weight

# 测试
edges = [(1,0,1), (4,0,2), (2,1,2), (6,1,3), (3,2,3)]
mst, weight = kruskal(edges, 4)
print(f"最小生成树权重: {weight}")
print(f"边: {mst}")

六、MATLAB 实现示例

%% 贪心活动选择（MATLAB/Octave）
activities = [1,4; 3,5; 0,6; 5,7; 3,8; 5,9; 6,10; 8,11; 6,12; 9,13];
% 按结束时间排序
[~,idx] = sort(activities(:,2));
activities = activities(idx,:);

selected = activities(1,:);
last_end = activities(1,2);
for i = 2:size(activities,1)
    if activities(i,1) >= last_end
        selected = [selected; activities(i,:)];
        last_end = activities(i,2);
    end
end
fprintf('最多选择 %d 个活动\n', size(selected,1));
disp(selected);

七、贪心 vs 动态规划

特性 贪心 动态规划
决策方式 只看当前最优 考虑所有子问题
正确性 需要证明 保证最优
速度 快 较慢
适用问题 具有贪心选择性质 具有最优子结构

关键区别：贪心只看眼前，DP 回溯所有可能。如果问题满足"贪心选择性质"，贪心更简单高效；否则必须用 DP。

八、常见误区与避坑清单

误区 正确做法
盲目用贪心，不证明正确性 用交换论证或反例验证
贪心得不到最优解就弃用 贪心仍是好的近似算法
排序后就贪心 先分析问题的贪心选择性质
忽略边界情况 单元素、空集、全部冲突等特例

九、论文写作技巧

针对活动选择问题，本文采用贪心算法求解。贪心策略为：每次选择结束时间最早且与已选活动兼容的活动。该策略的正确性可通过交换论证证明：假设最优解包含非贪心选择，用结束更早的贪心活动替换后不劣于原解，矛盾。算法时间复杂度为 O(nlog⁡n)O(n\log n)（排序主导）。

十、相关手册（延伸阅读）

完整算例（数字演示，照着算一遍）

场景：活动选择，开始/结束时间：A(1,4)、B(3,5)、C(5,9)、D(0,6)、E(5,7)、F(8,10)。选最多不重叠活动。

贪心（按结束时间升序）：选 A(结束4)→下一个开始≥4 选 E(5-7)→下一个开始≥7 选 F(8-10)，共 3 个。

结论：A、E、F 互不重叠且数量最多，贪心按结束时间最早得最优。

十一、本手册导航

本手册由「算法深度手册生成器」自动产出。