《算法设计与分析》课件 chp8随机算法

随机算法在算法设计中，随机算法是一类通过在执行过程中引入随机选择来提高效率或简化实现的算法。这种随机性可以帮助算法避免某些最坏情况，提高平均性能，甚至在许多问题上提供期望意义上的优良解法。随机算法允许在关键步骤中随机选择数据或操作,从而以一定的概率实现更高效的性能。随机算法的主要特点随机性算法的执行过程会依赖随机数的生成，因此即使在相同的输入下，不同的运行可能产生不同的结果。期望分析尽管随机算法的行为可能变化多样，其性能通常通过期望分析来得到理论保证。简单性与适应性随机性常常简化了算法设计，使其无需复杂的逻辑预处理，同时能很好地适应不同的输入特性。快速排序回顾让我们回顾一下快速排序，它的核心在于选择基准元素，并将数组分为两个子数组：一部分包含小于基准元素的值，另一部分包含大于基准元素的值。然而，在传统快速排序中，通常选择数组第一个元素或者最后一个元素作为基准元素，它通常会显著影响算法的效率。

随机化快速排序（RandQS）

核心思想：在数组中随机选择一个元素作为基准元素。

利用线性期望的性质可以得到：

在RandQS中，每次递归调用会选择一个分割元素y，然后将数组划分为左侧子数组（所有小于y的元素）和右侧子数组（所有大于y的元素）。

将概率代入期望公式，我们有：RandQS的独特性质需要注意的是，RandQS算法的运行时间依赖于算法在运行过程中做出的随机选择，而与输入数据的分布无关。即使对于相同的输入，算法在不同执行中可能表现不同，因为其行为受随机选择的影响。相关研究已证明，RandQS以非常高的概率，算法的运行时间不会超过其期望值太多，因此，几乎每次执行中，RandQS都能在一个高效的时间范围内完成，从而很好的解决了传统快速排序存在的性能退化问题。最小割问题设G为一个具有n个顶点的连通无向多重图。在多重图中，任意一对顶点之间可以存在多条边。图G中的一个割是指这样一组边：移除该组边后，图G被分割为两个或多个连通部分。最小割则是指具有最少边数的割。随机收缩算法步骤01随机挑选一条边从当前图中均匀随机地挑选任意一条边(u,v)。02收缩该边将边的两个端点u,v合并成一个新的"超级顶点"，记为uv。在合并过程中，若产生了自环，则将这些自环移除；若从超级顶点uv到某个顶点x原本存在多条平行边，则全部保留下来。03重复收缩随着每一次收缩，图中的顶点数减少1。重复该过程，直至图中仅剩下两个顶点。算法输出与多次运行输出割当图中只剩两个超级顶点时，这两个顶点之间所有边的集合即构成原图的一个割，将其作为本次随机收缩得到的"候选最小割"。多次运行由于算法具有随机性，一次执行不一定能保证找到最小割。通过多次独立随机运行，并取所有候选最小割中边数最少者，可以以较大概率获得最小割。成功概率分析下面我们分析随机收缩算法在最后输出最小割的成功概率。设C为最小割，且k为C中边的数量。随机化最小割算法的目标是找到一个大小恰为k的割。

·

·类似地，在第i次迭代时，图中剩余的边数至少为：未选中C中边的概率为：·注意，整个算法需要进行n-2次收缩。在每一次收缩中都不选中C中的任一边，才能保证最后保留割C。将各步未选中C中边的概率相乘，得到整个收缩过程中保持割C完好不被破坏的概率为：

可见，通过进一步增加运行次数，可以将失败概率降到任意小，但这会相应地增加算法的总运行时间。拉斯维加斯和蒙特卡罗算法随机化快速排序算法和随机最小割算法分别代表了两类不同的随机化算法。拉斯维加斯算法随机化快速排序算法总能返回正确的解，其唯一的不确定性体现在运行时间上，因此我们关注其运行时间分布，这类算法称为拉斯维加斯算法（LasVegasAlgorithm）。蒙特卡罗算法相比之下，随机最小割算法可能会产生错误解，但我们可以对错误解出现的概率进行有效约束，这类算法被称为蒙特卡罗算法（MonteCarloAlgorithm）。算法选择与应用场景在随机最小割算法中，如果每次运行均独立地进行随机选择，则通过多次重复运行能够显著降低失败概率，不过代价是运行时间的增加。在实际应用中，采用拉斯维加斯算法还是蒙特卡罗算法取决于具体需求——在某些场景下，错误解可能带来灾难性的后果。下面讨论如何将蒙特卡罗算法转换为拉斯维加斯算法的方法。蒙特卡罗到拉斯维加斯的转换

