高级算法(1)--NP完全性与近似算法

本节内容:本学期修读了尹一通老师的高级算法课,感觉略有困难,故将学习过程中的知识点以博客的形式记录下来,温故而知新,本节总结NP完全性问题和近似算法的概念。

NP完全理论

NP理论如下:

  • 多项式时间:一个问题的计算时间m(n)不大于问题大小n的多项式倍数。

  • 判定问题:判定某类问题是否具有算法解,或者是否存在能行性的方法使得对该问题类中的每一个特例能在有限步内机械地判定它是否具有某种性质的问题。

  • P类问题:在多项式时间内求解的判定问题构成P类问题。

  • 非确定性算法:非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的,算法的验证阶段是确定性的,它验证猜测阶段给出解的正确性。

  • NP类问题:非确定性多项式时间可解的判定问题构成NP类问题。

  • NPC问题:NP中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的。

  • NPH问题:某个问题被称作NP困难,当所有NP问题可以在多项式时间归约到这个问题。

它们之间的关系:

$$P \subseteq NP, NPC \subseteq NP, NPC \subseteq NPH$$

近似算法

在计算复杂性理论中的某些假设下,比如最著名的 $ P\neq NP $假设下,对于一些可已被证明为NP完全的优化问题,无法在多项式时间内精确求到最优解,然而在现实或理论研究中,这类问题都有广泛的应用,在精确解无法得到的情况下,转而依靠高效的近似算法求可以接受的近似解。

近似比

对于一个最大化问题的实例,设其最优解是 $ OPT $,某个近似算法的解是 $x$,若下式成立,

$$\alpha \leq \frac{x}{OPT} \leq 1 $$

其中 $ 0<\alpha <1 $ 则定义此近似算法的近似比为 $ \alpha $。

相应的,对于一个最小化问题的实例,

$$\alpha \geq \frac{x}{OPT} \geq 1 $$

其中 $\alpha >1$则定义此近似算法的近似比为 $ \alpha $。

分类

按照可以达到近似比的不同,可以将近似算法大致按以下分类:

  • FPTAS(Fully Polynomial-Time Approximation Scheme):FPTAS要求算法对问题规模n和1/ε都是多项式时间复杂度的,称为完全多项式时间近似模式,如$O((1/ε)^2n^3)$。

  • PTAS(Polynomial-Time Approximation Scheme):该算法的输入为问题的实例以及一个任意小的值ε > 0,而算法的结果是一个近似度为 1 + ε的可行解;并且对于每一个固定的ε,算法运行时间复杂度对于实例的规模n是多项式时间的,如$O(n^{2/ε})$。

  • 常数近似

  • 对数的多项式

  • 多项式

其中对数的多项式和多项式都是对应于输入规模的。

设计方法

近似算法的常用设计方法有贪心法,线性规划、半正定规划的松弛和取整,随机算法等。

课程网站

随机算法/高级算法