第29章算法设计与分析进阶

课程目录第29章算法设计与分析进阶

第29章：算法设计与分析进阶——NP完全问题、近似算法、随机化算法、在线算法

各位同学，今天我们聊点硬核的。前面我们学了排序、查找、图论、动态规划，这些算法都有一个共同点：能在多项式时间内求出精确解。但现实世界没那么温柔。我做了十几年嵌入式系统，遇到过不少问题——比如任务调度、资源分配、路径规划——这些问题的共同特点是：你越想求最优解，计算量就越爆炸。

为什么会这样？因为这些问题很可能属于NP完全问题。这一章，我们就来直面这些“难啃的骨头”，并看看工程师们是怎么“曲线救国”的。

29.1 NP完全问题：为什么有些问题就是“算不快”？

先理清几个概念。我个人习惯把计算问题分成三类：

P类问题：能在多项式时间内求出解。比如排序、最短路径。这类问题我们前面都学过了。
NP类问题：解的正确性可以在多项式时间内验证。注意，NP不是“非多项式”，而是“非确定性多项式”。
NP完全问题：NP中最难的一类。只要其中一个能在多项式时间内求解，所有NP问题都能。

说白了，NP完全问题就是“验证容易，求解极难”。我在项目中遇到过调度问题——给一批任务分配处理器核心，目标是最小化总完成时间。直觉上觉得可以贪心，但一查文献，这是经典的多机调度问题，属于NP完全问题。嗯，这时候就别想着求精确最优解了。

核心认知：遇到NP完全问题，不要试图在多项式时间内找到精确最优解。这不是你算法水平的问题，是问题本身的性质决定的。

常见的NP完全问题包括：旅行商问题（TSP）、背包问题、顶点覆盖、图着色、3-SAT等。你想想看，这些问题的共同点是什么？组合爆炸——候选解的数量随输入规模指数增长。

29.2 近似算法：退而求其次的智慧

既然精确解算不动，那我们就退一步——不求最优，只求“足够好”。这就是近似算法的思路。

近似算法的核心指标是近似比。假设最优解是OPT，算法给出的解是ALG，那么近似比ρ定义为：

ρ = max(ALG/OPT, OPT/ALG)   // 对于最小化问题，ρ ≥ 1

ρ越接近1，算法越好。比如ρ=2，意味着算法给出的解最多是最优解的2倍。

29.2.1 顶点覆盖问题的2-近似算法

顶点覆盖问题：给定一个图，选最少的顶点，使得每条边至少有一个端点被选中。这是NP完全的。

一个简单的2-近似算法：

// 顶点覆盖的2-近似算法
// 思路：不断选一条边，把两个端点都加入覆盖集，然后删除所有关联边
VertexCoverApprox(Graph G) {
    C = ∅  // 覆盖集
    E' = G.E  // 剩余边集
    while (E' ≠ ∅) {
        从E'中任选一条边 (u, v)
        C = C ∪ {u, v}
        从E'中删除所有与u或v关联的边
    }
    return C
}

为什么是2-近似？因为最优解至少需要选每条被选边的其中一个端点，而我们选了俩。所以|C| ≤ 2·|OPT|。

我的经验：在嵌入式系统中，顶点覆盖常用于传感器网络中的覆盖优化。我曾经用这个2-近似算法做节点选择，效果出奇地好——虽然理论上保证2倍，实际跑下来往往只有1.2~1.5倍。别被理论近似比吓到，实际表现通常更好。

29.2.2 旅行商问题的近似算法

TSP问题：找一条经过所有城市且总距离最短的回路。如果满足三角不等式（两边之和大于第三边），可以用MST-based算法得到2-近似解。

// TSP的2-近似算法（满足三角不等式）
TSPApprox(G) {
    1. 计算G的最小生成树T
    2. 对T进行深度优先遍历，得到顶点序列P
    3. 去除P中的重复顶点（只保留第一次出现）
    4. 返回P作为近似TSP回路
}

这个算法的近似比是2。后来有人改进到1.5（Christofides算法），但实现复杂度高了不少。

29.3 随机化算法：用随机性打破僵局

随机化算法，说白了就是在算法中引入随机选择。你可能会问：随机不会让结果更差吗？恰恰相反，随机性有时候能帮我们避开最坏情况。

随机化算法分两类：

拉斯维加斯算法：结果一定正确，但运行时间随机。比如随机化快速排序——最坏情况概率极低。
蒙特卡洛算法：运行时间确定，但结果可能出错（错误概率可控）。比如素数检测。

29.3.1 随机化快速排序

普通快速排序最坏情况O(n²)，但随机选pivot后，最坏情况几乎不可能发生。期望时间复杂度O(n log n)。

// 随机化快速排序的核心——随机选pivot
int randomizedPartition(int arr[], int low, int high) {
    int randomIndex = low + rand() % (high - low + 1);
    swap(&arr[randomIndex], &arr[high]);  // 把随机选中的元素放到最后
    return partition(arr, low, high);     // 执行标准partition
}

