算法-NP完全性与近似算法.ppt

算法设计与分析 2017 年2月26日讲授内容: NP 完全性与近似算法教 师: 胡学钢、吴共庆纲要?判定问题与最优化问题?多项式时间归约?利用多项式时间归约分析问题的复杂性?P、 NP 、 NP-hard 、 NPC ?电路可满足性问题? NPC 问题的证明方法?顶点覆盖问题?处理 NP-hard 问题?近似算法 2/26/2017 算法设计与分析-NP 完全性与近似算法 2 举例?容易的和困难的问题–最短简单路径 vs. 最长简单路径问题–欧拉回路 vs. 汉密尔顿回路– 2-SAT 问题 vs. 3-SAT 问题等 2/26/2017 算法设计与分析-NP 完全性与近似算法 3 判定问题与最优化问题?最优化问题问题的每个可行解都对应一个目标函数值,求解这类问题的目的是希望得到一个有最优目标函数值的可行解?判定问题回答是否存在一个满足问题要求的解,即解只是简单的回答“是(1) ”或“否(0) ”。?最优化问题与它相应的判定问题具有密切的联系,通过限界最优化问题要优化的目标函数值,通常可以把一个最优化问题转化为一个判定问题。?例如,最短路径问题的目标是找一条从 u到v的最短路径,优化的目标函数值是路径的边数。则相应的判定问题(Path) 可以描述为:给定一个有向图 G,顶点 u和v,以及整数 k,问图中从 u到v是否存在一条最多 k条边的路径。 2/26/2017 算法设计与分析-NP 完全性与近似算法 4 多项式时间归约?归约(Reduction) 实例: 具体问题的输入?多项式归约算法:一个过程能转化 A的任何一个实例α到B的某个实例β,且过程具有下列性质:(1)该转化过程只需要多项式时间就可以完成; (2)答案是一致的。也就是说, α的答案是“是”当且仅当β的答案也是“是”。 2/26/2017 算法设计与分析-NP 完全性与近似算法 5 多项式时间归约 2/26/2017 算法设计与分析-NP 完全性与近似算法 6 利用多项式时间归约分析问题的复杂性?用多项式时间归约算法的思想来证明特定的问题 B 不存在多项式时间算法–假设我们有一个判定问题 A,而且我们知道不存在求解 A 的多项式时间算法。–假设有多项式时间归约算法可以把 A的任意一个实例转化为B的一个实例–这样我们可以用简单的反证法来证明 B没有多项式时间的算法。?证明的思路是,假设 B有多项式时间算法,则按照上述归约算法的思想,我们也能证明 A也有多项式时间算法,这与已知不存在求解 A的多项式时间算法矛盾。 2/26/2017 算法设计与分析-NP 完全性与近似算法 7 P、NP、NP-hard 、NPC ?一个具体问题是多项式时间可解的如果该问题存在一个多项式时间 O(n k)求解算法,其中 k为一个常数。因此我们可以定义复杂类 P为多项式时间可解的具体判定问题的集合。?定义 P类语言= { L∈{0, 1} * : there exists an algorithm A that decides L in polynomial time } ?定理 P类语言={ L : L is accepted by a polynomial-time algorithm} 2/26/2017 算法设计与分析-NP 完全性与近似算法 8 P、NP、NP-hard 、NPC ?定义验证算法 A为带两个参数的算法。一个参数是给定的输入串 x(即输入实例),另一个参数是一个证书 y(即解)。如果存在一个证书 y,使得 A(x,y ) = 1 ,则说算法 A验证了输入串 x。因此,我们可以定义能够被算法 A所验证的语言 L ={x∈{0,1} * :there exists y∈{0,1} * such that A(x, y )=1}. ?直观地说,如果对任何的串 x,存在证书 y,能够用该证书证明 x∈L,而且,对任何 x ?L,没有证书能够证明 x∈L,则说算法验证了语言。 2/26/2017 算法设计与分析-NP 完全性与近似算法 9 P、NP、NP-hard 、NPC ?复杂类 NP ?定义复杂类 NP 指的是一类能够被多项式时间验证算法所验证语言的集合。?一个语言 L属于 NP 当且仅当存在有两个输入的多项式时间算法 A和常数 c,使得 L = { x∈{0, 1} * : there exists a certificate y with | y | = O (|x| c ) such that A(x, y ) = 1}. ?意思是说,算法 A在多项式时间内验证了语言L。 2/26/2017 算法设计与分析-NP 完全性与近似算法 10