程序设计实习

• 随机化算法
  • 基本分析
    • Union Bound
    • Markov 不等式
      • Example(Max-Cut算法)
    • Chernoff Bound
      • Example(Median Trick)
    • Hoeffding 不等式
  • 编程中的随机性
  • 数值概率算法
  • Monte Carlo算法
    • 求解最优化问题的Monte Carlo算法
    • 求解判定性问题的Monte Carlo算法
    • 正确率与复杂度
    • 算法设计思路1
      • 设计一个能解决问题的确定性算法
      • 向算法引入随机化优化复杂度
    • 算法设计思路2
      • 设计一个能解决问题的确定性算法
      • 向算法引入随机化优化复杂度
    • Example
      • Example 1(Millar-Rabin算法)
      • Example2(CodeChef MSTONE)
      • Example3(CF364D Ghd)
      • Example4([POI2014]Couriers)
    • Example5([NOI2013] 向量内积)
  • Las Vegas算法(Sherwood算法)
    • 算法设计思路
      • 设计一个能解决问题的确定性算法
      • 向算法引入随机化优化复杂度
    • Example
      • 快速排序算法
      • 一类由Monte Carlo算法改造而成的算法
      • Example3(CF329C Graph Reconstruction)
      • Example4([Petrozavodsk Summer-2015. Moscow IPT Contest B]Game With A Fairy)
  • 爬山与模拟退火
    • 爬山
    • 模拟退火

随机化算法

基本分析

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{2z^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^2d)\).

冷静一下,这个过程其实就是一个矩阵乘法的过程:我们设\(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_kD_{k,j}\),不难解得:\(E_i=-\frac{1}{D_{i,j}}\sum_{k\ne i}X_kD_{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}^2X_j=\sum_{j}B_{i,j}X_jB_{h,i}^T\),大概做做.

Las Vegas算法(Sherwood算法)

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

算法设计思路

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

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

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

1. 随机化寻找排列来降低复杂度.
2. 通常证明复杂度和正确率巨大麻烦,这里建议直接实践证明.

Example

快速排序算法

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

不妨设\(T(n)\)表示对长度为\(n\)的序列运行快速排序算法所需的期望时间,我们有: \[ T(0)=0\\ T(n)=n+\frac{1}{n}\sum_{i=0}^{n-1}(T_i+T_{n-i-1}) \] 做放缩(可能有些地方需要\(+1\)或者\(-1\)或者加取整,但是问题不大,反正是期望): \[ 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{3n}{4}}(T(i)+T(n-i-1))+\frac{2}{n}\sum_{i=\frac{3n}{4}}^{n}(T(i)+T(n-i-1)) \] 由于\(T(n)\geq n\),所以对于\(\frac{n}2\leq i\leq j\),我们显然有:\(T(i)+T(n-i)\leq T(j)+T(n-j)\).

因此: \[ T(n)\leq n+\frac{2}{n}\sum_{i=\frac{n}{2}}^{\frac{3n}{4}}(T(\frac{3n}{4})+T(\frac{n}{4}))+\frac{2}{n}\sum_{i=\frac{3n}{4}}^{n}(T(n-1)+T(0))\\ \leq n+\frac{1}{2}(T(\frac{3n}{4})+T(\frac{n}{4})+T(n-1)) \] 我们要证明\(\exists c\),\(T(n)\leq cn\log n\),考虑使用数学归纳法,则: \[ T(n)\leq n+\frac{1}2(\frac{3cn}4\log(\frac{3n}{4})+\frac{cn}4\log(\frac{n}{4})+c(n-1)\log(n-1))\\ \leq n+c(\frac{3n}{8}\log n-\frac{3n}{8}\log\frac{4}{3}+\frac{n}{8}\log n-\frac{n}{4}+\frac{n}{2}\log n)\\ =cn\log n+n(1-\frac{3c}{8}\log(\frac{4}{3})-\frac{c}{4}) \] 于是显然存在,假设成立.

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

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

设其期望运行\(k\)次,则: \[ k=\sum_{i=1}^{\infty}p(1-p)^{i-1}i\\ (1-p)k=\sum_{i=1}^{\infty}p(1-p)^ii\\ pk=\sum_{i=2}^{\infty}p(1-p)^{i-1}=p\sum_{i=0}^{\infty}(1-p)^i\\ k=\frac 1 p \] 则期望复杂度为\(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\),直到其小于终止温度.