第14章+：归约与 NP 完全性（可选深入）

Vol 2：算法森林探险 · 第14+站：复杂度暗区

---

你在哪

森林最深处，你发现了一些没有人能解决的问题——有些问题看起来不同但其实是一回事（归约），它们都属于一个叫 NP-Complete 的神秘家族。

你已经在算法森林里走了十四站。O(n log n) 的排序随手写，动态规划信手拈来，图的遍历更是闭着眼睛都能画。

但最近你遇到了几道题——旅行商要跑遍所有驿站、物资箱里塞哪几样东西价值最高、排课表怎么不冲突。你试了所有招数，代码跑 n=30 就开始卡，n=50 直接罢工。

你不是代码写得烂。你是遇到了算法森林里的"暗区"——那里面的问题，所有人来了都得跪。

这章讲的就是：如何判断一个问题是"本来就难"而不是"你没写对"，以及真遇到了怎么活下来。

---

📌 本章为可选深入，主要回答"为什么有些问题不要硬求最优"。 不要求掌握形式化证明。

你的任务

本章分层

• 必读：理解 P vs NP 的核心直觉（验证容易 ≠ 求解容易）；知道什么时候该放弃求最优（近似算法、启发式）
• 选读：归约的基本概念（把问题 A 翻译成问题 B）；识别几个经典 NP-hard 问题（TSP、背包、顶点覆盖）
• 深水区：归约的形式化证明——放在附录

本章不会要求你掌握

• 3-SAT 的归约证明（附录内容，知道"3-SAT 是第一个 NP-complete 问题"就够了）
• Cook-Levin 定理的完整证明
• P vs NP 的形式化证明

学完这一章，你要能做到这五件事：

1. 区分 P、NP、NP-complete、NP-hard——不是背定义，是真懂边界在哪。
2. 理解归约的核心思想——把问题 A "翻译"成问题 B，证明 A 不比 B 难。
3. 理解为什么 3-SAT 是"归约的通用语"——所有 NP-complete 问题的源头。
4. 识别几个经典 NP-hard 问题——顶点覆盖、哈密顿路径、背包问题。
5. 知道遇到 NP-hard 时怎么活——近似算法、启发式、参数化。不是每道题都要最优解。

---

遭遇战：林间信使的难题

你帮驿站规划物资分发路线。长老给你 15 个营地的距离表，说："排一条最短路线，每个营地都要到，一个都不能少。"

你信心满满地写下回溯搜索：

# 暴力版 · 旅行商问题（TSP）
# 遍历所有排列，找出最短回路
import itertools, math

def tsp_bruteforce(cities, dist):
    n = len(cities)
    best = math.inf
    best_route = None
    for perm in itertools.permutations(range(n)):
        d = sum(dist[perm[i]][perm[i+1]] for i in range(n-1))
        d += dist[perm[-1]][perm[0]]  # 回到起点
        if d < best:
            best = d
            best_route = perm
    return best, best_route

# 15 个城市
cities = list(range(15))
dist = [[abs(i-j) * (1 + (i+j)%3) for j in range(15)] for i in range(15)]

print(f"最短距离: {tsp_bruteforce(cities, dist)[0]}")

n=10 时程序还眨一下眼。n=15 时你等了一分钟。n=20 时你去倒水回来还没跑完。n=30 时——这台电脑大概跑到宇宙热寂也算不完。

问题在哪？ 全排列的数量是 n!。15! = 1.3 万亿。你不可能枚举完。

你去做学术搜索，论文说：TSP 是 NP-hard。没有人能在多项式时间里求出最优解。

你不信邪，写了个贪心：

# 贪心版 · 最近邻法
def tsp_greedy(cities, dist, start=0):
    n = len(cities)
    visited = {start}
    route = [start]
    curr = start
    while len(visited) < n:
        next_city = min(
            (c for c in range(n) if c not in visited),
            key=lambda c: dist[curr][c]
        )
        visited.add(next_city)
        route.append(next_city)
        curr = next_city
    return route, sum(dist[route[i]][route[i+1]] for i in range(n-1)) + dist[route[-1]][route[0]]

