随机算法

1 Las Vegas 型随机算法¶

1.1 特点¶

• 通过修改确定性算法得到，一般将算法的某步的确定型选择变成随机选择
• 一次运行可能得不到解；若得到解，则解 一定是正确的
• 改进途径：与确定型算法相结合
• 有可能改进确定型算法平均情况下的时间复杂度

有效的 Las Vegas 算法：期望运行时间是输入规模的多项式且总能给出正确答案的随机算法。

1.2 随机快速排序¶

算法：随机快速排序¶

输入：包含 \(n\) 个元素的数组

输出：经过排序的 \(n\) 个元素的数组

1.3 随机选择算法¶

算法：RandSelect¶

从 \(A[p..r]\) 中选第 \(k\) 小。

时间期望值估计：

假设 \(1..n\) 中每个数被选的概率相等，并且保守地假设第 \(k\) 小元素总是出现在划分后两个数组中较大的数组，则：

设划分一次的线性时间不超过 \(tn\)。归纳证明 \(T(n) \leq cn\)：假设对所有 \(k<n\) 成立，则

取 \(c \geq 4t\) 即可。因此随机选择算法的期望运行时间为 \(O(n)\)。

1.4 随机 n 后放置¶

算法：BoolQueen¶

1.4.1 与回溯相结合的改进算法¶

设 \(\text{stopVegas} \leq n\)，表示用 BoolQueen 算法放置的皇后数。剩下 \(n - \text{stopVegas}\) 个皇后用回溯方法放置。

• \(\text{stopVegas} = 0\) 时是完全的回溯算法
• \(\text{stopVegas} = n\) 时是完全的 Las Vegas 算法

算法：QueenLV¶

成功搜索与不成功搜索：

对于不同的 \(\text{stopVegas}\) 值，设：

• \(p\) 为算法成功概率
• \(s\) 为一次成功搜索访问的结点数的平均值
• \(e\) 为一次不成功搜索访问的结点数的平均值
• \(t\) 为算法找到一个解的平均时间

\(n = 12\) 时的统计数据：

2 Monte Carlo 型随机算法¶

2.1 特点¶

• 这种算法有时会给出 错误的答案
• 其运行时间和出错概率都是随机变量，通常需要分析算法的出错概率
• 多项式时间内运行且出错概率不超过 ⅓ 的随机算法称为有效的 Monte Carlo 型算法

2.2 主元素测试¶

主元素：出现次数超过一半以上的元素。

算法：Majority¶

输入：\(n\) 个元素的数组 \(T\)

输出：如果存在主元素则输出 "true"，否则 "false"

算法：BoolMajority¶

算法的正确性：

• 若回答 true：则 \(T\) 存在主元素，算法正确
• 若回答 false：\(T\) 仍可能存在主元素，算法可能出错
• 回答正确概率大于 ½

BoolMajority 算法正确的概率：

对于任意给定的 \(\varepsilon > 0\)，如果要使出错的概率不超过 \(\varepsilon\)，则调用次数 \(k\) 满足：

算法：MCMajority¶

输入：\(T, n, \varepsilon\)

2.3 串相等测试¶

问题：\(A\) 有一个长串 \(x\)，\(B\) 有长串 \(y\)，\(A\) 和 \(B\) 希望知道 \(x = y\)？

方法一：\(A\) 将 \(x\) 发送给 \(B\)，\(B\) 测试 \(x = y\)。发送消耗大（长串占用信道资源）。

方法二（指纹技术）：

1. \(A\) 用 \(x\) 导出一个短串 \(f(x)\)（fingerprints）
2. \(A\) 将 \(f(x)\) 发送到 \(B\)
3. \(B\) 使用同样方法导出相对于 \(y\) 的短串 \(f(y)\)
4. \(B\) 比较 \(f(x)\) 与 \(f(y)\)
5. 如果 \(f(x) \neq f(y)\)，则 \(x \neq y\)；如果 \(f(x) = f(y)\)，则还不能确定

2.3.1 指纹产生¶

设 \(x\) 和 \(y\) 的二进制表示对应正整数 \(I(x), I(y)\)。选择素数 \(p\)，定义指纹函数：

\(A\) 传送 \(p\) 和 \(I_p(x)\) 给 \(B\)。当 \(p\) 不太大时，传送的是短串。

指纹满足：

但反过来不一定成立：

当 \(x\neq y\) 时，一次测试出错的条件是：

2.3.2 随机测试与出错概率¶

若 \(x,y\) 的二进制表示位数为 \(n\)，则 \(x,y \leq 2^n\)。如果选择 \(M \geq 2n^2\)，一次测试的出错概率不超过：

重复执行 \(j\) 次，每次随机选择小于 \(M\) 的素数：

令 \(j=\lceil \log \log n\rceil\)，则出错概率至多约为：

例如 \(x,y\) 是 \(1{,}000{,}000\) 位二进制数，取 \(M=2\times 10^{12}\)，素数 \(p\) 和指纹 \(I_p(x)\) 都至多需要 41 位，因此总共传送约 82 位。

2.4 模式匹配¶

问题：给定串 \(X\)（\(|X| = n\)）和模式 \(Y\)（\(|Y| = m\)，\(m \leq n\)），求 \(Y\) 在 \(X\) 中的首次出现位置。

算法一：朴素算法，\(X\) 的首元素对齐，依次从前到后比较 \(X\) 与 \(Y\) 的元素。运行时间 \(O(mn)\)。

算法二：KMP 算法（Knuth, Morris, Pratt），运行时间 \(O(m + n)\)。

算法三（随机算法）：

