📐 组合优化导论

从理论到实践 · 第1章
组合优化定义 P与NP问题 NP完全性 NP难问题 TSP · 背包 · 图着色

🔍 组合优化问题定义

组合优化 (Combinatorial Optimization) 是在离散结构上寻找最优解的过程。 一个组合优化问题由 实例 (Instance)、可行解集合 (S) 以及 目标函数 (f) 构成， 目标是找到 最小化 (或最大化) f(x) 的可行解 x ∈ S。 例如：旅行商问题 (TSP) 在图中找最短哈密顿回路；背包问题在容量限制下最大化价值。

🧠 P 与 NP 问题

类别含义典型特征例子
P多项式时间可解存在确定型算法 O(nᵏ)最短路径、最小生成树
NP非确定性多项式时间可验证解可在多项式时间验证哈密顿回路、SAT
NP-完全NP中最难的问题所有NP问题可归约到它3-SAT、顶点覆盖
NP-难至少与NP问题一样难不一定是NP，但所有NP可归约TSP优化、停机问题

⚡ NP完全性 (NP-Completeness)

若问题 Q 满足 (1) Q ∈ NP, (2) 所有 NP 问题均可多项式归约到 Q，则 Q 是 NP-完全 的。 它是“NP中最难的问题”。第一个NP完全问题是 Cook-Levin定理 中的 SAT。

🔥 NP难问题 (NP-Hard)

NP-难问题不要求属于NP，但所有NP问题都能归约到它。 例如 TSP 优化版本（不是判定版本）是NP-难的，甚至可能不可判定。 许多现实调度、布局问题都是NP-难。

📌 经典问题概览

P NP NP-C NP-Hard
📊 P, NP, NP-C, NP-Hard 关系
TSP 回路
🗺️ 旅行商问题 (TSP)
🎒 v=5 v=8 v=3 0-1背包
📦 背包问题 (Knapsack)
图着色 (3色)
🎨 图着色问题

🧪 代码片段 · TSP暴力搜索 (Python)

# 组合优化导论 · TSP暴力枚举 (小规模)
import itertools

def tsp_bruteforce(dist_matrix):
    n = len(dist_matrix)
    cities = list(range(n))
    min_cost = float('inf')
    best_route = None
    for perm in itertools.permutations(cities[1:]):
        route = (0,) + perm + (0,)
        cost = sum(dist_matrix[route[i]][route[i+1]] for i in range(n))
        if cost < min_cost:
            min_cost = cost
            best_route = route
    return best_route, min_cost

# 示例距离矩阵 (4城市)
dist = [[0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]]
route, cost = tsp_bruteforce(dist)
print(f"最优路线: {route}, 总距离: {cost}")

📋 经典组合优化问题一览

问题输入目标复杂度
旅行商 (TSP)完全图 + 边权最小哈密顿回路NP-难
0-1背包物品重量/价值, 容量最大化价值NP-完全
图着色无向图, 颜色数k是否存在k-着色NP-完全 (k≥3)
顶点覆盖图, 整数k是否存在≤k顶点覆盖所有边NP-完全
最大团图, 整数k是否存在大小为k的团NP-完全
📚 课程资料