算法设计与分析：贪心算法

按开始时间最早优先选择 ✗

活动：[1, 10], [2, 3], [4, 5] 
按开始时间：选择 [1, 10]，只能选 1 个 
最优解：选择 [2, 3], [4, 5]，能选 2 个 

贪心策略：将活动按结束时间从小到大排序，依次选择与已选活动相容的活动。

为什么这个策略正确？

直观理解：

• 结束时间早的活动"占用"资源的时间短
• 为后续活动留出更多选择空间
• 类似于"早起的鸟儿有虫吃"

严格证明（贪心选择性质）：

定理：按结束时间最早优先选择的贪心策略能得到最优解。

证明（归纳法）：

设活动按结束时间排序为 f₁ ≤ f₂ ≤ … ≤ fₙ。

归纳基础：选择活动 1（结束最早的）是最优的。

• 如果某个最优解不包含活动 1，设其第一个活动是活动 k
• 由于 f₁ ≤ fₖ，可以用活动 1 替换活动 k，得到另一个最优解
• 因此，存在包含活动 1 的最优解

归纳假设：假设前 k 个贪心选择是正确的。

归纳步骤：第 k+1 个贪心选择选择的是与之前所有活动相容中结束最早的活动。

• 根据归纳基础，这个选择也是正确的

结论：通过归纳，贪心策略能得到最优解。

图解执行过程

以 6 个活动为例：

活动：A1 A2 A3 A4 A5 A6 
时间：[1,4] [3,5] [0,6] [5,7] [3,9] [5,9] 
排序后（按结束时间）：A1[1,4] → A2[3,5] → A3[0,6] → A4[5,7] → A5[3,9] → A6[5,9] 
4 5 6 7 9 9 
贪心选择过程：
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 
步骤 1: 选择 A1[1,4] 
剩余时间从 4 开始 
步骤 2: 检查 A2[3,5] 
开始 3 < 结束 4，冲突，跳过 
步骤 3: 检查 A3[0,6] 
开始 0 < 结束 4，冲突，跳过 
步骤 4: 检查 A4[5,7] 
开始 5 ≥ 结束 4，选择！ 
剩余时间从 7 开始 
步骤 5: 检查 A5[3,9] 
开始 3 < 结束 7，冲突，跳过 
步骤 6: 检查 A6[5,9] 
开始 5 < 结束 7，冲突，跳过 
最终选择：{A1, A4} 
最大活动数：2 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 

Python 实现

from typing import List, Tuple

class Activity:
    """活动类"""
    def __init__(self, start: int, finish: int, name: str = None):
        self.start = start
        self.finish = finish
        self.name = name if name else f"[{start},{finish}]"

    def __lt__(self, other):
        """按结束时间排序"""
        return self.finish < other.finish

    def __repr__(self):
        return f"{self.name}"

def activity_selection(activities: List[Activity]) -> List[Activity]:
    """
    活动安排问题的贪心算法
    参数:
        activities: 活动列表
    返回:
        选择的相容活动列表
    """
    if not activities:
        return []
    # 按结束时间排序
    sorted_activities = sorted(activities)
    n = len(sorted_activities)
    selected = [sorted_activities[0]]  # 选择第一个活动
    last_finish = sorted_activities[0].finish
    print("贪心选择过程：")
    print("=" * 50)
    print(f"初始选择：{sorted_activities[0]}")
    for i in range(1, n):
        current = sorted_activities[i]
        print(f"检查 {current}: ", end="")
        if current.start >= last_finish:
            selected.append(current)
            last_finish = current.finish
            print(f"选择 ✓ (当前时间：{last_finish})")
        else:
            print(f"跳过 ✗ (冲突)")
    print("=" * 50)
    return selected

# 递归解法（对比）
def activity_selection_recursive(s: List[int], f: List[int], k: int, n: int) -> List[int]:
    """
    递归求解活动安排问题
    参数:
        s: 开始时间数组（1-indexed）
        f: 结束时间数组（1-indexed）
        k: 上一个选择的活动索引
        n: 活动总数
    返回:
        选择的活动索引列表
    """
    m = k + 1  # 找到第一个与活动 k 相容的活动
    while m <= n and s[m] < f[k]:
        m += 1
    if m <= n:
        return [m] + activity_selection_recursive(s, f, m, n)
    return []

# 示例用法
if __name__ == "__main__":
    # 示例 1：基本示例
    print("示例 1：基本活动安排")
    print("-" * 50)
    activities = [
        Activity(1, 4, "会议 1"),
        Activity(3, 5, "会议 2"),
        Activity(0, 6, "会议 3"),
        Activity(5, 7, "会议 4"),
        Activity(3, 9, "会议 5"),
        Activity(5, 9, "会议 6"),
    ]
    selected = activity_selection(activities)
    print(f"\n最终选择：{selected}")
    print(f"最大活动数：{len(selected)}")
    # 示例 2：递归解法
    print("\n\n示例 2：递归解法")
    print("-" * 50)
    s = [0, 1, 3, 0, 5, 3, 5]  # 开始时间（1-indexed）
    f = [0, 4, 5, 6, 7, 9, 9]  # 结束时间
    result = activity_selection_recursive(s, f, 0, 6)
    print(f"递归解法选择的活动索引：{result}")
    print(f"选择的活动数：{len(result)}")