我记得有一次做嵌入式系统的实时数据排序，数据分布极不均匀。用普通快排偶尔会卡顿，换成随机化版本后，性能稳定多了。

29.3.2 素数检测的蒙特卡洛算法

Miller-Rabin算法是经典的蒙特卡洛算法。它判断一个数是否为素数，如果返回“合数”，100%正确；如果返回“素数”，有极小概率出错。通过多次迭代，错误率可以降到2^(-k)。

// Miller-Rabin素数检测（简化版）
bool isPrime(int n, int k) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    
    // 将n-1写成 d * 2^s 的形式
    int d = n - 1, s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    
    for (int i = 0; i < k; i++) {
        int a = 2 + rand() % (n - 3);
        int x = powMod(a, d, n);  // a^d mod n
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int j = 0; j < s - 1; j++) {
            x = (x * x) % n;
            if (x == n - 1) { composite = false; break; }
        }
        if (composite) return false;  // 确定是合数
    }
    return true;  // 很可能是素数
}

注意：随机化算法依赖高质量的随机数生成器。在嵌入式系统中，很多平台的rand()实现质量很差。我曾经踩过这个坑——用标准库的rand()做蒙特卡洛模拟，结果周期性明显，导致错误率远高于理论值。后来改用硬件随机数生成器才解决问题。

29.4 在线算法：边输入边决策

前面讲的算法都是离线算法——所有输入数据一开始就已知。但现实世界不是这样的。你想想看：

操作系统的页面置换：不知道未来会访问哪些页面
网络路由：不知道未来会有多少流量
股票交易：不知道明天的价格

这些场景下，我们需要在线算法——数据是逐个到达的，必须在不知道未来的情况下做出决策。

在线算法的核心指标是竞争比：在线算法做出的决策与最优离线算法（知道全部未来）的比值。

29.4.1 缓存替换：LRU vs 最优策略

经典的缓存替换问题：缓存容量为k，请求序列逐个到达。如果请求的页面在缓存中，命中；否则，需要从主存调入，如果缓存已满，必须替换一个页面。

最优离线算法（Belady算法）是替换未来最远才会被访问的页面。但未来不可知，所以我们需要在线算法。

LRU（最近最少使用）是最常用的在线算法。它的竞争比是k——也就是说，在最坏情况下，LRU的缺页次数是最优算法的k倍。

关键洞察：任何确定性在线算法的竞争比至少是k。所以LRU在理论上已经是最优的确定性在线算法了。但随机化在线算法可以做得更好——竞争比可以降到O(log k)。

29.4.2 在线任务调度

在嵌入式实时系统中，任务往往是动态到达的。你不知道下一个任务什么时候来、需要多少时间。这时候就需要在线调度算法。

最简单的策略是先来先服务，但平均等待时间可能很差。最短剩余时间优先在离线场景下最优，但在线场景下可能被恶意输入欺骗。

// 在线调度中的“最坏情况”示例
// 假设处理器单核，任务按以下顺序到达：
// 时间0: 任务A，需要10ms
// 时间1: 任务B，需要10ms
// 时间2: 任务C，需要10ms
// ...
// 如果使用最短剩余时间优先，每次新任务到来都会抢占当前任务
// 结果：所有任务都无法完成，产生“饿死”现象

我曾经在项目中遇到过类似问题。一个多任务采集系统，数据包到达时间不确定。一开始用贪心策略，结果高优先级任务频繁抢占，低优先级任务永远得不到执行。后来改用比例公平调度，才解决了问题。

29.5 四种算法的对比与选择

算法类型	适用场景	保证	代价	典型应用
精确算法	P类问题，或小规模NP问题	最优解	可能指数级时间	排序、最短路径
近似算法	NP完全问题，可接受近似解	近似比保证	解不是最优	顶点覆盖、TSP
随机化算法	需要打破最坏情况，或概率性正确	高概率正确或期望时间	结果或时间有随机性	快速排序、素数检测
在线算法	数据流式到达，无法预知未来	竞争比保证	无法达到离线最优	缓存替换、任务调度

我的建议：在实际工程中，不要一上来就想着用高级算法。先问自己三个问题：

问题规模有多大？如果n很小，暴力搜索可能就够了。
真的需要最优解吗？很多时候，95%的最优解就够用了。
数据是全部已知还是流式到达？这决定了用离线还是在线算法。

我曾经见过一个团队花三个月优化一个调度算法，最后发现客户只需要一个简单的贪心策略——因为他们的任务数量从来不超过10个。嗯，有时候过度设计比不设计更可怕。

好了，这一章的内容就到这里。NP完全问题让我们认识到计算的边界，而近似算法、随机化算法、在线算法则是工程师面对这些边界时的智慧结晶。记住：不是所有问题都需要最优解，有时候“足够好”就是最好的答案。

📚 课程目录