distances, route = tsp_greedy(cities, dist)
print(f"贪心最短距离: {distances}")

这回秒出了。但是——不一定最优。有时候最优是 100，贪心给你 120。你觉得这 20% 的损失能接受吗？

欢迎来到 NP-hard 的世界。 没人给你保证最优解。你要做的不是"找最优"，而是"找能接受的"。

** Java 差异：** Java 里全排列用 Collections2.permutations(list)（Guava 库）。但一样是 O(n!)。别幻想换语言能换复杂度——复杂度是问题本身的属性，不是语言特性。 贪心版的 Java 实现比 Python 快几十倍（常数因子），但算法框架完全一样。

** C++ 差异：** C++ 的 std::next_permutation 按字典序逐个生成排列，O(n!) 跑满。贪心版本用 std::priority_queue 优化最近邻查找可以降到 O(n log n)。但要记住：优化贪心不减损失率。 你还是可能比最优差 20%。

---

常见陷阱：P、NP 与非确定性

1. 先给"难"下一个精确的定义

计算机科学家花了几十年想弄清楚一件事：到底哪些问题有"高效算法"？

他们把所有问题分成几个大类：

┌─────────────────────────────────────┐
│             NP-hard                 │
│  ┌────────────────────────────┐     │
│  │        NP-complete         │     │
│  │  ┌──────────────────┐     │     │
│  │  │       NP         │     │     │
│  │  │  ┌────────────┐  │     │     │
│  │  │  │     P      │  │     │     │
│  │  │  │            │  │     │     │
│  │  │  │ 排序, 查找 │  │     │     │
│  │  │  │ 最短路, DP │  │     │     │
│  │  │  └────────────┘  │     │     │
│  │  │                  │     │     │
│  │  │  3-SAT, 顶点覆盖 │     │     │
│  │  │  Subset Sum      │     │     │
│  │  └──────────────────┘     │     │
│  │                           │     │
│  │  停机问题（不可判定）     │     │
│  └───────────────────────────┘     │
└─────────────────────────────────────┘

P（Polynomial Time）： 能在多项式时间内求解的问题。排序、查找、最短路、动态规划的绝大多数场景都是 P。**解决了。"

NP（Nondeterministic Polynomial Time）： 给我一个"候选答案"，我能在多项式时间内验证它对不对。验证容易，求解不一定。

举个例子：数独的解。给你一个填满的数独棋盘，你花几秒钟就能验证它是否符合规则。但要你自己从头解一个高难度数独——可能要花几小时。验证易，求解难。 这就是 NP 的含义。

非确定性（Nondeterministic）这个修饰词来自历史——理论上说，如果有一台"神奇机器"每次都能猜中正确答案，那 NP 问题也能在多项式时间内求解。但现实中没有这种机器，所以 Nondeterministic 代表了一种"如果猜得对就能快"的理想化模型。

NP-complete： NP 里最难的问题。任何一个 NP 问题都可以在多项式时间内归约到它。 这意味着——如果你给其中一个找到了多项式解法，所有 NP 问题都解决了（P = NP）。

NP-hard： 至少和 NP-complete 一样难，甚至更难。不一定在 NP 集合里（比如 TSP 的通用版本就是 NP-hard，因为它的判定版本才是 NP-complete）。

P vs NP 百万美元问题： P 是否等于 NP？如果 P = NP，意味着所有验证容易的问题都能高效求解——密码学崩塌、数学证明自动发现、药物分子设计自动化。大多数人相信 P ≠ NP，但没人能证明。

2. 归约（Reduction）——把难题翻译成另一道难题（附录）

归约的形式化证明属于深水区。 主线理解"归约是把问题 A 翻译成问题 B"这个直觉就够了。

归约是 NP 理论最核心的技术。它的思想很简单：

如果你能把问题 A 的任意实例，在多项式时间内转换成问题 B 的一个实例，并且 B 的解就是 A 的解——那就证明 A 不比 B 难。

记作：A ≤_p B（A 能多项式归约到 B）。

实操一把。我们来证明顶点覆盖问题可以归约到独立集问题。

顶点覆盖（Vertex Cover）： 给你一个图和一个数 k，问能不能选出 ≤k 个顶点，使得每条边至少有一个端点被选中。