输出：

示例 1：基本活动安排 -------------------------------------------------- 贪心选择过程： ================================================== 初始选择：会议 1 检查 会议 2: 跳过 ✗ (冲突) 检查 会议 3: 跳过 ✗ (冲突) 检查 会议 4: 选择 ✓ (当前时间：7) 检查 会议 5: 跳过 ✗ (冲突) 检查 会议 6: 跳过 ✗ (冲突) ================================================== 最终选择：[会议 1, 会议 4] 最大活动数：2 示例 2：递归解法 -------------------------------------------------- 递归解法选择的活动索引：[1, 4] 选择的活动数：2 

复杂度分析

• 时间复杂度：O(n log n)
  • 排序：O(n log n)
  • 贪心选择：O(n)
  • 总复杂度：O(n log n)（排序主导）
• 空间复杂度：O(1)（迭代）或 O(n)（递归，递归栈深度）

4.2 贪心算法的基本要素

贪心选择性质

定义：可以通过做出局部最优选择来达到全局最优。

关键特征：

1. 每一步做选择时，只考虑当前状态下的最优选择
2. 一旦做出选择，就不能回溯
3. 不需要考虑子问题的所有可能解

判断方法：

• 观察问题是否可以逐步做出选择
• 尝试证明：每次的局部最优选择能否导向全局最优
• 通过反例验证：是否存在反例说明贪心策略不成立

最优子结构性质

定义：问题的最优解包含其子问题的最优解。

与动态规划的对比：

• 贪心算法：自顶向下，每步做选择后缩减问题规模
• 动态规划：自底向上，先求解子问题再组合

共同点：都要求最优子结构性质

区别：

贪心策略正确性的证明

证明方法：

1. 归纳法

# 证明模板
""" 
定理：[贪心策略描述] 能得到最优解。
证明：
1. 基础情况：证明第一步选择是正确的
2. 归纳假设：假设前 k 步选择是正确的
3. 归纳步骤：证明第 k+1 步选择也是正确的
4. 结论：通过归纳，整个策略正确
"""

2. 反证法

# 证明模板
""" 
定理：[贪心策略描述] 能得到最优解。
证明（反证法）：
假设贪心策略不能得到最优解。
推导出矛盾，因此假设错误，贪心策略正确。
"""

3. 交换论证

# 证明模板
""" 
定理：[贪心策略描述] 能得到最优解。
证明（交换论证）：
1. 设贪心解为 G，最优解为 O
2. 证明可以通过逐步交换，将 O 转换为 G
3. 每次交换不会使解变差
4. 因此 G 也是最优解
"""

示例：贪心 vs 动态规划

硬币找零问题：

给定硬币面值和目标金额，求最少硬币数。

from typing import List, Tuple

# 贪心算法
def coin_change_greedy(coins: List[int], amount: int) -> Tuple[int, List[int]]:
    """
    贪心算法：每次选择面值最大的硬币
    注意：贪心算法并非总是最优！
    """
    coins.sort(reverse=True)
    count = 0
    remaining = amount
    used = []
    for coin in coins:
        while remaining >= coin:
            remaining -= coin
            count += 1
            used.append(coin)
    return count, used

# 动态规划
def coin_change_dp(coins: List[int], amount: int) -> Tuple[int, List[int]]:
    """
    动态规划：始终能得到最优解
    时间复杂度：O(amount × len(coins))
    """
    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)
    # 重构解
    if dp[amount] == float('inf'):
        return 0, []
    used = []
    remaining = amount
    for coin in sorted(coins, reverse=True):
        while remaining >= coin and dp[remaining] == dp[remaining - coin] + 1:
            used.append(coin)
            remaining -= coin
    return dp[amount], used

# 对比
print("硬币找零：贪心 vs 动态规划")
print("=" * 50)
# 案例 1：贪心有效
coins1 = [1, 5, 10, 25]
amount1 = 67
greedy1, used1 = coin_change_greedy(coins1, amount1)
dp1, used_dp1 = coin_change_dp(coins1, amount1)
print(f"\n案例 1：面值{coins1}，目标{amount1}")
print(f"贪心算法：{greedy1}个硬币 {used1}")
print(f"动态规划：{dp1}个硬币 {used_dp1}")
print(f"结果：{'相同 ✓' if greedy1 == dp1 else '不同 ✗'}")
# 案例 2：贪心失效
coins2 = [1, 3, 4]
amount2 = 6
greedy2, used2 = coin_change_greedy(coins2, amount2)
dp2, used_dp2 = coin_change_dp(coins2, amount2)
print(f"\n案例 2：面值{coins2}，目标{amount2}")
print(f"贪心算法：{greedy2}个硬币 {used2}")
print(f"动态规划：{dp2}个硬币 {used_dp2}")
print(f"结果：{'相同 ✓' if greedy2 == dp2 else '不同 ✗ (贪心非最优!)'}")

