南开大学软件学院2021年秋季学期研究生算法课程（复习）非确定算法：随机与近似

本文主要是介绍南开大学软件学院2021年秋季学期研究生算法课程（复习）非确定算法：随机与近似，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

非确定算法：随机与近似

确定性算法Deterministic algorithms

对于给定的输入，算法的输出和运行时间不变

非确定性算法Non-deterministic algorithms

对于给定的输入，算法的输出或运行时间是不确定的

启发式算法Heuristic algorithms
- 利用输入数据的特征和信息对问题进行求解
- 尽全力逼近最优解，但是无法得知和最优解的差距
近似算法Approximation algorithms
- 对问题给出一个近似最优解（数据无关）
- 可以给出对最优解或最优解的上下界的近似比（夹挤）
随机算法Randomized algorithms
- 随机数使算法本身成为随机变量，具有分布（数据无关）

随机算法

随机算法的优势

实现简单；
更加高效；
避开最坏情况（防hack）；

常见的随机算法

数论：Miller-Rabin素数测试，Pollard-Rho素因子分解
数据结构：随机平衡树，布隆过滤器，各种哈希
图论：最小割，平面图上的系列随机优化
代数与优化：多项式矩阵正确性测试，线性规划，整数规划

关于随机和概率的一个问题

在半径为 $r$ 的圆上取一弦，弦长大于 $\sqrt{3}r$ 的概率是多少？

引例：快速排序（确定性算法）

代码：每次在当前子数组中的确定位置选值做划分
算法的最快运行时间按为O(n log n)
但永远可以构造一个（或多个）对抗样例使算法时间复杂度到O(n^2)，只要使得每次选取的值都是当前区间的最值
即对于数据“明牌”了

随机化快速排序

每次在区间内随机选取一个值作为分界值
算法集合：每种选值策略都会对应一个新算法。
- 共多少个？ $n!$ 个，等价于洗牌shuffle后选指定位置（考虑划分树）
期望时间复杂度为O(n log n)
对谁的期望？关键在于：数据与算法之间的博弈
对算法分布求期望（√）vs对数据分布求期望（×）
在算法分布上，对任一数据求期望（为什么O(n log n)）

两个疑问

洗牌算法如何实现？
- 在n！全排列中选？
- 现实洗牌
- Fisher-Yates算法：
  - 对 $i=1,\cdot \cdot \cdot ,n$ ，从i到n中任选一个数与 $a_i$ 交换
- 错误的Fisher-Yates算法？对i+1到n换；对1到n换
为什么洗牌后，每次指定位置元素等价于每次在随机位置选元素？

随机化快速排序时间复杂度分析

直接计算？对算法集合
- $\mathbb{E}(T(A))=\sum_{k=1}^{n!}T(A_k)P(A_k)=\frac{1}{n!}\sum_{k=1}^{n!}T(A_k)$
- 其中， $T(A_k)$ 表示算法 $A_k$ 中两个数发生比较的次数
注意共有n！个算法，每个算法比较次数可模拟算出
如n=10的分布：
若n更大，如何估计？采样！

随机化快速排序时间复杂度分析

如何更有效地计算这个期望呢？（思考二项分布的期望计算）
- 利用期望的线性性质对样本空间进行重新划分
- $\mathbb{E}(\sum X)=\sum \mathbb{E}(X)$
令为数组中第大元素，定义如下指示器随机变量
- $X_{ij}=\left\{\begin{matrix} 1,\ S_i\ and\ S_j\ are\ compared\\ 0,\ S_i\ and\ S_j\ not\ compared \end{matrix}\right.$
于是，随机变量（即算法的比较次数）满足
- $T(A)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij}$
因此，根据期望的线性性质有
- $\mathbb{E}(T(A))=\mathbb{E}(\sum_{i=1}^{n-1}\sum_{j=i+1}^nX_{ij})=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\mathbb{E}(X_{ij})=\sum_{i=1}^{n-1}\sum_{j=i+1}^nX_{ij}P(X_{ij})=\sum_{i=1}^{n-1}\sum_{j=i+1}^nP(X_{ij}=1)$
是多少？思考物理意义！（回顾弦问题）
- 事件随机性来自于？
  - 等概率选取一个确定性算法，即等概率选取一个洗牌结果
- 事件什么时候发生？
  - 在随机取得的洗牌结果中， $S_i$ 和 $S_j$ 发生过比较