设计思想：设 \(X(j) = x_j x_{j+1} \ldots x_{j+m-1}\)，把 \(X(j)\)（\(j = 1, 2, \ldots, n-m+1\)）与 \(Y\) 逐个字符的比较，改成对指纹 \(I_p(X(j))\) 与 \(I_p(Y)\) 的比较。

\(X(j)\) 与 \(X(j+1)\) 的关系：

其中 \(W_p = 2^m \pmod p\)。

算法：PatternMatching¶

输入：串 \(X\) 和 \(Y\)，\(|X| = n\)，\(|Y| = m\)，\(m \leq n\)

输出：如果 \(Y\) 在 \(X\) 中，\(Y\) 出现的第一位置；否则为 "0"

时间复杂度：\(O(m + n)\)

• \(W_p\)、\(I_p(Y)\)、\(I_p(X(1))\) 计算 \(O(m)\) 时间
• 从 \(I_p(X(j))\) 计算 \(I_p(X(j+1))\) 总共需要 \(O(n)\) 时间

出错条件：\(Y \neq X(j)\)，但 \(I_p(Y) = I_p(X(j))\)。等价地：

出错概率：上述乘积大小不超过 \((2^m)^n = 2^{mn}\)，整除它的素数个数不超过 \(\pi(mn)\)。选 \(M = 2mn^2\)，则出错概率不超过：

3 素数测试¶

3.1 求幂运算¶

算法：Exp¶

求 \(x\) 的 \(m\) 次幂，\(m = d_k d_{k-1} \ldots d_1 d_0\) 为二进制自然数。

算法：ExpMod¶

求 \(a\) 模 \(n\) 的 \(m\) 次幂，\(m = b_k b_{k-1} \ldots b_1 b_0\) 为二进制自然数。

时间复杂度：\(T(n) = O(k \log^2 n) = O(\log^3 n)\)（以位乘作为基本运算）。

3.2 Fermat 小定理¶

素数测试原理：检测 \(2^{n-1} \equiv 1 \pmod n\)。如是，输出 "素数"；否则输出 "合数"。

算法：Ptest1¶

输入：奇整数 \(n\)，\(n > 5\)

输出："prime" 或者 "composite"

3.3 改进算法¶

算法：Ptest2¶

输入：奇整数 \(n\)，\(n > 5\)

由初等数论可以证明：如果 \(n\) 为合数，但不是 Carmichael 数，算法 Ptest2 测试 \(n\) 为合数的概率至少为 ½。

3.4 素数的另一个必要条件¶

称 \(x \neq \pm 1\) 的根为 非平凡的。如果方程有非平凡的根，则 \(n\) 为合数。

3.5 Miller-Rabin 算法¶

设 \(n\) 为奇素数，存在 \(q, m\) 使得 \(n - 1 = 2^q m\)（\(q \geq 1\)）。

构造序列：\(a^m \pmod n, a^{2m} \pmod n, \ldots, a^{2^q m} \pmod n\)，其最后一项为 \(a^{n-1} \pmod n\)，而且每一项是前面一项的平方。

测试方法：

1. 对于任意 \(i\)（\(i = 0, 1, \ldots, q-1\)），判断 \(a^{2^i m} \pmod n\) 是否为 1 和 \(n-1\)，且它的后一项是否为 1
2. 如果其后项为 1，但本项不等于 1 和 \(n-1\)，则它就是非平凡的根，从而知道 \(n\) 不是素数
3. 随机选择 \(a \in \{2, 3, \ldots, n-1\}\)，进行上述测试

算法：findq-m¶

找 \(q, m\) 使得 \(n - 1 = 2^q m\)。

运行时间：\(O(\log n)\)。

算法：test¶

检测序列是否存在非平凡的根。

性能分析：

• 1 次测试运行时间 \(O(\log^3 n)\)
• 可证明 1 次测试出错的概率至多 ½
• 重复运行 \(k\) 次，可将出错概率降到至多 \(2^{-k}\)

算法：PrimalityTest（Miller-Rabin）¶

输入：奇整数 \(n \geq 5\)

时间：\(T(n) = O(\log^4 n)\)（按位乘统计）。

令 \(k = \lceil \log n \rceil\)，出错的概率小于等于 \(2^{-k} \leq 1/n\)。因此如果 \(n\) 为素数，则算法输出 "prime"；如果 \(n\) 为合数，则算法以至少 \(1-1/n\) 的概率输出 "composite"。

4 随机算法的分类与局限性¶

4.1 Las Vegas 型 vs Monte Carlo 型¶

Monte Carlo 型随机算法的错误类型：

常见随机复杂性类：

4.2 处理难解问题的策略¶

4.2.1 对问题施加限制¶

有些 NP 完全问题在限制输入结构后会变成多项式时间可解问题。

4.2.2 固定参数算法¶

固定参数算法：输入中带有一个参数 \(k\)，当输入规模为 \(n\) 时运行时间为 \(O(f(k) \cdot n^c)\) 的算法。

4.2.3 改进的指数时间算法¶

\(O^*\) 表示忽略了多项式因子，如 \(O^*(2^n) = O(n^{O(1)} 2^n)\)。

• 蛮力算法为 \(O^*(2^n)\) 时，对任何 \(1 < c < 2\)，\(O^*(c^n)\) 称为 非平凡的指数时间算法
• 可证明在 \(O^*(1.8393^n)\) 时间内正确求解 3-SAT
• 指数时间假设：对每个正整数 \(k\)，都存在常数 \(c_k > 0\)，使得求解 \(k\)-SAT 的精确算法时间复杂性不低于 \(\Omega^*(2^{c_k n})\)

4.2.4 其他策略¶

5 总结¶