输出：

硬币找零：贪心 vs 动态规划 ================================================== 案例 1：面值 [1, 5, 10, 25]，目标 67 贪心算法：6 个硬币 [25, 25, 10, 5, 1, 1] 动态规划：6 个硬币 [25, 25, 10, 5, 1, 1] 结果：相同 ✓ 案例 2：面值 [1, 3, 4]，目标 6 贪心算法：3 个硬币 [4, 1, 1] 动态规划：2 个硬币 [3, 3] 结果：不同 ✗ (贪心非最优!) 

关键洞察：

• 贪心算法简单高效，但并非对所有问题有效
• 需要通过证明确认贪心策略的正确性
• 当贪心失效时，考虑使用动态规划

4.3 最优装载问题

问题描述

有一批集装箱需要装船，每个集装箱有重量 w[i]，船的载重量为 C。目标是装载尽可能多的集装箱。

注意：与 0-1 背包问题不同，这里的目标是最大化数量而不是总重量。

示例：

集装箱重量：[5, 3, 7, 2, 8, 4, 1, 6] 
船的载重量：20 

解题思路

贪心策略

策略：按重量最轻优先装载

直观理解：

• 轻的集装箱占用空间小
• 能装更多的集装箱
• 类似于"能用小盒子就别用大盒子"

正确性证明

定理：按重量最轻优先装载的贪心策略能得到最优解。

证明（交换论证）：

设贪心算法得到的解为 G = {g₁, g₂, …, gₖ}，按重量排序（w₁ ≤ w₂ ≤ … ≤ wₖ）。 设最优解为 O = {o₁, o₂, …, oₘ}，按重量排序。

目标：证明 k = m（贪心解也是最优解）

证明：

1. 假设 k < m，即最优解装箱数更多
2. 由于贪心算法每次选择最轻的，对于任意 i ≤ k，有 gᵢ ≤ oᵢ
3. 因此 Σ(gᵢ) ≤ Σ(oᵢ) ≤ C
4. 但是贪心算法在无法再装时停止，说明 oₖ₊₁ 也无法装入
5. 这与 O 是可行解矛盾
6. 因此 k = m，贪心解是最优的

与 0-1 背包的对比

关键区别：

• 最优装载：所有物品的"价值"相同（数量 +1），贪心有效
• 0-1 背包：物品有不同价值，贪心可能失效，需要 DP

Python 实现

from typing import List, Tuple

def optimal_loading(weights: List[int], capacity: int) -> Tuple[int, List[int]]:
    """
    最优装载问题的贪心算法
    参数:
        weights: 集装箱重量列表
        capacity: 船的载重量
    返回:
        (装箱数量，选择的集装箱重量)
    """
    # 按重量从小到大排序
    sorted_weights = sorted(weights)
    count = 0
    total_weight = 0
    selected = []
    print("贪心选择过程：")
    print("=" * 60)
    print(f"{'序号':<8}{'重量':<10}{'累计重量':<12}{'剩余容量':<10}{'决策':<10}")
    print("-" * 60)
    remaining = capacity
    for i, weight in enumerate(sorted_weights, 1):
        print(f"{i:<8}{weight:<10}{total_weight:<12}{remaining:<10}", end=" ")
        if remaining >= weight:
            selected.append(weight)
            total_weight += weight
            remaining -= weight
            count += 1
            print("装入 ✓")
        else:
            print("跳过 ✗（超出容量）")
    print("-" * 60)
    print(f"最终结果：装入 {count} 个集装箱，总重量 {total_weight}")
    return count, selected

# 示例用法
if __name__ == "__main__":
    # 示例 1
    print("示例 1：基本最优装载")
    print("-" * 50)
    weights = [5, 3, 7, 2, 8, 4, 1, 6]
    capacity = 20
    print(f"集装箱重量：{weights}")
    print(f"船的载重量：{capacity}\n")
    count, selected = optimal_loading(weights, capacity)
    print(f"\n装载方案：")
    print(f" 装箱数量：{count}")
    print(f" 集装箱重量：{selected}")
    print(f" 总重量：{sum(selected)}/{capacity}")

输出：

示例 1：基本最优装载 -------------------------------------------------- 集装箱重量：[5, 3, 7, 2, 8, 4, 1, 6] 船的载重量：20 贪心选择过程： ---------------------------------------------------- 序号 重量 累计重量 剩余容量 决策 ---------------------------------------------------- 1 1 0 20 装入 ✓ 2 2 1 19 装入 ✓ 3 3 3 17 装入 ✓ 4 4 6 14 装入 ✓ 5 5 10 10 装入 ✓ 6 6 15 5 跳过 ✗（超出容量） 7 7 15 5 跳过 ✗（超出容量） 8 8 15 5 跳过 ✗（超出容量） ---------------------------------------------------- 最终结果：装入 5 个集装箱，总重量 15 装载方案： 装箱数量：5 集装箱重量：[1, 2, 3, 4, 5] 总重量：15/20 

