程序设计实习

发表于 分类于 Waline：

随机化算法

基本分析

Union Bound

即:\(Pr [ \bigcup_i X_i ] \leq \sum Pr [ X_i ]\),取等当且仅当所有\(X_i\)互斥.

Markov 不等式

若\(X \geq 0\),则\(Pr [ X \geq t \mathbb{ E } [ X ] ] \leq \frac{ 1 }{ t }\).

Example(Max-Cut算法)

一个无向无权图,将点集划分成两个部分,使得跨越这两部分的边尽可能多.

直接随机划分,容易见到每条边有\(\frac{ 1 }{ 2 }\)的概率是割边,因此期望自然是\(\frac{ 1 }{ 2 } | E | \geq \frac{ 1 }{ 2 } | \text{ max - cut } |\).

由此立即见到,\(Pr [ | ans | \leq ( \frac{ 1 }{ 2 } - \epsilon ) | E | ] = Pr [ | E | - | ans | \geq ( \frac{ 1 }{ 2 } + \epsilon ) | E | ] \leq \frac{ 1 }{ 1 + 2 \epsilon }\).

由于每次独立操作,因此如果有\(P\)的概率失败,那么运行\(T\)次后至少成功一次的概率应当为\(1 - P^T\).从而\(T = O ( \log_P{ \delta } ) = O ( \cfrac{ \ln \frac{ 1 }{ \delta } }{ \ln ( 1 +{ 2 \epsilon } ) } ) \approx O ( \cfrac{ \ln \frac{ 1 }{ \delta } }{ \epsilon } )\)即可拿到\(\delta\)失败概率.

Chernoff Bound

设\(X_1 , \cdots , X_n \in [ 0 , 1 ]\)是独立,同期望(期望为\(\mu \geq t\))的随机变量,令\(X = \frac{ \sum_k X_k }{ n }\),对于任何失败概率\(\delta \in ( 0 , 1 )\),应当有:

\[ Pr \left [ | X - \mu | \geq \sqrt{ \cfrac{ \log ( 1 / \delta ) }{ nt } } \mu \right ] \leq \delta \]

Example(Median Trick)

现在有一个黑盒能够以\(p > \frac{ 1 }{ 2 }\)的概率正确回答Yes或者No,问重复\(T\)选多少次能拿到\(1 - \delta\)的成功概率.

考虑重复\(T\)次后应当有期望\(pT\)个正确答案,因此直接取中位数.称此算法为Median Trick.

Chernoff Bound 告诉我们\(T = O ( \log \frac{ 1 }{ \delta } )\)足够.

Hoeffding 不等式

设独立随机变量\(x_1 , \cdots , x_m \in [ s , t ]\),令\(X = \sum_i x_i\),则:

\[ Pr [ X - E [ X ] \geq z ] \leq 2 \exp \left ( - \cfrac{ 2 z^2 }{ m ( t - s )^2 } \right ) \]

编程中的随机性

一般采用伪随机,也即是给定初值\(X_0\),通过某个确定性的函数来生成\(X_{ n + 1 } = f ( X_n )\)这样的.

数值概率算法

即通过随机选取元素从而求得在数值上的近似解.较之于传统算法,其运行速度更快,而且随着运行时间的增加,近似解的精度也会提高.在不可能或不必要求出问题的精确解时,可以使用其得到相当满意的近似解,如随机撒点法(近似求难以计算的图形面积).

Monte Carlo算法

总是能在确定的运行时间内出解,但是得到的解有一定概率是错的.通常出错的概率比较小,因此可以通过反复运行算法来得到可以接受的正确率.

求解最优化问题的Monte Carlo算法

事实上,大部分最优化问题都可以转化为判定性问题:也就是判定一个解是否是最优解,因此我们接下来基本都是讨论的求解判定性问题的Monte Carlo算法.

求解判定性问题的Monte Carlo算法

  1. 假倾向的Monte Carlo算法:当这类算法的返回值为假的时候,结果一定正确,但返回值为真的时候则有一定概率错误.

  2. 真倾向的Monte Carlo算法:当这类算法的返回值为真的时候,结果一定正确,但返回值为假的时候则有一定概率错误.

  3. 产生双侧错误的Monte Carlo算法:无论返回值为什么都有概率出错.基本不会使用.

以下讨论的Monte Carlo算法均为产生单侧错误的Monte Carlo算法.

正确率与复杂度

