Mengzelev's Blog

难问题求解学习笔记-近似算法

Word count: 1,712 / Reading time: 8 min
2019/05/18 Share

概念

近似算法是能提供最优化问题的可行解的算法,所提供的解的质量不会与最优解相差太多

形式化定义:$U={\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal}$是一个最优化问题,$A$是$U$的consistent algorithm. 对任意$x\in L_I$, $A$在$x$上的相对误差(relative error)$\varepsilon_A(x)$定义为
$$\varepsilon_A(x)=\frac{|cost(A(x))-Opt_U(x)|}{Opt_U(x)}$$
对任意$x\in\mathbb{N}$,定义$A$的相对误差$$\varepsilon_A(n)=\max{\varepsilon_A(x)|x\in L_I\cap (\Sigma_I)^n}$$
对每个$x\in L_I$,$A$在$x$上的的近似率(approximation ration)$R_A(x)$定义为$$R_A(x)=\max{\frac{cost(A(x))}{Opt_U(x)}, \frac{Opt_U(x)}{cost(A(x))}}$$
对任意$n\in\mathbb{N}$,定义$A$的近似率为$$R_A(n)=\max{R_A(x)|x\in L_I\cap (\Sigma_I)^n}$$
$R_A$又名最坏情况性能(worst case performance),近似因子(approximation factor), 性能约束(performance bound),性能率(performance ratio),误差率(error ratio)

若$A$是最小化问题且$R_A(x)=\frac{Opt_U(x)}{cost(A(x))}$,则$R_A(x)=1+\varepsilon_A(x)$

对于任意正实数$\delta>1$,若$R_A(x)\le\delta$对任意$x\in L_I$恒成立,则称$A$是$U$的$\delta-$近似算法
对任意函数$f:\mathbb{N}\to\mathbb{R}^+$,若$R_A(x)\le f(n)$对任意$n\in\mathbb{N}$恒成立,则称$A$是$U$的$f(n)-$近似算法

近似方案(approximation scheme)

用户可以指定一个小的相对误差值$\varepsilon$,程序可以提供出一个误差至多为$\varepsilon$的可行解

定义4.2.1.6:$U={\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal}$是一个最优化问题。若对任意输入对$(x,\varepsilon)\in L_I\times\mathbb{R}^+$, $A$计算出一个相对误差至多为$\epsilon$的可行解$A(x)$, 且$Time_A(x,\varepsilon^{-1})$以某个$|x|$的多项式函数为界,则称$A$是$U$的多项式时间近似方案(polynomial-time approximation scheme, PTAS). 若$Time_A(x,\varepsilon^{-1})$以某个同时是$|x|$和$\varepsilon^{-1}$的多项式的函数为界,则称$A$是$U$的完全多项式近似方案(fully polynomial-time approximation scheme, FPTAS)

一般来说$Time_A(x,\varepsilon^{-1})$关于$|x|$和$\varepsilon^{-1}$都单调递增

好处:用户有权决定要快还是要精度

最优化问题的分类

在近似的意义下NPO可以被分为以下五类:

  • NPO(I): NPO中所有存在FPTAS的最优化问题(e.g.背包问题)
  • NPO(II): NPO中所有存在PTAS的最优化问题(e.g. MS)
  • NPO(III): 包含所有$U\in NPO$满足:
    • 对某些$\delta>1$存在多项式时间的$\delta-$近似算法
    • 对某些$d<\delta$不存在多项式时间的的$d-$近似算法
    • i.e.$U$没有PTAS
  • NPO(IV): 包含所有$U\in NPO$满足:
    • 对某些$f:\mathbb{N}\to\mathbb{R}^+$,存在多项式时间的$f(n)-$近似算法,其中$f$以某个多项式函数为界
    • 对任意$\delta\in\mathbb{R}^+$不存在任何多项式时间的$\delta-$近似算法
    • e.g.集合覆盖问题
  • NPO(V): 包含所有$U\in NPO$,满足若存在多项式时间的$f(n)-$近似算法,则$f(n)$不以任何多项式函数为界(e.g. TSP, 最大团问题)

以上分类都基于合理的假设P$\neq$NP
所有集合都是非空的

近似算法的稳定性

即使是NPO(V)中的问题,也可能有很大一部分的输入是比较简单的

稳定性用来衡量问题实例的限定(参数,特性等)对近似率的影响
如果对模型的限制影响近似率的程度很低,则可以说我们的算法是稳定的

定义4.2.3.1:$U={\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal}$, $\overline{U}={\Sigma_I, \Sigma_O, L, L, \mathcal{M}, cost, goal}$是两个最优化问题,$L_I\subseteq L$. $\overline{U}$依据$L_I$的距离函数(distance function for $\overline{U}$ according to $L_I$)是任何满足下列性质的函数$h_L:L\to\mathbb{R}^+\cup{0}$:

  • 对任意$x\in L_I, h_L(x)=0$
  • $h$可以在多项式时间内计算