复杂度分析

• 时间复杂度：O(n log n)
  • 排序：O(n log n)
  • 贪心选择：O(n)
• 空间复杂度：O(n) 或 O(1)

4.4 哈夫曼编码

问题描述

哈夫曼编码是一种前缀编码，用于数据压缩。目标是为字符集中的每个字符分配二进制编码，使得：

1. 前缀性质：任何一个编码都不是另一个编码的前缀
2. 高频字符的编码短，低频字符的编码长
3. 平均编码长度最短

示例：

文本："hello world" 
字符频率：h=1, e=1, l=3, o=2, ' '=1, w=1, r=1, d=1 
目标：构造最优前缀编码 

解题思路

什么是前缀编码？

前缀编码：没有任何编码是另一个编码的前缀。

优点：无需分隔符就能唯一解码

示例：

定长编码：A=00, B=01, C=10, D=11（前缀编码） 
变长编码：A=0, B=10, C=110, D=111（前缀编码） 
非前缀编码：A=0, B=01（B 的前缀是 A，有歧义） 

贪心策略

策略：频率最小的两个节点优先合并

算法步骤：

1. 统计每个字符的频率
2. 将每个字符看作叶子节点，频率作为权重
3. 反复选择两个频率最小的节点合并：
   • 创建新节点作为它们的父节点
   • 新节点的频率 = 两个子节点频率之和
4. 重复步骤 3，直到只剩一个节点（根节点）
5. 从根到叶子的路径标记 0 和 1，得到编码

为什么这个策略正确？

直观理解：

• 频率高的字符应该在树的较高层（编码短）
• 频率低的字符应该在树的较低层（编码长）
• 每次合并最小频率节点保证了这一点

严格证明：

定理：哈夫曼编码生成的编码是所有前缀编码中平均长度最短的。

证明（归纳法和交换论证）：

引理 1：在最优前缀编码中，频率最低的两个字符必定是兄弟节点

引理 2：合并两个最小频率节点后，子问题也是最优的

归纳基础：n=2 时，显然哈夫曼编码是最优的

归纳步骤：对于 n 个字符，哈夫曼算法合并频率最低的 x 和 y

• 由引理 1，任何最优编码中 x 和 y 都是兄弟
• 合并 x 和 y 得到 n-1 个字符的问题
• 由归纳假设，哈夫曼算法对这个子问题是最优的
• 因此，原问题也是最优的

图解示例

以文本 'hello world' 为例：

字符频率统计：h: 1, e: 1, l: 3, o: 2, ' ': 1, w: 1, r: 1, d: 1 
按频率排序：d:1, h:1, e:1, ' ':1, w:1, r:1, o:2, l:3 
构建过程：
步骤 1: 合并 d(1) 和 h(1) → dh(2) 
步骤 2: 合并 e(1) 和 ' '(1) → e' '(2) 
步骤 3: 合并 w(1) 和 r(1) → wr(2) 
步骤 4: 合并 dh(2) 和 e' '(2) → dhe' '(4) 
步骤 5: 合并 wr(2) 和 o(2) → wro(4) 
步骤 6: 合并 dhe' '(4) 和 wro(4) → all(8) 
步骤 7: 合并 all(8) 和 l(3) → root(11) 
最终哈夫曼树：
root(11)
/ \ 
all(8) l(3)
/ \ 
dhe'(4) wro(4)
/ \ / \ 
dh(2) e'(2) wr(2) o(2)
/ \ / \ / \ 
d h e ' ' w r 
编码结果：
l: 0 
o: 100 
r: 1010 
w: 1011 
d: 11000 
h: 11001 
e: 11010 
' ': 11011 

Python 实现

import heapq
from typing import Dict, List
from collections import Counter

class HuffmanNode:
    """哈夫曼树节点"""
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right

    def __lt__(self, other):
        """用于堆比较"""
        return self.freq < other.freq

    def is_leaf(self):
        """判断是否为叶子节点"""
        return self.left is None and self.right is None

def build_huffman_tree(frequency: Dict[str, int]):
    """构建哈夫曼树"""
    # 创建优先队列
    heap = []
    for char, freq in frequency.items():
        node = HuffmanNode(char=char, freq=freq)
        heapq.heappush(heap, node)
    print("\n构建哈夫曼树的过程：")
    print("=" * 60)
    step = 1
    # 合并节点
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        print(f"步骤{step}: 合并 {left.char or'内'}({left.freq}) + "
              f"{right.char or'内'}({right.freq}) = {left.freq + right.freq}")
        merged = HuffmanNode(
            freq=left.freq + right.freq,
            left=left,
            right=right
        )
        heapq.heappush(heap, merged)
        step += 1
    print("=" * 60)
    return heap[0]