显然,如果我们有一个单词正确率为\(p\),时间复杂度为\(O ( f ( n ) )\)的算法,我们运行其\(k\)次,则正确率为\(1 - ( 1 - p )^k\),时间复杂度为\(O ( kf ( n ) )\).

算法设计思路1

我们来总结一下通常的Monte Carlo算法的设计思路:

设计一个能解决问题的确定性算法

  1. 这个算法需要枚举一些元素.

  2. 设这个算法的复杂度为\(O ( f ( n ) g ( n ) )\),其中\(f ( n )\)为枚举部分的复杂度,\(g ( n )\)为单词枚举中计算所需的复杂度.大部分情况下应保证\(g ( n )\)不会很大.

向算法引入随机化优化复杂度

  1. 随机化寻找元素来降低复杂度.

  2. 计算随机化情况下的正确率以及复杂度.

算法设计思路2
设计一个能解决问题的确定性算法

  1. 这个算法需要用到一个或多个传入的元素.

  2. 这个元素的值不应该依赖于输入数据.

  3. 我们可以通过check这个元素来得到与答案有关的信息.

向算法引入随机化优化复杂度

  1. 随机这个元素.

  2. 计算随机化情况下的正确率以及复杂度

Example
Example 1(Millar-Rabin算法)

略

Example2(CodeChef MSTONE)

平面上有\(n\)个互不重合的点,已知存在不超过\(7\)条直线可以覆盖全部的点,问在平面上作一条直线,最多能覆盖多少个点.\(n \leq 10000\).

考虑一个朴素的暴力:枚举两个点,确定一条直线,然后判断多少个点在这条直线上.但是这样复杂度是\(O ( n^3 )\)的.

考虑加入随机化.我们不妨每次随机两个点,注意到存在七条直线覆盖全部的点,那覆盖点最多的直线覆盖的点数一定不少于\(\lceil \frac{ n }{ 7 } \rceil\)个点.换句话说,我们随机一个点,这个点在这条直线上的概率是\(\frac{ 1 }{ 7 }\),因此随机两个点确定这条直线的概率为\(\frac{ 1 }{ 49 }\).随机\(1000\)次,错误概率为\(1 - ( \frac{ 48 }{ 49 } )^{ 1000 }\),是很小的.

Example3(CF364D Ghd)

给定一个长度为\(n\)的序列,要求找出一个长度大于等于\(\frac{ n }{ 2 }\)的子序列,使这个子序列中所有数的\(\gcd\)最大,求最大的\(\gcd\).\(n \leq 10^6\),\(a_i \leq 10^{ 12 }\).

注意到我们随机一个数,这个数在最终答案中的概率是\(\frac{ 1 }{ 2 }\).我们不妨直接随机这个数,然后枚举它的因子,判断每个因子在序列中的出现次数即可.但是这样单次复杂度\(O ( n \sqrt{ a } )\),好像不太能过.

冷静一下,我们不妨将这\(\sqrt{ a }\)个质因子全都存下来,然后将\(n\)个数也全都存下来,做狄利克雷后缀和即可.不过直接做可能还需要离散化/map,我们考虑先把所有数与我们随机到的那个数取一个\(\gcd\),这样所有数就都是这个数的因子,可以使用大小因子分别编号来实现.

Example4([POI2014]Couriers)

给定长度为\(n\)的序列\(a\),有\(m\)次询问,每次给定一个区间\([ l , r ]\),问\(a [ l , r ]\)中是否存在出现次数严格大于其它所有数出现次数之和的数,如果存在请输出.\(( n , m \leq 500000 , 1 \leq a_i \leq n )\).

先存下来每个位置的数是第几次出现,我们就可以利用二分快速找到一个区间内某个数出现次数.接下来只需要随机化找这个区间内某个数并判断是否满足条件即可.

Example5([NOI2013] 向量内积)

先考虑\(k = 2\)的情况:

首先,我们自然可以枚举一个向量\(A\)并判断它与其它向量的内积,这样复杂度为\(O ( n^2 d )\).

冷静一下,这个过程其实就是一个矩阵乘法的过程:我们设\(A = \begin{bmatrix}\vec{ a_1 } , \vec{ a_2 } , . . . , \vec{ a_n }\end{bmatrix}\),那我们要验证的无非是\(B = AA^T\)中是否存在一个不在主对角线上的元素\(B_{ i , j }\)在\(\mod 2\)意义下为\(0\).

