元数据卡
- 前置知识：ch14-greedy（复杂度直觉）
- 预计时间：25 分钟
- 核心难度：进阶
- 完成标志：能解释 P/NP/NP-complete/NP-hard 的区别，知道面对 NP-hard 怎么活
你的进度
贪心和 DP 你都会了。但你遇到了一些奇怪的问题：旅行商要走遍所有驿站，你试了所有招数，n=30 就卡死。你不是代码写得烂——你是遇到了计算复杂度的暗区。
你的任务 理解 P vs NP 的核心直觉，学会归约思维，认识几个经典 NP-complete 问题，知道遇到它们时怎么活。
P、NP、NP-complete、NP-hard
P： 能在多项式时间内求解。排序、查找、最短路、DP——多数属于 P。
NP： 给个"候选答案"能在多项式时间内验证。验证容易，求解不一定。比如数独——填满的棋盘几秒验证完，但从头解可能花几小时。
NP-complete： NP 里最难的问题。任何一个 NP 问题都可以归约到它。找到一个 NP-complete 的多项式解法，所有 NP 问题都解决了（P = NP）。
NP-hard： 至少和 NP-complete 一样难。可能不在 NP 里。
NP-hard
+-------------------------+
| NP-complete |
| +-------------------+ |
| | NP | |
| | +------+ | |
| | | P | | |
| | | 排序 | | |
| | +------+ | |
| | 3-SAT 顶点覆盖 | |
| +-------------------+ |
| 停机问题（不可判定） |
+-------------------------+归约——把难题翻译成另一道
把问题 A 的实例在多项式时间内转换成问题 B 的实例，且 B 的解就是 A 的解。记作 A <=_p B。
顶点覆盖 -> 独立集：补集翻译。
python
def vertex_cover_to_independent_set(graph, k):
return graph, len(graph) - k经典 NPC 问题
旅行商问题（TSP）： n 个城市，找最短回路。暴力 O(n!)。n=30 时 30! 约 2.65e32，算不完。
python
def tsp_nearest_neighbor(dist, start=0):
n = len(dist)
visited, route = {start}, [start]
cur = start
while len(visited) < n:
nxt = min((c for c in range(n) if c not in visited),
key=lambda c: dist[cur][c])
visited.add(nxt); route.append(nxt); cur = nxt
route.append(start)
total = sum(dist[route[i]][route[i+1]] for i in range(n))
return route, total
dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
route, total = tsp_nearest_neighbor(dist)
print(f"路线: {route}, 距离: {total}")
# 预期: 路线: [0,1,3,2,0], 距离: 80顶点覆盖 2-近似：
python
def approx_vertex_cover(graph):
edges = {(u,v) for u in graph for v in graph[u] if u < v}
selected = set()
while edges:
u,v = edges.pop()
selected.update([u,v])
edges -= {(a,b) for (a,b) in edges if a in (u,v) or b in (u,v)}
return selected
g = {0:[1,2],1:[0,2,3],2:[0,1,3],3:[1,2]}
print(approx_vertex_cover(g))
# 保证覆盖大小 <= 2 * 最优应对 NP-hard 的策略
| 策略 | 适用场景 | 代价 |
|---|---|---|
| 精确搜索 + 剪枝 | n <= 30 | 指数时间 |
| 近似算法 | 能接受有界误差 | 损失最优性 |
| 启发式（贪心/模拟退火） | 不需要保证 | 无界误差但可用 |
| 参数化算法（FPT） | 某参数小 | 指数只依赖参数 |
| 直接用 solver | 不想自己写 | 依赖第三方 |
心态： 知道问题是 NP-hard 不等于放弃。大部分现实问题有特殊结构——图不大、数据有规律、能接受近似。
常见陷阱
| 卡点 | 真相 |
|---|---|
| "NP-complete 就是所有难题" | 不对，停机问题更难（不可判定） |
| "归约必须写完整代码" | 不需要，核心是转换逻辑 |
| "找不到多项式解 -> NP-hard" | 不一定，可能是你没找到正确结构 |
旅人笔记
NP-complete 的价值不是"这问题难"，而是"别怪自己没写对"。知道这个事实能省掉你几周瞎折腾。近似算法在工业界比精确算法值钱 10 倍。Google Maps 不保证绝对最优——但它 200ms 内给你足够好的路线。
下一步：摊还分析
NP 讲的是"有的问题本来就难"。下一站讲另一种智慧——有些操作偶尔很贵，但长期平均很便宜。