def generate_codes(root: HuffmanNode, current_code: str = "", codes: Dict[str, str] = None) -> Dict[str, str]:
    """从哈夫曼树生成编码"""
    if codes is None:
        codes = {}
    if root is None:
        return codes
    if root.is_leaf():
        codes[root.char] = current_code if current_code else "0"
        return codes
    generate_codes(root.left, current_code + "0", codes)
    generate_codes(root.right, current_code + "1", codes)
    return codes

def huffman_encode(text: str, codes: Dict[str, str]) -> str:
    """使用哈夫曼编码对文本编码"""
    return ''.join(codes[char] for char in text)

def huffman_decode(encoded: str, root: HuffmanNode) -> str:
    """使用哈夫曼树对编码解码"""
    result = []
    current = root
    for bit in encoded:
        if bit == '0':
            current = current.left
        else:
            current = current.right
        if current.is_leaf():
            result.append(current.char)
            current = root
    return ''.join(result)

# 示例用法
if __name__ == "__main__":
    text = "hello world"
    frequency = Counter(text)
    print(f"原始文本：'{text}'")
    print(f"字符频率：{dict(frequency)}")
    # 构建哈夫曼树
    root = build_huffman_tree(frequency)
    # 生成编码
    codes = generate_codes(root)
    print("\n哈夫曼编码表：")
    print("=" * 50)
    for char, code in sorted(codes.items(), key=lambda x: len(x[1])):
        print(f"'{char}': {code} (长度：{len(code)})")
    print("=" * 50)
    # 编码和解码
    encoded = huffman_encode(text, codes)
    print(f"\n编码结果：{encoded}")
    decoded = huffman_decode(encoded, root)
    print(f"解码结果：'{decoded}'")
    print(f"正确性：{'✓ 正确' if decoded == text else '✗ 错误'}")
    # 压缩率
    original_bits = len(text) * 8
    compressed_bits = len(encoded)
    print(f"\n压缩统计:")
    print(f" 原始比特数：{original_bits}")
    print(f" 压缩比特数：{compressed_bits}")
    print(f" 压缩比：{compressed_bits / original_bits:.2%}")
    print(f" 节省空间：{(1 - compressed_bits / original_bits) * 100:.1f}%")

输出：

原始文本：'hello world' 字符频率：{'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1} 构建哈夫曼树的过程： ============================================================ 步骤 1: 合并 d(1) + h(1) = 2 步骤 2: 合并 e(1) + (1) = 2 步骤 3: 合并 w(1) + r(1) = 2 步骤 4: 合并 内 (2) + 内 (2) = 4 步骤 5: 合并 内 (2) + o(2) = 4 步骤 6: 合并 内 (4) + 内 (4) = 8 步骤 7: 合并 内 (8) + l(3) = 11 ============================================================ 哈夫曼编码表： ================================================== 'l': 0 (长度：1) 'o': 100 (长度：3) 'w': 1011 (长度：4) 'r': 1010 (长度：4) 'h': 11001 (长度：5) 'e': 11010 (长度：5) ' ': 11011 (长度：5) 'd': 11000 (长度：5) ================================================== 编码结果：11001110101101001001101001111110100 解码结果：'hello world' 正确性：✓ 正确 压缩统计：原始比特数：88 压缩比特数：37 压缩比：42.05% 节省空间：58.0% 

复杂度分析

• 时间复杂度：O(n log n)
  • 堆操作：n 次插入，n 次删除，每次 O(log n)
• 空间复杂度：O(n)
  • 哈夫曼树：O(n)
  • 编码表：O(n)

应用实例

• ZIP 压缩：使用 DEFLATE 算法（哈夫曼编码 + LZ77）
• JPEG：图像压缩中的编码步骤
• MP3：音频压缩中的编码步骤

4.5 单源最短路径

问题描述

给定带权有向图 G = (V, E) 和源点 s，求从 s 到图中所有其他顶点的最短路径。

约束：所有边权必须非负

示例：

图：A(0)
/ | \
4 2 1
/ | \
B C D
| | |
3 3 2
| | |
E F G
求：从 A 到所有其他顶点的最短路径 

解题思路

Dijkstra 算法的贪心策略

策略：选择距离估计最小的未访问顶点

算法步骤：

1. 初始化：d[s] = 0，其他 d[v] = ∞
2. 维护两个集合：已确定顶点集 S，未确定顶点集 V-S
3. 重复以下步骤，直到 S = V：
   • 从 V-S 中选择 d 值最小的顶点 u，加入 S
   • 松弛 u 的所有出边 (v, u)：
     • 如果 d[u] + w(u, v) < d[v]，更新 d[v]

为什么这个策略正确？

• 边权非负保证了：一旦顶点加入 S，其距离就是最终的
• 贪心选择（最小距离估计）每次都能确定一个顶点的最短路径

正确性证明

定理：Dijkstra 算法能正确计算单源最短路径。

证明（归纳法）：

不变量：

1. 对于所有已确定顶点 u ∈ S，d[u] 是从 s 到 u 的最短距离
2. 对于所有未确定顶点 v ∈ V-S，d[v] 是从 s 到 v 且只经过 S 中顶点的最短路径长度

归纳基础：初始时 S = {s}，d[s] = 0 显然正确

归纳步骤：设 u 是选择的顶点（d[u] 最小）。

• 假设存在更短的路径 P 从 s 到 u
• 路径 P 必须经过某个顶点 x ∈ V-S
• 由于边权非负，d[x] ≤ P 的长度 < d[u]
• 但 d[u] 是 V-S 中的最小距离，矛盾
• 因此，d[u] 是最短距离

Python 实现

import heapq
from typing import Dict, List, Tuple, Set
from collections import defaultdict

class Graph:
    """图类（邻接表表示）"""
    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self, u: str, v: str, weight: int, directed: bool = False):
        """添加边"""
        self.adj[u].append((v, weight))
        if not directed:
            self.adj[v].append((u, weight))

    def vertices(self) -> Set[str]:
        """获取所有顶点"""
        vertices = set(self.adj.keys())
        for u in self.adj:
            for v, _ in self.adj[u]:
                vertices.add(v)
        return vertices