这咋做啊?我们冷静一下,构造一个矩阵\(C\),其中\(C\)的主对角线元素与\(B\)相同,而其他元素全是\(1\).接下来我们要做的无非是找到\(B\)和\(C\)不同的地方.

这咋办呢?我们考虑这么一点:如果\(B = C\),那么对于任意一个\(X_{ m \times n }\)都应该满足\(XB = XC\),取\(m = 1\),我们的问题就转化为:是否能找到一个\(X\),使得\(XB \ne XC\)?这显然可以随机化.计算前者的复杂度为\(O ( nd )\),后者由于\(C\)很特殊,可以在\(O ( n )\)的时间内求出.这样我们就保证了算法复杂度上的合理性.

接下来,我们要证明其正确率上的合理性.这个算法显然是单侧错误的Monte Carlo算法.问题在于正确率:

令\(D = B - C\),若返回相等但实际上不相等,则\(D\)中至少存在一个不为\(0\)的数字,假设\(D_{ i , j } \ne 0\).我们令\(E = X \times D\),那么只有当\(E\)是零向量时才会错误.而\(E_j = \sum_{ k } X_k D_{ k , j }\),不难解得:\(E_i = - \frac{ 1 }{ D_{ i , j } } \sum_{ k \ne i } X_k D_{ k , j }\),也就是说如果\(X\)的其它位置都确定了,那么\(E\)只有一种取值会返回错误.由于\(k\)一共就俩取值,所以正确率至少\(\frac{ 1 }{ 2 }\).

至于找到答案:我们找到一个不为\(0\)的\(E_i\),那么一定存在一组解包含了第\(i\)个向量,只需枚举另一个向量检验就行,复杂度\(O ( nd )\).

\(k = 3\)的话,我们注意到\(\mod 3\)意义下,\(1\)和\(2\)的平方都是\(1\).考虑\(\sum_{ j } B_{ i , j }^2 X_j = \sum_{ j } B_{ i , j } X_j B_{ h , i }^T\),大概做做.

Las Vegas算法(Sherwood算法)

总是能返回正确的结果,但是其运行时间不确定.对于一些平均时间复杂度优秀,但是最坏情况下复杂度较高的确定性算法,通过引入随机函数,尝试减小最坏情况的可能性,以在期望意义下达到优秀的时间复杂度.

算法设计思路
设计一个能解决问题的确定性算法

  1. 这个算法需要枚举全排列.

  2. 通常,问题问的是要么只是可行解而不是最优解,要么最优方案特别多,总之要保证有用的排列个数不会太少

向算法引入随机化优化复杂度

  1. 随机化寻找排列来降低复杂度.

  2. 通常证明复杂度和正确率巨大麻烦,这里建议直接实践证明.

Example
快速排序算法

我们试图计算它的期望时间复杂度:

不妨设\(T ( n )\)表示对长度为\(n\)的序列运行快速排序算法所需的期望时间,我们有:

\[ \begin{aligned} T ( 0 ) & = 0 \\ T ( n ) & = n + \frac{ 1 }{ n } \sum_{ i = 0 }^{ n - 1 } ( T_i + T_{ n - i - 1 } ) \end{aligned} \]

做放缩(可能有些地方需要\(+ 1\)或者\(- 1\)或者加取整,但是问题不大,反正是期望):

\[ \begin{aligned} T ( n ) & = n + \frac{ 1 }{ n } \sum_{ i = 0 }^{ n - 1 } ( T_i + T_{ n - i - 1 } ) \\ & = n + \frac{ 2 }{ n } \sum_{ i = \frac{ n }{ 2 } }^{ n - 1 } ( T_i + T_{ n - i - 1 } ) \\ & = n + \frac{ 2 }{ n } \sum_{ i = \frac{ n }{ 2 } }^{ \frac{ 3 n }{ 4 } } ( T ( i ) + T ( n - i - 1 ) ) + \frac{ 2 }{ n } \sum_{ i = \frac{ 3 n }{ 4 } }^{ n } ( T ( i ) + T ( n - i - 1 ) ) \end{aligned} \]

由于\(T ( n ) \geq n\),所以对于\(\frac{ n }{ 2 } \leq i \leq j\),我们显然有:\(T ( i ) + T ( n - i ) \leq T ( j ) + T ( n - j )\).

因此:

\[ \begin{aligned} T ( n ) & \leq n + \frac{ 2 }{ n } \sum_{ i = \frac{ n }{ 2 } }^{ \frac{ 3 n }{ 4 } } ( T ( \frac{ 3 n }{ 4 } ) + T ( \frac{ n }{ 4 } ) ) + \frac{ 2 }{ n } \sum_{ i = \frac{ 3 n }{ 4 } }^{ n } ( T ( n - 1 ) + T ( 0 ) ) \\ & \leq n + \frac{ 1 }{ 2 } ( T ( \frac{ 3 n }{ 4 } ) + T ( \frac{ n }{ 4 } ) + T ( n - 1 ) ) \end{aligned} \]

我们要证明\(\exists c\),\(T ( n ) \leq cn \log n\),考虑使用数学归纳法,则:

\[ \begin{aligned} T ( n ) & \leq n + \frac{ 1 }{ 2 } ( \frac{ 3 cn }{ 4 } \log ( \frac{ 3 n }{ 4 } ) + \frac{ cn }{ 4 } \log ( \frac{ n }{ 4 } ) + c ( n - 1 ) \log ( n - 1 ) ) \\ & \leq n + c ( \frac{ 3 n }{ 8 } \log n - \frac{ 3 n }{ 8 } \log \frac{ 4 }{ 3 } + \frac{ n }{ 8 } \log n - \frac{ n }{ 4 } + \frac{ n }{ 2 } \log n ) \\ & = cn \log n + n ( 1 - \frac{ 3 c }{ 8 } \log ( \frac{ 4 }{ 3 } ) - \frac{ c }{ 4 } ) \end{aligned} \]

于是显然存在,假设成立.

一类由Monte Carlo算法改造而成的算法

对于一类一定有解的构造性问题,假设我们有一个正确率为\(p\),时间复杂度为\(O ( f ( n ) )\)的产生单侧错误的Monte Carlo算法,我们时图将其改造为Las Vegas算法,我们现在想知道它的期望复杂度.

设其期望运行\(k\)次,则:

\[ \begin{aligned} k & = \sum_{ i = 1 }^{ \infty } p ( 1 - p )^{ i - 1 } i \\ ( 1 - p ) k & = \sum_{ i = 1 }^{ \infty } p ( 1 - p )^i i \\ pk & = \sum_{ i = 2 }^{ \infty } p ( 1 - p )^{ i - 1 } = p \sum_{ i = 0 }^{ \infty } ( 1 - p )^i \\ k & = \frac{ 1 }{ p } \end{aligned} \]

则期望复杂度为\(O ( \frac{ f ( n ) }{ p } )\).

Example3(CF329C Graph Reconstruction)
Example4([Petrozavodsk Summer-2015. Moscow IPT Contest B]Game With A Fairy)

首先注意到一个问题:操作能得到的信息太少了,应该是没有什么确定性算法.因此考虑随机化,那就肯定要先将整个序列random_shuffle一下.

然后呢?我们考虑之后随机选取新序列的一个前缀询问,只要有大致的正确性/复杂性估计应该就是很正确的.

这里有一种方式:考虑这个前缀中第一个有宝藏的位置\(x_1\)和第二个位置\(x_2\),显然只要问到\([ x_1 , x_2 )\)是正确的.

考虑因为是随机,所以\(x_1 \times 2 \leq x_2\)的概率应当是不低的(事实上约为\(\frac{ 1 }{ 2 }\)),而此时的\([ x_1 , x_2 )\)中必有一个位置是二的整数幂,因此我们查询一个等比数列:\(1 , 2 , 4 , . . .\).每次random_shuffle后就查一次,就可以得到一个正确性较高的Las Vegas算法.

爬山与模拟退火

爬山

也就是随机一个起始的解,然后走向与其相邻的较大的解.

但是这样会卡在一个局部最优解上而得不到全局最优解.

于是我们就有了模拟退火算法.

模拟退火

简而言之,模拟退火就是以一定的概率跳到随机的不优秀的点,这样就避免卡在了局部最优解上.不妨设我们想找到最大解,如果要最小解那就稍微改改.

下面给出这个概率的公式:

\[ P = \begin{cases} 1 & E_{ t + 1 } > E_t \\ e^{ \frac{ E_{ t + 1 } - E_t }{ T } } & E_{ t + 1 } \leq E_t \end{cases} \]

具体流程是,先设定一个初始温度\(T_0\),降温速度\(k \in ( 0 , 1 )\),以及终止温度\(T_k\),每次操作后让\(T = kT\),直到其小于终止温度.