Mengzelev's Blog

难问题求解学习笔记-随机算法

Word count: 1,175 / Reading time: 5 min
2019/05/25 Share

前言

输出为随机变量的算法称为蒙特卡洛算法(Monte Carlo)
输出总是正确的但时间复杂度为随机变量的算法称为拉斯维加斯算法(Las Vegas)

概率论理论引入了随机算法$A$与确定输入$x$构成的随机试验。试验可以被描述为概率空间$(S_{A,x},Prob)$,其中$S_{A,x}={C\mid C \text{is a computation (radom run) of } A \text{ on } x}$,$Prob$是$S_{A,x}$上的概率分布。

基础

一种新的复杂度度量

$Random_A(x)$: 对于所有$A$在$x$上的随机计算中使用的random bits的最大数量
$Random_A(n)=\max{Random_A(x)\mid x \text{is a input of size }n}$

这么衡量的两点原因

  • 产生真随机数非常困难,且真随机序列越长越困难
  • 如果一个算法的$Random_A(x)$是对数级的,那就可能可以在多项式时间内追踪它的所有运行的可能情况,做到去随机化(derandomization)

$Prob_{A,x}(C)$: 某一次$A$对输入$x$的计算$C$, 由相应的随机序列的概率决定
$Prob(A(x)=y)$: $A$ outputs $y$ for an input $x$的概率
$Time(C)$: the time complexity of the run $C$ of $A$ on $x$

期望时间复杂度of $A$ on $x$(expected time complexity)
$$Exp-Time_A(x)=E[Time]=\sum\limits_{C}Prob_{A,x}(C)\cdot Time(C)$$

$A$的期望时间复杂度(worst case approach)
$$Exp-TIme_A(n)=\max{Exp-Time_A(x)\mid x \text{is an input of size } n}$$

$$Time_A(x)=\max{Time(C)\mid C \text{ is a run of} A \text{on} x }$$
$$Time_A(n)=\max{Time_A(x)\mid x \text{ is an input of size }n}$$

随机算法不一定会终止,可能会进行无限次计算,在实际情况下可以在某一时间后叫停,算法输出”?”,即无法在给定时间内解决该问题,然后重新开始

随机算法的分类

拉斯维加斯算法

拉斯维加斯算法与其时间复杂度有两种定义方式,适用于不同的场景

第一种定义

若对问题$F$的任意输入实例$x$,$Prob(A(x)=F(x))=1$,其中$F(x)$是问题$F$对于输入$x$的解,则称$A$是计算问题$F$的拉斯维加斯算法。这种定义下时间复杂度是$Exp-Time_A(n)$

第二种定义

允许”?”输出
若对问题$F$的任意输入实例$x$,$Prob(A(x)=F(x))\ge\frac{1}{2}$且$Prob(A(x)=”?”)=1-Prob(A(x)=F(x))\le\frac{1}{2}$.
这种定义下时间复杂度采用$Time_A(n)$

第一种定义一般用于计算函数,第二种一般用于计算decision problem

单边误差蒙特卡洛算法

ONE-SIDED-ERROR MONTE CARLO ALGORITHMS

$L$的单边蒙特卡洛算法满足

  • 对任意$x\in L, Prob(A(x)=1)\ge 1/2$
  • 对任意$x\notin L, Prob(A(x)=0)=1$

重复次数越多,得到正确答案的可能性就越大

质数定理:集合${1,2,\cdots,m}$中质数的个数大约是$m/\ln m$,且当$m\ge 100$时至少是$m/\ln m$

双边误差蒙特卡洛算法

TWO-SIDED-ERROR MONTE CARLO ALGORITHMS

若存在实数$\varepsilon, 0\le\varepsilon <1/2$,满足对于$F$的任意输入$x, Prob(A(x)=F(x))\ge\frac{1}{2}+\varepsilon$,则称该算法为$F$的双边蒙特卡洛算法

无限制误差蒙特卡洛算法

UNBOUNDED-ERROR MONTE CARLO ALGORITHMS

若对于$F$的任意输入$x, Prob(A(x)=F(x))>\frac{1}{2}$,则称这样的算法$A$是无限制蒙特卡洛算法

随机最优化问题

判定问题的随机算法是选择出现最多的答案,而最优化问题是选择最接近(根据cost function)的答案

随机近似算法

随机算法可以看成是以高概率得到与最优解差别不大的解的近似算法

定义5.2.2.10:设$U=$(略)是一个最优化问题。对任意正实数$\delta>1$,随机算法$A$是$U$的随机$\delta-$近似算法,若$A$满足以下要求

  • $Prob(A(x)=\mathcal{M}(x))=1$且
  • $Prob(R_A(x)\le\delta)\ge 1/2$

对任意$x\in L_I$

类似可定义随机$f(n)-$近似算法

随机多项式近似方案(RPTAS)

还有随机 完全多项式近似方案(RFPTAS)

$\delta-$期望近似算法

以上两种定义互不包含

随机算法设计

挫败对手

随机选择一系列算法中的一个,这样就无法特意构造一组最坏输入

充分取证

常用于判定问题

如Example5.2.2.6的取模运算

指纹

用于判定等价问题

随机采样

松弛与随机舍入

比如把线性规划的值舍入成整数规划

CATALOG
  1. 1. 前言
  2. 2. 基础
    1. 2.1. 一种新的复杂度度量
  3. 3. 随机算法的分类
    1. 3.1. 拉斯维加斯算法
      1. 3.1.1. 第一种定义
      2. 3.1.2. 第二种定义
    2. 3.2. 单边误差蒙特卡洛算法
    3. 3.3. 双边误差蒙特卡洛算法
    4. 3.4. 无限制误差蒙特卡洛算法
    5. 3.5. 随机最优化问题
      1. 3.5.1. 随机近似算法
  4. 4. 随机算法设计
    1. 4.1. 挫败对手
    2. 4.2. 充分取证
    3. 4.3. 指纹
    4. 4.4. 随机采样
    5. 4.5. 松弛与随机舍入