def dijkstra(graph: Graph, start: str) -> Tuple[Dict[str, float], Dict[str, str]]:
    """
    Dijkstra 算法实现
    参数:
        graph: 图对象
        start: 源点
    返回:
        (距离字典，前驱字典)
    """
    vertices = graph.vertices()
    distances = {v: float('infinity') for v in vertices}
    predecessors = {v: None for v in vertices}
    distances[start] = 0
    # 优先队列：(距离，顶点)
    pq = [(0, start)]
    visited = set()
    print("Dijkstra 算法执行过程：")
    print("=" * 70)
    print(f"{'步骤':<6}{'当前顶点':<10}{'距离':<8}{'操作':<40}")
    print("-" * 70)
    step = 1
    while pq:
        current_dist, current = heapq.heappop(pq)
        if current in visited:
            continue
        visited.add(current)
        print(f"{step:<6}{current:<10}{current_dist:<8}", end=" ")
        # 松弛操作
        relaxed = False
        for neighbor, weight in graph.adj[current]:
            if neighbor in visited:
                continue
            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                predecessors[neighbor] = current
                heapq.heappush(pq, (new_dist, neighbor))
                relaxed = True
        if not relaxed:
            print("无可松弛边")
        step += 1
    print("-" * 70)
    return distances, predecessors

def reconstruct_path(predecessors: Dict[str, str], start: str, end: str) -> List[str]:
    """重构最短路径"""
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = predecessors[current]
    path.reverse()
    if path[0] == start:
        return path
    return None

# 示例用法
if __name__ == "__main__":
    graph = Graph()
    graph.add_edge('A', 'B', 4)
    graph.add_edge('A', 'C', 2)
    graph.add_edge('B', 'C', 1)
    graph.add_edge('B', 'D', 5)
    graph.add_edge('C', 'D', 8)
    graph.add_edge('C', 'E', 10)
    graph.add_edge('D', 'E', 2)
    print("图的邻接表：")
    for u in sorted(graph.adj.keys()):
        edges = ', '.join([f"{v}({w})" for v, w in graph.adj[u]])
        print(f" {u} → [{edges}]")
    distances, predecessors = dijkstra(graph, 'A')
    print("\n算法结果：")
    print("=" * 70)
    print(f"{'顶点':<10}{'最短距离':<12}{'路径'}")
    print("-" * 70)
    for v in sorted(distances.keys()):
        if distances[v] == float('infinity'):
            path = "不可达"
        else:
            path = reconstruct_path(predecessors, 'A', v)
            path_str = ' → '.join(path)
        print(f"{v:<10}{distances[v]:<12}{path_str}")
    print("=" * 70)

输出：

图的邻接表：A → [B(4), C(2)] B → [C(1), D(5)] C → [B(1), D(8), E(10)] D → [B(5), C(8), E(2)] E → [C(10), D(2)] Dijkstra 算法执行过程： ====================================================================== 步骤 当前顶点 距离 操作 ---------------------------------------------------------------------- 1 A 0 松弛 A→B(4) 2 C 2 松弛 C→B(1) 3 B 3 松弛 B→D(5) 4 E 5 无可松弛边 5 D 8 无可松弛边 ---------------------------------------------------------------------- 算法结果： ====================================================================== 顶点 最短距离 路径 ---------------------------------------------------------------------- A 0 A B 3 A → C → B C 2 A → C D 8 A → C → B → D E 5 A → C → D → E ====================================================================== 

复杂度分析

• 时间复杂度：O((V + E) log V)
  • 使用优先队列（二叉堆）
  • 每个顶点入堆一次：O(V log V)
  • 每条边可能导致一次松弛：O(E log V)
• 空间复杂度：O(V + E)

与其他算法对比

4.6 最小生成树

问题描述

给定带权无向连通图 G = (V, E)，求一棵生成树 T，使得 T 中所有边的权值之和最小。

