随机算法与近似算法

概述

随机算法利用随机性来简化设计、提高效率或处理不确定性。近似算法放弃精确最优，在多项式时间内给出有质量保证的近似解。两者都是处理难问题的重要工具。

---

1. 随机算法分类

1.1 Las Vegas算法

• 结果总是正确的
• 运行时间是随机变量
• 期望运行时间有保证

例：随机化快速排序

1.2 Monte Carlo算法

• 运行时间确定（或有上界）
• 结果可能不正确，但错误概率有限

例：Miller-Rabin素性测试

graph TD
    RA[随机算法] --> LV[Las Vegas]
    RA --> MC[Monte Carlo]
    LV --> LV1[结果一定正确]
    LV --> LV2[时间随机]
    MC --> MC1[时间确定]
    MC --> MC2[结果可能错误]
    MC --> MC3[可通过重复降低错误概率]

---

2. 随机化快速排序

2.1 算法

随机选择pivot元素：

import random

def randomized_quicksort(arr, lo, hi):
    if lo < hi:
        # 随机选择pivot
        pivot_idx = random.randint(lo, hi)
        arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
        p = partition(arr, lo, hi)
        randomized_quicksort(arr, lo, p - 1)
        randomized_quicksort(arr, p + 1, hi)

2.2 期望时间分析

定理：随机化快速排序的期望比较次数为 \(O(n \log n)\)。

证明：设排序后元素为 \(z_1 < z_2 < \cdots < z_n\)，定义指示随机变量：

\[ X_{ij} = \begin{cases} 1 & \text{if } z_i \text{ 与 } z_j \text{ 被比较} \\ 0 & \text{otherwise} \end{cases} \]

总比较次数：

\[ X = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} X_{ij} \]

\(z_i\) 与 \(z_j\) 被比较当且仅当 \(\{z_i, z_{i+1}, \ldots, z_j\}\) 中第一个被选为pivot的是 \(z_i\) 或 \(z_j\)，概率为 \(\frac{2}{j - i + 1}\)。

\[ E[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1} = \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} \frac{2}{k} \leq 2n \sum_{k=2}^{n} \frac{1}{k} = O(n \log n) \]

---

3. Bloom过滤器

3.1 原理

Bloom过滤器是一种概率数据结构，支持高效的集合成员查询。

• 结构：长度为 \(m\) 的位数组 + \(k\) 个独立哈希函数
• 插入：将 \(k\) 个哈希位置设为1
• 查询：检查 \(k\) 个位置是否都为1

3.2 错误率

假阳性概率（在插入 \(n\) 个元素后）：

\[ p \approx \left(1 - e^{-kn/m}\right)^k \]

最优哈希函数个数：

\[ k^* = \frac{m}{n} \ln 2 \]

此时 \(p \approx (0.6185)^{m/n}\)。

class BloomFilter:
    def __init__(self, m, k, hash_funcs):
        self.bits = [False] * m
        self.m = m
        self.hash_funcs = hash_funcs[:k]

    def insert(self, item):
        for h in self.hash_funcs:
            self.bits[h(item) % self.m] = True

    def query(self, item):
        return all(self.bits[h(item) % self.m] for h in self.hash_funcs)

特点：

• 无假阴性（如果说不在，一定不在）
• 有假阳性（可能误报存在）
• 空间效率极高
• 不支持删除（可用Counting Bloom Filter）

---

4. 跳表（Skip List）

4.1 结构

跳表是一种随机化数据结构，每个节点以概率 \(p = 1/2\) 提升到上层。

Level 3:  1 -----------------> 9
Level 2:  1 -------> 5 ------> 9
Level 1:  1 --> 3 -> 5 -> 7 -> 9
Level 0:  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

4.2 性能

操作	期望时间	最坏时间
查找	\(O(\log n)\)	\(O(n)\)
插入	\(O(\log n)\)	\(O(n)\)
删除	\(O(\log n)\)	\(O(n)\)

期望层数：\(O(\log n)\)，期望空间：\(O(n)\)。

优势：实现简单，支持范围查询，无需复杂的平衡操作。Redis的有序集合就使用跳表实现。

---

5. 近似算法基础

5.1 近似比

对于最小化问题，算法 \(A\) 的近似比 \(\rho(n)\)：

\[ \frac{A(I)}{OPT(I)} \leq \rho(n) \quad \forall \text{实例 } I \]

对于最大化问题：

\[ \frac{OPT(I)}{A(I)} \leq \rho(n) \]

5.2 近似方案

类型	定义	运行时间
PTAS	对任意 \(\varepsilon > 0\)，\((1+\varepsilon)\)-近似	\(n^{f(1/\varepsilon)}\)
FPTAS	对任意 \(\varepsilon > 0\)，\((1+\varepsilon)\)-近似	\(\text{poly}(n, 1/\varepsilon)\)