定义:对任意$r\in\mathbb{R}^+$,$$Ball_{r,h}(L_I)={w\in L\mid h(w)\le r}$$

$p$是正实数,若对任意实数$0\le r\le p$, 存在$\delta_{r,\varepsilon}\in\mathbb{R}^{>1}$, $A$是$U_r={\Sigma_I, \Sigma_O, L, Ball_{r,h}, \mathcal{M}, cost, goal}$的$\delta_{r,\varepsilon}-$近似算法,则称$A$是p-stable according to $h$

若对任意$p\in\mathbb{R}^+$,$A$都是p-stable的,则称$A$是stable according to $h$
反之,若对任意$p\in\mathbb{R}^+$,$A$都不是p-stable的,则称$A$是unstable according to $h$

对任意正整数$r$和任意函数$f:\mathbb{N}\to\mathbb{R}^{>1}$,若$A$是$U_r={\Sigma_I, \Sigma_O, L, Ball_{r,h}, \mathcal{M}, cost, goal}$的$f_r(n)-$近似算法,则称$A$是$(r,f_r(n))$-quasistable accroding to $h$

把PTAS$A$看作一系列多项式时间$(1+\varepsilon)-$近似算法的集合$A_\varepsilon$.若在某个距离度量$h$下对任意$\varepsilon>0$,$A_\varepsilon$都是稳定的,则我们可以得到以下二者之一

  • $U_r$的一个PTAS(for every $r\in\mathbb{R}^+$)
  • $U_r$的一个$\delta_{r,\varepsilon}$近似算法,但没有PTAS

定义4.2.3.6: $U,\overline{U}$定义同上。$h$是$\overline{U}$根据$L_I$的距离函数,$U_r$同上。设$A={A_\varepsilon}{\varepsilon>0}$是$U$的一个PTAS
若对任意$r>0$和$\varepsilon>0$,$A
\varepsilon$是$\delta_{r,\varepsilon}$-近似算法,则$A$是关于$h$stable的
若$\delta_{r,\varepsilon}\le f(\varepsilon)\cdot g(r)$,其中$f$和$g$是某些$\mathbb{R}^{\ge 0}\to\mathbb{R}^+$的函数且$\lim\limits_{\varepsilon\to 0}f(\varepsilon)=0$, 则称$A$关于$h$超稳定(superstable).

如果$A$对$U$超稳定,则$A$对$U_r$也超稳定

对偶近似算法

修改限制条件$\mathcal(M)$来简化计算

定义4.2.4.1:$U={\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal}$是一个最优化问题。$U$的限制距离函数(constraint distance function)是任何满足下列条件的函数$h:L_I\times\Sigma^*_O\to\mathbb{R}^{\ge 0}$:

  • 对任意$S\in\mathcal{M}(x), h(x,S)=0$
  • 对任意$S\notin\mathcal{M}(x), h(x,S)>0$
  • $h$是多项式时间内可计算的

对任意$\varepsilon\in\mathbb{R}^+$,任意$x\in L_I$,$\mathcal{M}_\varepsilon^h(x)={S\in\Sigma_O^*\mid h(x,S)\le\varepsilon}$是$\varepsilon-$ball of $\mathcal{M}(x)$ according to $h$.

定义4.2.4.2: $U$是最优化问题,$h$是$U$的限制距离函数. 若对任意$x\in L_1$,有$A(x)\in\mathcal{M}_\varepsilon^h(x)$且$cost(A(x))\ge Opt_U(x)$ if $goal=maximum$且$cost(A(x))\le Opt_U(x)$ if $goal=minimum$, 则称$A$是$U$的$h-$对偶$\varepsilon-$近似算法

定义4.2.4.3: 条件同上。若

  • 对任意输入$(x,\varepsilon)\in L_I\times\mathbb{R}^+, A(x,\varepsilon)\in\mathcal{M}_\varepsilon^h(x)$
  • $cost(A(x))\ge Opt_U(x)$ if $goal=maximum$且$cost(A(x))\le Opt_U(x)$ if $goal=minimum$
  • $Time_A(x,\varepsilon^{-1})$以某个$|x|$的多项式函数为界

则称$A$是$U$的$h-dual$PTAS
类似的可以定义$U$的$h-dual$FPTAS

总结

降低问题难度的方法:

  • 对输出精度要求降低
  • 对输入做限制
CATALOG
  1. 1. 概念
  2. 2. 近似方案(approximation scheme)
  3. 3. 最优化问题的分类
  4. 4. 近似算法的稳定性
  5. 5. 对偶近似算法
  6. 6. 总结