独立集（Independent Set）： 给你一个图和一个数 k，问能不能选出 ≥k 个顶点，使得这些顶点之间没有任何边相连。

这两者其实是互补的：

# 归约：顶点覆盖 → 独立集
def vertex_cover_to_independent_set(graph, k):
    """
    输入: graph (邻接表), k
    归约逻辑: 在图 G 中找一个大小为 k 的顶点覆盖 ↔
              在图 G 中找一个大小为 n-k 的独立集
    因为: 一个顶点覆盖以外的所有点，两两之间不可能有边相连
    """
    n = len(graph)
    # 直接翻译
    target_size = n - k
    # 图不变，只是目标大小翻转为 n-k
    return graph, target_size

# 演示
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
k = 2  # 顶点覆盖大小
print(f"顶点覆盖 k={k} → 独立集目标大小 n-k={len(graph)-k}")

你本质上做了一次"补集翻译"——不用动图的结构，只是把约束反过来。

** Java 差异：** Java 里做图的归约同样简单——只是语法更冗长。核心是算法逻辑的翻译，不是语言技巧。

** C++ 差异：** C++ 的 std::bitset 在处理小规模图归约时非常高效（O(1) 的位操作检查边是否存在），但大规模图还是邻接表。

附录：3-SAT —— 归约的"万用砖"

附录内容，不影响主线。 知道"3-SAT 是第一个被证明为 NP-complete 的问题"即可。

3-SAT 是 NP-complete 理论中的"原子问题"——所有的 NP-complete 问题的第一次归约，都是归约到 SAT 或者 3-SAT。

什么是 3-SAT？

• 你有 n 个布尔变量：x₁, x₂, ..., xₙ
• 你有 m 个子句（clause），每个子句是三个变量的析取（OR）
• 问：是否存在一组赋值使所有子句都为真（整个公式为真）？

(x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ x₄) ∧ (x₂ ∨ ¬x₃ ∨ ¬x₄)

这是第一个被证明为 NP-complete 的问题（Cook-Levin 定理，1971）。证明过程极其复杂——但它的意义是：只要你能把问题归约成 3-SAT，它至少是 NP-hard。

# 3-SAT 求解器（暴力回溯——n 小的时候能用）
def three_sat_bruteforce(vars, clauses):
    """
    vars: ['x1', 'x2', 'x3', 'x4']
    clauses: [('x1', '-x2', 'x3'), ('-x1', 'x2', 'x4'), ...]
    返回: (True, {赋值}) 或 (False, None)
    """
    from itertools import product
    for bits in product([True, False], repeat=len(vars)):
        assignment = {v: bits[i] for i, v in enumerate(vars)}
        satisfied = True
        for clause in clauses:
            clause_ok = False
            for lit in clause:
                if lit.startswith('-'):
                    var = lit[1:]
                    clause_ok = clause_ok or (not assignment[var])
                else:
                    clause_ok = clause_ok or assignment[lit]
            if not clause_ok:
                satisfied = False
                break
        if satisfied:
            return True, assignment
    return False, None

clauses = [('x1', '-x2', 'x3'), ('-x1', 'x2', 'x4'), ('x2', '-x3', '-x4')]
ok, assn = three_sat_bruteforce(['x1','x2','x3','x4'], clauses)
print(f"可满足: {ok}, 赋值: {assn}")
# 假设输出: 可满足: True, 赋值: {'x1': True, 'x2': False, 'x3': True, 'x4': True}

变量 4 个时瞬间出结果。变量 100 个时——2¹⁰⁰ 种组合，暴力没戏。

4. 经典 NP-hard 问题群像

顶点覆盖（Vertex Cover）

# 近似算法：2-近似顶点覆盖
def approx_vertex_cover(graph):
    """
    贪心选边 -> 把两端都加入覆盖集
    保证覆盖大小 ≤ 2 × 最优
    """
    n = len(graph)
    covered = set()
    edges = set()
    for u in graph:
        for v in graph[u]:
            if u < v:
                edges.add((u, v))

    selected = set()
    while edges:
        u, v = edges.pop()
        selected.add(u)
        selected.add(v)
        # 删除与 u 或 v 相连的所有边
        to_remove = set()
        for e in edges:
            if e[0] in (u, v) or e[1] in (u, v):
                to_remove.add(e)
        edges -= to_remove
    return selected