示例：

图：A---4---B
| \ |
2 1 3
| \ |
C---5---D
求：最小生成树 

解题思路

最小生成树的性质

割性质（Cut Property）：对于图的任意割，横跨该割的最小权边必属于某个 MST

环性质（Cycle Property）：对于图中的任意环，该环中权值最大的边必不属于任何 MST

Prim 算法

贪心策略：从已选顶点集选择最小权值边

算法步骤：

1. 从任意顶点开始，将其加入已选顶点集 S
2. 重复以下步骤，直到 S = V：
   • 在所有横跨割 (S, V-S) 的边中，选择权值最小的边 (u, v)
   • 将 v 和边 (u, v) 加入 MST

复杂度：O((V + E) log V)

Kruskal 算法

贪心策略：全局选择最小权值边

算法步骤：

1. 将所有边按权值从小到大排序
2. 初始化空边集 T
3. 依次检查每条边 (u, v)：
   • 如果 u 和 v 不连通，将边加入 T
   • 否则，跳过（会形成环）
4. 直到 |T| = |V| - 1

复杂度：O(E log E)

两种算法对比

Python 实现

import heapq
from typing import Dict, List, Tuple, Set
from collections import defaultdict

class Graph:
    """图类"""
    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self, u: str, v: str, weight: int):
        """添加无向边"""
        self.adj[u].append((v, weight))
        self.adj[v].append((u, weight))

    def edges(self) -> List[Tuple[int, str, str]]:
        """获取所有边"""
        edges = set()
        for u in self.adj:
            for v, w in self.adj[u]:
                if u < v:  # 避免重复
                    edges.add((w, u, v))
        return sorted(edges)

