NP 完全性与近似算法

复杂度分类

P vs NP

类别	定义	示例
P	多项式时间内可解决	排序、查找、最短路径
NP	多项式时间内可验证	Sudoku、哈密顿回路
NP-Complete	NP 中最难的问题	SAT、TSP、Knapsack
NP-Hard	至少和 NP-Complete 一样难	停机问题（不可计算）

P ⊆ NP

P ⊆ NP ⊆ EXPTIME
      ↑          ↑
  多项式验证   指数验证

著名的 NP-Complete 问题

1. SAT（布尔可满足性） - 第一个 NPC 问题
2. 旅行商问题 (TSP) - 找到访问所有城市的最短路径
3. 背包问题 - 容量限制下的最大价值
4. 哈密顿回路 - 访问每个顶点恰好一次
5. 团问题 - 找最大完全子图
6. 顶点覆盖 - 最小顶点覆盖所有边

IMPORTANT

如果一个问题被证明是 NPC 问题，目前没有已知的多项式时间解法。 面试中识别出 NPC 问题意味着：你应该尝试近似算法或启发式方法。

---

如何识别 NP-Complete 问题

特征

1. 组合爆炸 - 可能的解空间指数级增长
2. 子集/组合 - 从大量元素中选择
3. 优化问题 - 找最大/最小/最优
4. 无有效算法 - 暴力搜索不可行

经典模式

模式	可能是 NPC
"找出最小/最大的..."	优化变体可能是 NPC
"所有可能的组合..."	组合问题可能是 NPC
"划分成相等的两部分"	分割问题
"选择若干元素覆盖..."	覆盖问题

---

处理 NP-Complete 问题

1. 近似算法

给出一个"足够好"的解，而非最优解。

例子：顶点覆盖近似

def approx_vertex_cover(graph):
    """
    简单的 2-近似算法：
    找出所有的边，随机选择端点加入覆盖集
    """
    cover = set()
    edges = list(graph.edges())

    while edges:
        u, v = edges.pop()
        # 如果 u 和 v 都已在覆盖中，跳过
        # 否则，将 u 和 v 加入覆盖
        if u not in cover and v not in cover:
            cover.add(u)
            cover.add(v)
            # 移除所有与 u、v 相连的边
            edges = [(x, y) for x, y in edges if x != u and y != u and x != v and y != v]

    return cover

近似比：

• 最优解 ≤ 近似解 ≤ 2 × 最优解（上述算法）

2. 启发式算法

例子：贪心求解背包问题

def knapsack_greedy(items, capacity):
    """
    贪心近似：按单位价值排序，优先选取
    时间复杂度：O(n log n)
    """
    # 计算单位价值
    for item in items:
        item['ratio'] = item['value'] / item['weight']

    # 按单位价值排序
    sorted_items = sorted(items, key=lambda x: x['ratio'], reverse=True)

    total_value = 0
    total_weight = 0
    selected = []

    for item in sorted_items:
        if total_weight + item['weight'] <= capacity:
            selected.append(item)
            total_value += item['value']
            total_weight += item['weight']

    return {'value': total_value, 'items': selected}

3. 分支定界

系统性地枚举搜索空间，通过剪枝减少搜索量。

4. 动态规划（伪多项式）

对于某些 NPC 问题，如果数值范围有限，DP 可能可行。

例子：背包问题（数值有限制）

def knapsack_dp(items, capacity):
    """
    伪多项式时间：O(n * capacity)
    当 capacity 很大时不可行
    """
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if items[i-1]['weight'] <= w:
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - items[i-1]['weight']] + items[i-1]['value']
                )
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

---

实际面试策略

当你识别出 NPC 问题时

1. 明确指出 - "这个问题可以归约为背包问题，是 NPC 问题"
2. 解释影响 - "没有已知的多项式时间算法"
3. 提出方案 - 讨论近似算法或启发式方法
4. 协商范围 - 也许数据规模允许暴力解法

示例对话

面试官：如何设计一个广告投放系统，在预算限制下最大化收益？

你：这个问题本质上是背包问题，是 NP-Complete 的。我可以：

1. 如果数据规模小，用动态规划精确求解
2. 数据规模大时，用贪心近似（按 ROI 排序）
3. 或者用分段贪心，分批处理

---

常见 NPC 问题总结

问题	归约来源	近似难度
顶点覆盖	—	2-近似
集合覆盖	—	O(log n) 近似
装箱问题	—	1.5 近似
旅行商	—	无常数近似（除非 P=NP）
背包	—	完全伪多项式

---

参考

• 推荐资源 - 深入学习的书籍
• 问题解决模式 - 一般解题策略