g = {0: [1,2], 1: [0,2,3], 2: [0,1,3], 3: [1,2]}
print(f"近似顶点覆盖: {approx_vertex_cover(g)}")
# 假设输出: 近似顶点覆盖: {0, 1}  # 最优就是2个顶点

这个 2-近似算法的直觉是：每次选一条边，把两个端点都放进覆盖集。最优解至少需要选其中一个端点，所以你最多比最优多一倍。

哈密顿路径（Hamiltonian Path）

给你一张图，问是否存在一条路径经过每个顶点恰好一次。

# 哈密顿路径判定（回溯 + 剪枝）
def has_hamiltonian_path(graph):
    n = len(graph)
    visited = [False] * n

    def dfs(v, count):
        if count == n:
            return True
        for w in graph[v]:
            if not visited[w]:
                visited[w] = True
                if dfs(w, count + 1):
                    return True
                visited[w] = False
        return False

    for start in range(n):
        visited[start] = True
        if dfs(start, 1):
            return True
        visited[start] = False
    return False

g_yes = {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]}
g_no  = {0: [1], 1: [0], 2: [3], 3: [2]}  # 两个孤立对
print(f"有哈密顿路径: {has_hamiltonian_path(g_yes)}")  # True
print(f"有哈密顿路径: {has_hamiltonian_path(g_no)}")   # False

0-1 背包问题（NP-hard）

# 0-1 背包的伪多项式 DP（已在第13章详细讨论）
# 这里展示近似解法：贪心按价值密度排序
def knapsack_greedy_approx(values, weights, capacity):
    """
    近似解法：按 value/weight 比从优到劣取物品
    近似的坏处：没有最优保证，但案例中通常不差太多
    """
    n = len(values)
    items = list(range(n))
    items.sort(key=lambda i: values[i] / weights[i], reverse=True)

    total_val = 0
    total_wt = 0
    chosen = []
    for i in items:
        if total_wt + weights[i] <= capacity:
            chosen.append(i)
            total_wt += weights[i]
            total_val += values[i]
    return chosen, total_val

v = [60, 100, 120]
w = [10, 20, 30]
c = 50
chosen, val = knapsack_greedy_approx(v, w, c)
print(f"贪心选取物品: {chosen}, 总价值: {val}, 容量: {sum(w[i] for i in chosen)}")
# 输出可能是 [0, 1] 价值=160 或 [1, 2] 价值=220 取决于密度排序

** Java 差异：** Java 用 Arrays.sort + Comparator.comparingDouble 做密度排序。伪多项式 DP 的空间可以用一维数组优化成 O(capacity)。容量大时还是内存爆炸。

** C++ 差异：** C++ 的 std::nth_element 可以做快速选择（不用完全排序），在近似算法的常数优化上有优势。但贪心的近似比（approximation ratio）是语言无关的。

---

通关挑战

1. 徒手归约：证明"独立集 ≤_p 团问题（Clique）"——图 G 中的独立集 ↔ 补图 G' 中的团。给出代码证明。

2. 3-SAT → 顶点覆盖：已知顶点覆盖是 NP-complete，你能想通为什么 3-SAT 可以归约到顶点覆盖吗？（提示：用子句-变量结构图）

3. 近似比分析：0-1 背包的贪心按密度取，最坏情况下会差多少？构造一个反例使贪心解的比值无限差。

👆 参考答案

1. 独立集指集合内无边相连。补图中原来没有边的变成了有边。所以原图的独立集就是补图中的团。

2. 创建"子句-变量图"：每个子句是一个三角形（覆盖约束），每个变量是两点连线（真假选择）。子句与变量之间的边代表文字的对应关系。大小为 k 的顶点覆盖对应着满足所有子句的赋值。

3. 容量 100，两个物品：(v=101, w=100), (v=100, w=100)。密度贪心会选第一个（价值 101），但最优是选第二个（价值 100）——所以贪心反而更好。真正的坏案例需要更精心构造，最多差到任意大比值。