随机化快速排序时间复杂度分析

等概率取得的一个洗牌结果中， $S_i$ 和 $S_j$ 发生过比较的概率是？

考虑快速排序过程构造的划分树：即用一个二叉树，每个子树包含一个区间的所有数，根为用来划分当前区间的主元，左子树为小于主元的数，右子树为大于主元的数。
重要发现：每个节点与祖先比较过，两个子树间没有比较。
此时，考虑 $S_i,S_{i+1},\cdot \cdot \cdot ,S_j$ 的作为主元的出现顺序，如果 $S_k,i<k<j$ 更早地作为主元， $S_i$ 和 $S_j$ 必在两棵子树中，只有当 $S_i$ 或 $S_j$ 率先作为主元时，其发生比较。
随机选点时，等概率地被第一个选值，所以
- $P(X_{ij}=1)=\frac{2}{j-i+1}$

随机化快速排序时间复杂度分析

$\mathbb{E}(T(A))=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\mathbb{E}(X_{ij})=\sum_{i=1}^{n-1}\sum_{j=i+1}^nP(X_{ij}=1)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1}=\sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{2}{k+1}<\sum_{i=1}^{n-1}\sum_{k=1}^n\frac{2}{k}=\sum_{i=1}^{n-1}O(\ln n)=O(n\ln n)$

Insight：

对样本空间进行巧妙划分后，利用期望的线性性质可以解很多问题。由此，可以体会到用指示器随机变量的根本原因为：

$\mathbb{E}(X)=1\times P(X=1)+0\times P(X=0)=P(X=1)$

随机算法

引例：最小割Min cut

在连通无向图 $G=(V,E)$ 上，至少删几条边可使原图不连通？

确定性算法

根据最大流最小割定理，可以用最大流算法求得有向图上，分割源点和汇点间的最小割，常见算法约为O(n^4)-O(n^5)
那么无向图、且无源点汇点的全局最小割呢？
- 固定源点，枚举汇点，重复n次最大流找全局最小割

关于问题的思考（最优&可行）

能否给出最小割的上界？可行解里较优的？（最小度数点）

最小割的随机算法（Karger's Algorithm）

收缩操作Contraction：以均匀分布随机选择图的一条边，将边上两个点缩为一个点，并将两点间的所有边删除
重复步骤1，知道图只剩下两个点（注意此时的图不再是简单图）
最终，两点间的个数即为最小割

简单分析

该贪心策略既为保证可行，也未保证最优：答案可能不是正确的！
但是该算法的效率很高，时间复杂度为O(n)（n为图中点的个数）

失败案例

成功案例

算法分析

有多大概率，该算法可以给出一个正确的最小割呢？

假设图中有n个点，最小割为k。此时即使最小割有多解，我们只关注其中一种，并用边集C表示（即C包含k条边）。于是，问题转为求在n-2次收缩操作中，均为选中C中边的概率。

首先，显然图中至少有 $\frac{kn}{2}$ 条边
令事件为第i次收缩时，没有选C中边，那么对第一次
- $P(\varepsilon _1)\geq 1-\frac{k}{kn/2}=1-\frac{2}{n}$
在第一次的基础上，第二次收缩为
- $P(\varepsilon_2|\varepsilon_1)\geq 1-\frac{k}{k(n-1)/2}=1-\frac{2}{n-1}$
于是在第i次收缩时
- $P(\varepsilon_i|\bigcap_{j=1}^{i-1}\varepsilon_j)\geq 1-\frac{2}{n-i+1}$
由条件概率公式可得n-2次都为选C中边的概率为
- $P(\bigcap_{i=1}^{n-2}\varepsilon_i)\geq \prod_{i=1}^{n-2}\frac{n-i-1}{n-i+1}=\frac{2}{n(n-1)}\geq \frac{2}{n^2}$
从未选中C中边的概率大于 $\frac{2}{n^2}$ ，即算法成功率大于 $\frac{2}{n^2}$
此时如果拖过重复执行 $\frac{n^2}{2}$ 次算法，全部失败的概率为
- $P(fail)\leq (1-\frac{2}{n^2})^{\frac{n^2}{2}}<\frac{1}{e}$
换言之，在O(n^3)时间内，以超过 $1-\frac{1}{e}$ 的概率找到最小割
当重复足够多次后，找不到最小割的概率将会是无穷小