class UnionFind:
    """并查集（带路径压缩和按秩合并）"""
    def __init__(self, vertices: Set[str]):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, x: str) -> str:
        """查找（带路径压缩）"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: str, y: str) -> bool:
        """合并（返回是否成功）"""
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        # 按秩合并
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

def prim_mst(graph: Graph, start: str) -> Tuple[List[Tuple[str, str, int]], int]:
    """Prim 算法实现"""
    pq = [(0, start, None)]
    visited = set()
    mst_edges = []
    total_weight = 0
    print("\nPrim 算法执行过程：")
    print("-" * 60)
    while pq and len(visited) < len(graph.adj):
        weight, current, from_vertex = heapq.heappop(pq)
        if current in visited:
            continue
        visited.add(current)
        if from_vertex is not None:
            mst_edges.append((from_vertex, current, weight))
            total_weight += weight
            print(f"添加边：{from_vertex}-{current} (权值:{weight}), 累计:{total_weight}")
        for neighbor, edge_weight in graph.adj[current]:
            if neighbor not in visited:
                heapq.heappush(pq, (edge_weight, neighbor, current))
    return mst_edges, total_weight

def kruskal_mst(graph: Graph) -> Tuple[List[Tuple[str, str, int]], int]:
    """Kruskal 算法实现"""
    edges = graph.edges()
    vertices = set(graph.adj.keys())
    for u in graph.adj:
        for v, _ in graph.adj[u]:
            vertices.add(v)
    uf = UnionFind(vertices)
    mst_edges = []
    total_weight = 0
    print("\nKruskal 算法执行过程：")
    print("-" * 60)
    for weight, u, v in edges:
        if uf.union(u, v):
            mst_edges.append((u, v, weight))
            total_weight += weight
            print(f"选择边：{u}-{v} (权值:{weight}), 累计:{total_weight}")
        else:
            print(f"跳过边：{u}-{v} (形成环)")
        if len(mst_edges) == len(vertices) - 1:
            break
    return mst_edges, total_weight

# 示例用法
if __name__ == "__main__":
    graph = Graph()
    graph.add_edge('A', 'B', 4)
    graph.add_edge('A', 'C', 4)
    graph.add_edge('B', 'C', 2)
    graph.add_edge('B', 'D', 3)
    graph.add_edge('C', 'D', 5)
    graph.add_edge('C', 'E', 2)
    graph.add_edge('D', 'E', 1)
    print("图的邻接表：")
    for u in sorted(graph.adj.keys()):
        edges = ', '.join([f"{v}({w})" for v, w in graph.adj[u]])
        print(f" {u} → [{edges}]")
    # Prim 算法
    prim_edges, prim_weight = prim_mst(graph, 'A')
    print(f"\nPrim 算法结果：")
    print(f" MST 边数：{len(prim_edges)}")
    print(f" 总权值：{prim_weight}")
    # Kruskal 算法
    kruskal_edges, kruskal_weight = kruskal_mst(graph)
    print(f"\nKruskal 算法结果：")
    print(f" MST 边数：{len(kruskal_edges)}")
    print(f" 总权值：{kruskal_weight}")

复杂度分析

Prim 算法：

• 时间复杂度：O((V + E) log V)
• 空间复杂度：O(V + E)

Kruskal 算法：

• 时间复杂度：O(E log E)
• 空间复杂度：O(V)

4.7 多机调度问题

问题描述

有 n 个作业需要分配给 m 台相同的机器并行处理，每个作业 i 有处理时间 t[i]。目标是最小化所有作业的最大完成时间（makespan）。

注意：这是一个 NP 难问题，因此讨论近似算法。

示例：

作业时间：[8, 7, 6, 5, 4, 3, 2, 1] 
机器数量：3 
求：最小化最大完成时间 

解题思路

LPT 算法

贪心策略：Longest Processing Time first（长作业优先）

算法步骤：

1. 将作业按处理时间从大到小排序
2. 依次分配给当前负载最小的机器

近似比：4/3 - 1/(3m)

正确性分析

LPT 算法不能保证得到最优解，但可以保证近似解不超过最优解的 4/3 倍。

定理：LPT 算法的近似比为 4/3 - 1/(3m)。

Python 实现

import heapq
from typing import List, Tuple

def lpt_schedule(jobs: List[int], m: int) -> Tuple[List[List[int]], int]:
    """
    LPT 算法求解多机调度问题
    参数:
        jobs: 作业处理时间列表
        m: 机器数量
    返回:
        (调度方案，makespan)
    """
    # 按处理时间从大到小排序
    sorted_jobs = sorted(jobs, reverse=True)
    # 最小堆：(机器负载，机器编号)
    heap = [(0, i) for i in range(m)]
    heapq.heapify(heap)
    # 调度结果
    schedules = [[] for _ in range(m)]
    print(f"\nLPT 算法执行过程（{m}台机器）：")
    print("-" * 60)
    for job_time in sorted_jobs:
        load, machine = heapq.heappop(heap)
        schedules[machine].append(job_time)
        new_load = load + job_time
        heapq.heappush(heap, (new_load, machine))
        print(f"作业{job_time} → 机器{machine+1} (负载:{load}→{new_load})")
    # 计算 makespan
    makespan = max(load for load, _ in heap)
    print("-" * 60)
    return schedules, makespan

# 示例用法
if __name__ == "__main__":
    jobs = [8, 7, 6, 5, 4, 3, 2, 1]
    m = 3
    print(f"作业时间：{jobs}")
    print(f"机器数量：{m}")
    schedules, makespan = lpt_schedule(jobs, m)
    print(f"\n最终调度：")
    for i, schedule in enumerate(schedules, 1):
        total = sum(schedule)
        jobs_str = ' + '.join(map(str, schedule))
        print(f" 机器{i}: {jobs_str} = {total}")
    print(f"\nMakespan: {makespan}")

复杂度分析

• 时间复杂度：O(n log n)
  • 排序：O(n log n)
  • 堆操作：O(n log m)
• 空间复杂度：O(n + m)

练习题

概念题

1. 什么是贪心选择性质？它与动态规划的最优子结构性质有什么区别？
2. 为什么活动安排问题可以按结束时间排序贪心选择，而不能按开始时间排序？
3. 哈夫曼编码为什么能保证是最优前缀编码？
4. Dijkstra 算法为什么要求边权非负？如果有负边权会怎样？
5. 最小生成树的割性质和环性质分别是什么？如何用于证明算法正确性？

证明题

1. 证明最优装载问题中，按重量最轻优先装载的贪心策略能获得最优解。
2. 证明 Prim 算法的正确性（使用割性质）。
3. 证明 Kruskal 算法的正确性（使用环性质）。
4. 证明 LPT 算法的近似比为 4/3 - 1/(3m)。
5. 证明哈夫曼编码生成的编码树是最优的。

编程题

1. 活动安排问题：给定 n 个活动的开始和结束时间，求最多能安排多少个相容活动。
2. 最优装载问题：给定 n 个集装箱的重量和船的载重量，求最多能装多少个集装箱。
3. 哈夫曼编码：给定一段文本，构造哈夫曼编码树，计算压缩率。
4. Dijkstra 算法：实现 Dijkstra 算法，并输出从源点到所有其他顶点的最短路径。
5. 最小生成树：分别实现 Prim 算法和 Kruskal 算法，对比它们的性能。

本章小结

贪心算法的两个基本要素

1. 贪心选择性质：可以通过做出局部最优选择来达到全局最优
2. 最优子结构性质：问题的最优解包含子问题的最优解

贪心算法 vs 动态规划

经典贪心算法总结

关键要点

1. 贪心选择性质是贪心算法可行性的关键
2. 最优子结构性质使得可以递归地构造最优解
3. 贪心策略的正确性需要通过归纳法、反证法或交换论证来证明
4. 贪心算法通常具有更低的时间和空间复杂度
5. 对于 NP 难问题，贪心算法可以作为近似算法

学习建议

1. 理解每个问题的贪心策略为什么有效
2. 掌握贪心策略正确性的证明方法
3. 通过练习识别哪些问题适合用贪心算法
4. 对比贪心算法与动态规划的适用场景
5. 实现并运行贪心算法，加深理解