---

验收标准

读完本章后，你能：

• [ ] 解释 P、NP、NP-complete、NP-hard 的核心区别——用你自己的话
• [ ] 理解归约的核心思想（把问题 A 翻译成问题 B）
• [ ] 理解 3-SAT 为什么是"所有 NP-complete 问题的母亲"
• [ ] 能认出一个问题是不是 NP-hard（直觉判断）
• [ ] 面对 NP-hard 问题时，知道降级选择：近似算法 / 启发式 / 参数化 / 精确但小规模
• [ ] 本章不要求形式化证明——理解概念和直觉即可

---

常见卡点

卡点	真相
"归约必须写完整的代码？"	不需要。归约的核心是转换的逻辑正确性——你怎么把问题 A 的实例变成问题 B 的实例，以及为什么 B 的解能翻译回 A 的解
"NP-complete 就是所有难题"	不是。停机问题比任何 NP 问题都难——它根本不可判定，连"验证答案"都做不到
"我的问题找不到多项式解，所以它是 NP-hard"	不一定。你可能只是没有找到正确的 DP 或特殊结构。许多问题在受限条件下是 P
"近似算法 = 2-近似"	部分正确。近似比可以是任意函数。PTAS（Polynomial-Time Approximation Scheme）可以把近似比做得任意接近 1——但代价是运行时间随精度指数爆炸

---

现在不需要理解

• Cook-Levin 定理的具体证明——知道"SAT 是第一个 NP-complete 问题"就够了，证明过程繁复且对日常帮助不大
• P ≠ NP 的严格形式化证明——如果有谁教会了你这个，先去领 Clay Institute 的百万美元奖金
• 量子计算能不能解决 NP-complete 问题——QC 只能提供平方加速（Grover 搜索），不能把指数降到多项式
• 随机化归约——确定性归约（多对一归约）是够用的，随机化归约是进阶话题

---

旅人笔记

• NP-complete 的真正价值不是"这问题难"，而是"别怪自己没写对"。 很多工程师面对 NP-hard 问题的第一反应是"我的算法不够好"——其实不是，这个问题本身就没有高效的通用解法。知道这个事实本身就能省掉你几周的瞎折腾。
• 归约是一种思维模型。 当你遇到新问题，第一反应是"这像哪个已知问题？"——你已经掌握了归约思维。只是实际工作中你不需要严格证明，只要找到类比就行。
• 近似算法在工业界比精确算法值钱 10 倍。 Google Maps 给你的路线不保证绝对最优——但它在几百毫秒内给你足够好的路线。"够好 + 够快"胜过"完美 + 跑不动"。
• 面试考不考 NP？ 很少直接考。但面试官问你"这个问题最坏情况复杂度会怎样"时，你能说出"这本质上是一个 3-SAT 归约下来的装箱问题，没有多项式解法"——你立刻从"不错"变成"让人印象深刻"。
• 知道一个问题是 NP-hard 不等于放弃。 大部分现实问题有特殊结构：图不大、数据有规律、可以接受有界误差。参数化算法（如固定参数可解 FPT）就是针对这种"理论上难，实际上能解"的场景。

---

📋 应对 NP-hard 的实战工具箱

策略	适用场景	代价
精确搜索 + 剪枝	n ≤ 30，问题规模小	指数时间
近似算法（2-近似/PTAS）	能接受有界误差	损失最优性
启发式（贪心/模拟退火/遗传算法）	不需要理论保证	无界误差，但通常工程可接受
参数化算法（FPT）	某个参数（如树宽）小	指数只依赖参数
分支限界 + 松弛（LP/ILP）	小到中等规模，需要精确解	求解时间不可预测
直接用现成 solver	不想自己实现	依赖第三方求解器

---

→ 下一站预告

第14章+（第二篇）：摊还分析

NP-complete 那边讲的是"有的问题本身就难，别白费力气"。而摊还分析这边讲的是另一种智慧——个别操作可能很贵，但长期平均下来很便宜。

从动态数组的 push_back 到 splay 树的查找——摊还分析帮你解释为什么这些结构在实际中比最坏情况快得多。