直观上，可以采用"重复调用+逐次验证"的方案：不断调用蒙特卡罗算法A，对每次结果进行验证，若验证通过则停止，否则继续下一次调用，直至获得正确解。

根据几何分布的性质，

马尔科夫链蒙特卡罗方法在许多概率与统计问题中，我们常常需要对某些复杂分布进行近似采样，或对多维积分进行数值估计。然而，当目标分布的形式十分复杂或维度较高时，直接从中采样往往十分困难。马尔科夫链蒙特卡罗（MarkovChainMonteCarlo，简称MCMC）方法提供了一种利用马尔科夫链在状态空间中进行随机游走的策略，使得经过足够多次迭代后，所得到的样本分布可以逼近目标分布，从而在数值计算、统计推断以及机器学习等领域得到广泛应用。马尔科夫链基本概念马尔科夫链是一类具有"无后效性"性质的随机过程，即其当前状态仅依赖于前一时刻的状态，而与更早时刻的状态无关。

随机游走与应用随机游走指在状态空间中按马尔科夫链进行的一连串"随机跳转"，可视为对目标分布进行探查的一种过程。比如当目标分布难以直接采样时，利用随机游走可在迭代充分后逼近该分布。此外，一些随机优化方法（如模拟退火）也基于马尔科夫链的思想，通过随机跳转来跳出局部极值，从而在更大范围内搜索全局最优解。吉布斯采样算法步骤初始化

条件采样依次（或随机）选择某个坐标i，从条件分布中采样并更新。重复迭代重复上一步，直到达到收敛或满足抽样数量要求。吉布斯采样（GibbsSampling）是MCMC家族中的一种具体算法，它的思想是在高维分布中，每次仅更新一个维度（或某个子集）的状态，其他维度保持不变，最终也能产生服从目标分布的样本。双变量正态分布采样案例

我们希望从该分布中采样出大量(X,Y)数据点，用于后续分析或模拟。为什么使用吉布斯采样

吉布斯采样步骤示意初始化

第1步

第2步

重复迭代执行若干轮，得到Markov链。

MCMC方法总结马尔科夫链蒙特卡罗方法通过在状态空间中进行随机游走，逐步逼近目标分布，是解决高维采样、复杂概率分布模拟和复杂积分问题的强有力手段。本节我们具体介绍了吉布斯采样算法用于高维采样，除此之外，还有Metropolis-Hastings采样算法。随机数生成随机数通常指那些在理论或实践中无法被预测、或者按照某种概率分布规律呈现的数值序列。它们在模拟、统计推断、密码学以及各种随机化算法中有着广泛的应用。在算法设计与分析中，随机数是随机化算法的基石：我们常假设能够在常数时间内从区间[0,1]内均匀地获得一个随机数。理想与现实在理论分析中，我们往往假设可以无限次地产生理想随机数，并且这些随机数具备独立同分布等理想性质。然而，在实际的计算机环境中，无论是通过软件算法生成的伪随机数（Pseudo-randomNumber），还是通过硬件噪声源获得的真随机数（TrueRandomNumber），都只能提供一定程度上的近似随机性。线性同余法目前，广泛使用的随机数生成器大多基于D.H.Lehmer于1949年提出的线性同余法（LCG,LinearCongruentialGenerator）。该方法的递推形式为：

线性同余法示例

7,6,9,0,7,6,9,0,…可以看出，该序列显示出周期为4的循环。对于模数m较大的实际应用来说，所生成的随机数序列的周期应尽可能长，以保证更好的随机性。模数m的选择周期长度考虑我们希望m相对较大，因为周期的长度最多只能有m个元素，如果m过小，序列可能会快速重复，随机性不足。如果m=2，生成的序列只能是0,1,0,1,0,1,…，随机性极差。计算效率考虑

最长周期的条件研究表明，对于由参数m、a、c和X_0定义的线性同余序列，其周期长度能够达到m的条件是：c和m的最大公约数为1，这确保了增量c不会与模数m有共同的因数，从而避免因c的选择导致序列周期过短。b=a−1必须能被所有整除m的质因数（能整除某个整数的质数）p整除。如果m是4的倍数，则b也是4的倍数。参数选择示例比如，选择m=16，选择增量c=5（5和16互斥），选择乘数a=13（m的质因素为2和3，a-1=12是2和3的倍数，12也是4的倍数）。上述参数的选择满足最长周期长度的要求。因此，线性同余序列定义为：

2,15,8,13,14,11,4,9,10,7,0,5,6,3,12,1,2,15,8,13,…生成指定区间的均匀分布

生成高斯分布随机数

