《第九章NP完全性理论与近似算法.ppt》由会员分享，可在线阅读，更多相关《第九章NP完全性理论与近似算法.ppt（31页珍藏版）》请在三一文库上搜索。
1、第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,1,第九章NP完全性理论,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,2,难？易？,可在多项式时间内解决的问题看作是“易”解问题。将需要指数函数时间解决的问题看作是“难”问题。这里所说的时间是针对问题规模n的多项式还是指数函数。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,3,内容,两部分：三种机器（RAM, RASP, TM）NP完全理论,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,4,随机存取机RAM(Random Access
2、 Machine)的构造,累加器,指令计数器,程序存储部件,内存储器,r0r1r2,只读输入带,只写输出带,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,5,随机存取机RAM的指令集,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,6,RAM机的复杂性标准,均匀耗费标准对数耗费标准,每条RAM指令需要一个单位时间，每个寄存器占用一个单位空间。,RAM指令的执行时间与操作数的长度的对数(l(i)成比例，一个寄存器可放一个任意大小的整数。,若每个操作数不超过一个机器字，则用均匀耗费标准是合理的，否则适用对数耗费标准。,第九章NP完全性理论与近似
3、算法,2022/1/16,计算机算法设计与分析,7,随机存取存储程序机RASP(Random Access Stored Program Machine),RASP与RAM的区别在于(1)RASP的程序存储在内存并且可以修改自身；(2)RASP不允许间接寻址，它通过修改指令模拟间接寻址。RASP的指令集见表9-4。RASP更加接近冯诺伊曼体系结构。无论是采用均匀耗费标准还是对数耗费标准，在相差一个常数因子的意义下，RAM与RASP是等价的。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,8,RAM与RASP是等价的,定理 不论在均匀耗费标准下还是在对数耗费标准下，对
4、时间复杂性为T(n)的任一RAM程序，都存在一个时间复杂性为kT(n)的RASP程序与之等价，k为常数。定理 不论在均匀耗费标准下还是在对数耗费标准下，对每一个时间复杂性为T(n)的RASP程序，都有一个时间复杂性为kT(n)的RAM程序与之等价，k为常数。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,9,图林机(Turing Machine)的构造,图林机(Turing Machine)是英国数学家Turing在1936年提出的计算模型，被认为是当今计算机的理论模型。下面是图林机(TM)原型的构造：,输入带,有限控制器,磁头,输入带被视为右无穷，并被划分为一个个
5、单元用于存放符号(带符号)。,有限控制器由有限个状态构成。,磁头可左右移动，读写带符号。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,10,图灵机的操作,根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面三个操作之一或全部。改变有限状态控制器的状态清除读写头下方的原有符号，并写上新的符号读写头向左或者向右移动一个方格，或不动,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,11,TM的数学描述,Q是有限状态的集合；T是有限个带符号的集合；I T，是输入符号的集合；：QTkQ(TL,R,S)k为转移函数；b是
6、唯一的空白符，bT I；q0和qf分别为初始状态和终止状态。,M = (Q, T, I, , b, q0, qf ) 其中：,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,12,的进一步说明,操作可以表示为(q,a1,ak)=(q,(a1,d1),(ak,dk)当图灵机处于状态q且对一切i，1=i=k，第i条带的读写头扫描着的当前方格中的符号为ai时，图灵机就按这个操作进行工作：q变为qa变为a左移或者右移,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,13,图灵机的语言,当且仅当从指定的初始状态q0开始，经过一系列计算步后，最终进入终止
7、状态qf时，称图灵机接受这个输入符号串。所有这台图灵机能接受的输入符号串的集合就是这台图灵机识别的一个语言。图灵机也可作为计算函数的装置。函数的自变量可编码成一字符串输入到一条输入带上，用一特殊符号隔开。若图灵机经过有限步后，在一条指定的带上输出整数y并停机，则可以说图灵机计算出了f(x)=y。如果对于某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。例：4整除问题：构造一个图灵机，判断输入的二进制串是否能被4整除。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,14,RAM与TM,由定理可知：可用RAM来模拟TM也可用TM来模拟RAM定理（补）：在对数耗
8、费标准下，对于同一个算法，采用RAM模型和TM模型的时间复杂性是多项式相关的。对空间复杂性亦如此。注意在均匀耗费标准下这个关系不成立。TM模拟RAM的时间复杂性可能是指数的关系。,三种机器在计算能力上是等价的，差别在于计算速度不同,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,15,图林机的变形,多道图林机(输入带上有多个道)。双向图林机 (输入带被视为左右均是无穷的)。多带图林机(具有多条输入带)。多头图林机 (具有多个磁头)。多维图林机(输入带是多维的)。不确定的图林机(有限控制器是不确定的)。,不确定的图林机类似于不确定的自动机，即：QT(QTL, R),将图
9、林机是原型称为确定的，记为DTM；而将不确定的图林机记为NDTM，,已经证明各类变形图林机在可计算的能力上等价于原型图林机。但是在复杂性是有区别的。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,16,NDTM(Nonditerministic Turing Machine),与DTM(diterministic Turing Machine)区别开来对于DTM，：QTkQ(TL,R,S)k只有一个唯一的值与它对应对于NDTM， 具有不确定性，有一个唯一的子集与之对应。区别在于：DTM每一步只有一种选择，而NDTM有多种选择。显然，DTM是NDTM的一个特例。,第九
10、章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,17,确定的图林机与不确定图林机,任何NDTM都可以用DTM来模拟实现，但其复杂性却不相同。对于一台复杂性为T(n)的NDTM，可用一台复杂性为O(CT(n)的DTM来模拟，这里C为常数。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,18,P类与NP类语言/问题,P = L | L在多项式时间被DTM接受NP = L | L在多项式时间被NDTM接受,这里也可用RAM等其它的机器模型来定义。但它们都是等价的。,若QNP，则可以用一个DTM来模拟接受Q的NDTM，所需要时间复杂性为O(CT(n)。
11、,这使人们认为NP类问题要比P类问题更难。,真的如此吗？,显然，因为DTMNDTM(是一个特例)，所以PNP。是否有PNP？,即是否有QNP，且QP？,这是个尚未解决的问题。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,19,问题的变换及时间等价性,若问题A的求解能够变换成问题B的求解且变换的时间为O(n)，则称A是(n)时间变换为B，简记为A(n)B，其中n为问题A的规模。若A(n)B，当(n)为多项式时，称A可多项式归结为问题B，记为AB 。一般来说，可变换性不是对称的。若A(n)B且B(n)A，则称A和B是(n)时间等价的。特别当(n)为线性时，称A和B等价
12、。这时A和B具有相同的时间复杂性。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,20,计算复杂性的归约,若A(n)B，设A和B的计算时间分别为TA(n)和TB(n)，则,TA(n) = (n) + TB(n),命题1 (计算时间下界归约) ：若TA(n)为A的计算时间下界，则B的计算时间TB(n)的下界为：,(TB(n) = TA(n) O(n),命题2 (计算时间上界归约) ：若TB(n)为B的计算时间上界，则A的计算时间TA(n)的上界为：,O(TA(n) = TB(n) + O(n),第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,
13、21,多项式归结与NP困难,多项式归结显然有如下两个性质：(1) AB且BP，则AP。 (2) 若AB且BC，则AC。定义：对于问题Q，如果任意问题QiNP，都有QiQ，则称问题Q是NP困难的。所谓NP困难的问题，是指该问题不会比NP中的任何问题容易，至少是同样难或更难。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,22,NP完全性,定义：对于问题Q，若满足QNP且Q是NP困难的，则称Q是NP完全的。所有NP完全的问题记为NPC。定理：设QNPC，P=NP当且仅当QP。如果PNP，则P，NP与NPC或许如下图所示：,NP,P,NPC,结论：如果任一NP完全问题可在
14、多项式时间内求解，则所有的NP中的问题都可在多项式时间内求解。反之，若NPP，则所有NP完全问题都不可能在多项式时间内求解,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,23,第一个NP完全的问题,Cook在1971年证明了第一个NP完全的问题。Cook定理：布尔表达式的可满足性SAT是NP完全的。,所谓可满足性SAT是这样的问题：给定k个布尔变量x1, xk的m个布尔表达式A1, , Am，若存在对各个布尔变量xi的0, 1赋值，使得每个布尔表达式Ai都为真，则称布尔表达式A1, , Am是可满足的。,Cook定理的证明由两个部分构成，第一部分是SATNP，这基本
15、是显然的。第二部分是任意LNP，可在多项式时间内转换为SAT问题。这是一个构造证明，即将接受L的NDTM的瞬象序列转换为一个SAT问题。,自从Cook证明了第一个NP完全的问题后，迄今为止，已经发现了至少有300多个NP完全的问题，但尚未证明其中任何一个是属于P的。,这一事实，增强了人们对PNP的猜测。但遗憾的是，这个猜测迄今仍然还只是个猜测。,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,24,若干NP完全问题,合取范式的可满足性问题CNF-SAT三元合取范式的可满足性3-SAT团问题CLIQUE顶点覆盖问题VERTEX-COVER子集和问题SUBST-SUM哈密
16、顿回路问题HAM-CYCLE旅行售货员问题TSP,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,25,近似计算,许多NP完全问题有很重要的实际意义。许多NP完全问题都是求最优化问题，如果不追求最优解，改为求一个满足要求的近似解，就会使得计算复杂性大大降低。因此非标准算法大多是求近似的满意解。近似计算的性能比函数(n)maxc*/c, c/c*, 其中c*和c分别为最优解的值和近似解的值。近似计算的相对误差界(n)|(c-c*)/c*|。显然(n) (n) 1。,第九章NP完全性理论与近似算法,26,Traveling Salesman Problem,B,A,C,D
17、,E,F,G,H,I,Asymmetric TSP (ATSP): (n-1)! TOURSComputer speed: 10e10 enumerations per second30! / 10e+10 2.65e+21 (s)i.e. 2.65e+21 / (365*24*60*60) 8.4e+13 (years),第九章NP完全性理论与近似算法,27,Serious damage to your position within the company !,“I cant find an efficient algorithm, I guess Im just too dumb.”,第
18、九章NP完全性理论与近似算法,28,“I cant find an efficient algorithm, because no such algorithm is possible!”,Unfortunately, proving intractability can be just as hard as finding efficient algorithms !, No hope !,P NP,第九章NP完全性理论与近似算法,29,“I cant find an efficient algorithm, but neither can all these famous people”,第九章NP完全性理论与近似算法,30,“Anyway, we have to solve this problem. Can we satisfy with a good solution ? “,第九章NP完全性理论与近似算法,2022/1/16,计算机算法设计与分析,31,实际应用的TSP问题,从实际应用中抽象出来的TSP问题具有一些特殊性质。三角不等式性质：对任意的三个顶点u,v,wV，有c(u,w)c(u,v) + c(v,w),