FPTAS 是最强的近似保证——既是多项式时间，又可以任意接近最优。

---

6. 顶点覆盖的2-近似

6.1 问题

给定图 \(G = (V, E)\)，找最小顶点覆盖（每条边至少有一个端点被选中）。

6.2 贪心匹配算法

def vertex_cover_2approx(graph):
    """顶点覆盖2-近似算法"""
    cover = set()
    edges = set(graph.edges())

    while edges:
        # 任选一条边
        u, v = next(iter(edges))
        cover.add(u)
        cover.add(v)
        # 移除与u或v关联的所有边
        edges = {(a, b) for (a, b) in edges if a != u and a != v and b != u and b != v}

    return cover

6.3 近似比证明

设算法选择了 \(k\) 条边组成最大匹配 \(M\)。

• 算法输出 \(|C| = 2k\)
• 最优覆盖至少需要覆盖 \(M\) 的每条边，至少需要 \(k\) 个顶点
• 因此 \(|C| = 2k \leq 2 \cdot OPT\)

近似比 \(\rho = 2\)。\(\square\)

---

7. 集合覆盖的贪心近似

7.1 问题

全集 \(U\)，子集族 \(\{S_1, \ldots, S_m\}\)，选最少的子集覆盖 \(U\)。

7.2 贪心算法

def greedy_set_cover(universe, subsets):
    """集合覆盖贪心算法"""
    covered = set()
    chosen = []

    while covered != universe:
        # 选择覆盖最多未覆盖元素的子集
        best = max(subsets, key=lambda s: len(s - covered))
        chosen.append(best)
        covered |= best

    return chosen

7.3 近似比

定理：贪心算法的近似比为 \(H_n = \sum_{i=1}^{n} \frac{1}{i} = O(\ln n)\)，其中 \(n = |U|\)。

证明思路：用记账论证（charging argument）。每次贪心选择的"代价"\(1\)分摊到新覆盖的元素上，第 \(k\) 个被覆盖的元素最多被收取 \(\frac{1}{n-k+1}\) 的代价。

最优性

在 \(P \neq NP\) 假设下，集合覆盖不能在多项式时间内近似到优于 \((1-\varepsilon) \ln n\) 的比率（Dinur & Steurer 2014）。因此贪心算法的近似比本质上是最优的。

---

8. MAX-SAT的随机近似

8.1 问题

给定CNF公式，最大化被满足的子句数。

8.2 随机赋值算法

独立地以概率 \(1/2\) 设每个变量为TRUE/FALSE。

定理：设公式有 \(m\) 个子句，每个子句至少 \(k\) 个文字。随机赋值的期望满足子句数 \(\geq (1 - 2^{-k}) \cdot m\)。

证明：子句 \(C_j\) 有 \(k_j\) 个文字，\(C_j\) 不被满足的概率为 \(2^{-k_j}\)。

\[ E[\text{满足子句数}] = \sum_{j=1}^{m} (1 - 2^{-k_j}) \geq \sum_{j=1}^{m} (1 - 2^{-k}) = (1 - 2^{-k})m \]

对于3-SAT（\(k=3\)）：期望满足 \(\frac{7}{8}m\) 个子句，近似比为 \(\frac{7}{8}\)。

8.3 去随机化

条件期望法：逐个确定变量值，每步选择使条件期望不降的赋值。将随机算法转化为确定性算法，保持相同的近似比。

---

9. 背包问题的FPTAS

9.1 动态规划

标准DP：\(O(nW)\)，这是伪多项式时间（\(W\) 可能指数大）。

9.2 FPTAS思路

1. 将所有价值缩放：\(\hat{v}_i = \lfloor v_i \cdot \frac{n}{\varepsilon v_{\max}} \rfloor\)
2. 对缩放后的价值运行DP
3. 运行时间：\(O(n^3 / \varepsilon)\)
4. 近似比：\((1 - \varepsilon)\)

---

10. 总结比较

方法	适用场景	保证
随机化算法	需要简化或加速	期望时间/概率正确性
2-近似	顶点覆盖等	常数因子
\(O(\ln n)\)-近似	集合覆盖等	对数因子
PTAS/FPTAS	背包等	任意精度
随机取整	MAX-SAT等	常数因子

graph LR
    NPC[NP完全问题] --> A1[精确算法<br>指数时间]
    NPC --> A2[近似算法<br>多项式时间+质量保证]
    NPC --> A3[随机算法<br>概率保证]
    NPC --> A4[启发式算法<br>无理论保证]
    A2 --> FPTAS
    A2 --> PTAS
    A2 --> CONST[常数近似比]
    A2 --> LOG[对数近似比]

---

参考资料

• Motwani & Raghavan, Randomized Algorithms
• Vazirani, Approximation Algorithms
• Williamson & Shmoys, The Design of Approximation Algorithms

相关章节：

• 计算复杂性
• 贪心算法
• 算法基础

---

评论