生成任意分布的随机数下一个问题是如何生成任意分布的随机数。之前我们已经学会了如何生成指定区间内服从均匀分布的随机数，但在更一般的情形下，我们可能希望为不同的取值赋予不同的权重。

反向变换采样法

…

这种方法称为反向变换采样法，通过利用均匀随机数U所落区间的划分，将其映射到目标分布上，从而生成满足任意离散分布的随机变量X。反函数法对于通用的实值分布，我们可以用其分布函数F(x)来描述，即定义随机变量X不超过x的概率：该分布函数从0单调递增到1，也就是说：

通常，当F(x)是连续且严格递增的分布函数时，我们可以通过设置：

换句话说，通过将均匀分布的随机数通过目标分布的反分布函数进行变换，可以得到符合目标分布的随机数。指数分布随机数生成示例

设U=F(x),则:因此,反函数为:

方法的优缺点优点上述方法的优点在于容易理解和实现，适用于许多常见分布，如指数分布、伯努利分布等。局限性但对于一些复杂分布，累积分布函数的反函数难以求得或不存在解析表达式，限制了方法的应用。此时，可使用拒绝采样法、吉布斯采样等方法。随机化数据结构在讨论随机化数据结构之前,先回顾一下二叉搜索树(BinarySearchTree,BST)的特点及其局限性。二叉搜索树的性质与局限BST具有以下性质:对于任意节点x,其左子树中所有节点的键值均小于x的键值对于任意节点x,其右子树中所有节点的键值均大于x的键值

为了解决这一问题,随机化数据结构被提出,其中较为著名的包括Treap和SkipList。它们通过引入随机性,有效缓解了输入顺序对性能的不利影响,从而在最坏情况下也能保持较好的期望效率。Treap的基本概念考虑一个二叉树,其中每个节点v包含一对值(k(v),p(v)):其中k(v)是节点的键值,p(v)是为该节点随机分配的优先级。如果该树在键值上满足二叉搜索树(BST)的性质,并且在优先级上满足堆的性质(Treap要求父节点的优先级严格大于其子节点的优先级),则称这种结构为Treap。Treap的结构定义例如,给定以下节点集合:

Treap的结构唯一性证明可以证明,对于任意给定的键值对集合S以及确定的随机优先级(即优先级已固定、且全部不同),存在且仅存在一个TreapT,包含S中的键值对,并满足Treap的性质。证明过程如下:01确定根节点在集合S中,优先级最高的键k必须是根节点,否则树将不满足堆序性质。02划分子树为了满足Treap相对于节点键值的有序性质,集合S中所有小于k的键必须位于左子树,而所有大于k的键必须位于右子树。03递归构造通过归纳法,键k的左右子树也必须以相同的方式构造,确保其同时满足二叉搜索树和堆的性质。因此,给定S的键值对,Treap的结构是唯一的。Treap的优先级选择策略

Treap深度分析:祖先关系

情况一假设在i和j之间存在一个键k,且k的优先级高于i和j。此时,i在Treap中位于k的左侧,j在树中位于k的右侧,因此i不是j的祖先。情况二假设从i到j的所有键中,j拥有最高的优先级,那么j是i的祖先。情况三假设从i到j的所有键中,i拥有最高的优先级,那么i是j的祖先。Treap期望深度的计算由此可见,i是j的祖先的唯一方式是:i在从位置i到j的所有键中拥有最高的优先级。而每个键拥有最高优先级的概率是相等的,因此i是j的祖先的概率为:可得:

Treap的高概率界

SkipList的基本思想

从概念上讲,SkipList可以视为一种具有"多层索引"的链表。具体来说,首先构造一条基础的有序链表(第1层),其中存放所有元素并按关键字从小到大排列。为了加速搜索过程,在此基础上随机建立若干层"索引链表"。SkipList的结构特点SkipList的多层索引结构具有以下特点:部分节点索引每一层索引链表只包含部分节点,它们的顺序依然保持不变(即按关键字排序)。向下包含性若一个节点在某一层出现,则它在更底层一定也会出现(可以理解为"向上抽取"了一部分节点)。这种多层结构使得在较高层可以快速定位目标区域,然后逐层向下查找,从而实现高效的搜索与更新操作。SkipList示例结构

并共包括四层链表:SkipList的随机化分层规则SkipList的核心在于节点如何被"晋升"到更高层。其随机化分层规则如下:插入底层

抛硬币决定晋升通过抛硬币(或生成0/1随机数)的方式,决定该节点是否晋升到上一层索引链表;如果抛硬币结果为"正面",则将该节点加入上一层,否则停止晋升。重复晋升过程重复上述步骤,继续抛硬币决定是否进