非确定算法：随机与近似

确定性算法Deterministic algorithms

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

非确定性算法Non-deterministic algorithms

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

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

随机算法

随机算法的优势

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

常见的随机算法

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

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

在半径为

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

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

随机化快速排序

• 每次在区间内随机选取一个值作为分界值
• 算法集合：每种选值策略都会对应一个新算法。
• 期望时间复杂度为O(n log n)
• 对谁的期望在于：数据与算法之间的博弈
• 对算法分布求期望（√）vs对数据分布求期望（×）
• 在算法分布上，对任一数据求期望（为什么O(n log n)）

两个疑问

• 洗牌算法如何实现
  • 在n！全排列中选li>
  • 现实洗牌
  • Fisher-Yates算法：
  • 错误的Fisher-Yates算法+1到n换；对1到n换
• 为什么洗牌后，每次指定位置元素等价于每次在随机位置选元素li>

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

• 注意共有n！个算法，每个算法比较次数可模拟算出

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

• 如何更有效地计算这个期望呢考二项分布的期望计算）
  • 利用期望的线性性质 对样本空间进行 重新划分

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

等概率取得的一个洗牌结果中，

• 考虑快速排序过程构造的划分树：即用一个二叉树，每个子树包含一个区间的所有数，根为用来划分当前区间的主元，左子树为小于主元的数，右子树为大于主元的数。
• 重要发现：每个节点与祖先比较过，两个子树间没有比较。

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

Insight：

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

随机算法

引例：最小割Min cut

在连通无向图

确定性算法

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

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

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

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

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

简单分析

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

失败案例

成功案例

算法分析

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

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

• 在第一次的基础上，第二次收缩为
• 于是在第i次收缩时
• 由条件概率公式可得n-2次都为选C中边的概率为
• 当重复足够多次后，找不到最小割的概率将会是无穷小

随机算法

两类随机算法

注意所有的随机性与数据无关

拉斯维加斯算法Las Vegas algorithms：随机化快速排序

• 算法永远输出正确的结果，但是算法的运行时间是随机的
• 主要用来防止针对性的最坏时间复杂度发生

蒙特卡罗算法Monte Carlo algorithms：最小割随机算法

• 算法会输出错误结果，但错误率有上界，运行时间也随机
• 主要用来使”难题“可解，并且快速求解
• 通常需要独立重复执行，但需注意如何整合多次执行的结果

两类随机算法之间的转化

拉斯维加斯算法?蒙塔卡罗算法

• 只需要让一个拉斯维加斯算法在指定时间内停止
• 得到的蒙特卡罗算法的错误率上界由马尔可夫不等式得到

蒙塔卡罗算法?拉斯维加斯算法

• 当存在一个快速验证解的方法时可转化（NP问题）
• 重复执行蒙塔卡罗算法知道找到正确解

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35127 人正在系统学习中