《10np-完全问题剖析》由会员分享，可在线阅读，更多相关《10np-完全问题剖析（52页珍藏版）》请在金锄头文库上搜索。
1、10 NP-完全问题,理解有限自动机、下推自动机和图灵机计算模型 理解P类与NP问题 了解NP-完全问题 思考NP-完全问题的计算机实现,学习要点,计算模型,建立计算模型的目的是为了使问题的计算复杂性分析有一 个共同的客观尺度。 3个基本计算模型： （1）有限自动机 （2）下推自动机 （3）图灵机,有限自动机,有限自动机由中央处理单元、输入纸带和一个读入头组成，其中读入头联系中央处理单元与输入纸带。 中央处理单元联系着数目有限的内部状态，这个有限的状态集合可以表示为：S0, S1, , Sn 集合中包含了初始状态S0，中间状态，和终止状态（终止状态组成的集合记为F，F是的子集）。 输入纸带被划
2、分为一个个方格，左右两端可以无限延长。要输入的字符序列就写在纸带上，自左至右，一个字符占一个方格。如果没有输入字符的话，方格里就填上表示空格的字符#。纸带只能向一个方向移动（自右向左）。出现在纸带上的字符构成了一个输入字符集，如：VA=a1, a2, an 沟通中央处理单元和输入纸带的是一个读入头，它只能读取纸带上的字符，但是不能对其进行修改。自动机启动时，读入头总是处于左端第一个输入字符上，以后它每读入一个字符，输入纸带也就相应地左移一格。,有限自动机,自动机内部有一组数目有限的转移规则T： (ai, Sj) Sk ，表示：当机器处于状态Sj时，如果读入字符ai，则转移到状态Sk。 转移规则
3、实际上就是一些指令，它根据读入的字符，决定机器内部状态的变换。 显然，有限自动机就是一个包含了输入字符集、有限内部状态（包括初始状态中间状态和终止状态）和一组转移规则的形式系统。这个形式系统可以表述如下： FSM 有限自动机的操作流程是：根据读入头读入的字符和机器内部的转移规则，不断地改变中央处理单元的内部状态，当自动机读完最后一个字符停下来时，如果这时机器的内部状态恰好就是终止状态，那么输入字符序列就被自动机接受了；否则，就表示输入字符序列就被拒绝。,下推自动机,下推自动机输出部分的读写头具有在输出纸带方格内写入字符或抹除字符的功能，也就是用空格符号去替代原有的字符。输出纸带的左端以特殊字符
4、开始，它可以左右移动。当输出纸带其向左移动时，读写头就在纸带上写入输出字符bi ，输出字符被写在右边和读写头紧密相连的纸带方格上；当输出纸带向右移动时，读写头就“抹除”原先已贮存到纸带上的当前字符。输出部分具有特殊的贮存功能，具有一种先进后出而后进先出的特殊记忆形式。,下推自动机,下推自动机增添了输出装置，整个系统也就比有限自动机多了一个输出（或贮存）字符集VB： VB = b1, b2 , , bn 同时，转移规则的形式也复杂了起来，其指令形式为： (ai, Sj, bk) (Si, O),在机器运行时，执行指令(ai, Sj, bk) (Si, O) ，使中央处理单元从状态Sj转移到Si
5、，输入纸带向左移动一格；输出部分的读写头或在向左移动一格的输出纸带上写入bk，或者抹除向右移动的输出纸带上当前方格内原有的字符，我们在这里约定表示抹除工作的符号是R。经抹除后，# 就替代了原有的字符bk.，当空字符e出现在ai 或bk 上时，相对应的纸带就不作任何移动。,下推自动机,（1）所有的输入字符都被读过； （2）中央处理单元处于终止状态 （3）输出纸带是完全空的，即读写头仍处于位置上。,下推自动机的形式系统可以表示成：(VA, VB, , T, F ) 下推自动机的操作从初始状态S0开始，此时读入头处于输入纸带最左端的字符上，而读写头则处于输出纸带的字符上，输出纸带的右侧部分都是空格。
6、根据输入和输出的字符以及转移规则，机器不断地改变其内部状态，直到满足下述情况之一，就证明自动机接受了输入字符序列；否则，就表示拒绝。,图灵机,同有限自动机相比，TM有三个基本的不同： （1）TM联系中央处理单元和纸带的是一个读写头。读写头既可以读入纸带上的输入 字符，也可以反过来在纸带上写上输出字符，然而有限自动机是一个读入头，它只能输入，不能输出。 （2）TM的纸带既可以向左移动，也可以向右移动，还可以停住不动。它既是输入纸带，还可以充当输出纸带，而在有限自动机上，纸带只能朝一个方向移动。 （3）纸带可以为k条，k的范围为k1，而在有限自动机上，纸带只有一条。,图灵机,单带TM的形式系统可以
7、表示为：TM=（V, , F, T）,包括一个输出-输入字符集V; 一组数目有限的有限状态的集合 ，其中s0是初始状态；终止状态集F（F是的一个子集）；一组转移规则的集合T。 由于图灵机既可以从纸带读入字符，也可以向纸带写字符，纸带可以两个方向上移动，因此它可以拥有的转移规则如下： （1）(ai, Sj)（at, Si) （2）(ai, Sk)（R, Si) （3）(ai, Sl)（L, Si) 在（1）中字符ai 被字符at 所代替, 但纸带并不移动；在（2）中，纸带向右移动一格，但读写头并不在纸带上写出任何字符, R表示向右移动；在（3）中，纸带向左移动一格，但读写头并不输出字符，L表示向
8、左移动。 例10.1,图灵机,根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。,例 10.2,图灵机,k带图灵机的形式化描述：(Q，T，I，b，q0，qf)，其中: (1)Q是有限个状态的集合。 (2)T是有限个带符号的集合。 (3)I是输入符号的集合，IT。 (4)b是唯一的空白符，bT-I。 (5)q0是初始状态。 (6)qf是终止(
9、或接受)状态。 (7)是移动函数。它是从QTk的某一子集映射到Q (TL，R，S)k的函数。,例 10.2,图灵机,图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。,图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。,图灵机既可作为语言接受器，也可作为计算函数的装置。,一些难解问题,（1）图着色问题 图G=的着色，是指一个映射函数C:VS,此函数满足：如果E，则有c(i)c(j),即G中任意两个相邻顶点不被置
10、为相同颜色，其中，S为一有限的颜色集合。 图G=(V,E)的色数K是指为图G着色所用到的最少色数，即 K=min|C(V)|,C(V)为G的着色方案。 图着色问题，就是求图G=(V,E)的色数K。 （2）0-1背包问题 已知：容量为C的背包和n个对象的集合U，对象的重量为w1,w2,wn,价值为v1,v1,vn。 0-1背包问题：如何选择装入背包中的对象，使得装入背包中对象的总价值最大？,一些难解问题,（）装箱问题 有任意多个容量为l的箱子和大小为Si（0si 1)的n个物体。 装箱问题：求可以装下n个物体的最小箱数。 把n个物体装入n个n个箱子，肯定装得下。但如果要求最小的装箱数，问题就变得
11、复杂了，因为对每个箱子可能有许多种不同的装法。如果要求最紧凑的装箱分配，当n比较大时，其计算量也是十分惊人的。,一些难解问题,（4）作业调度问题 作业调度是这样一类问题，按照细节不同可以形成不同的问题，这里介绍带罚款的作业调度问题。 已知：n项作业J1,J2,Jn将按照某种次序依次完成，它们所需的执行时间为t1,t2,tn,要求最迟完成的时间为d1,d2,dn (从第一项作业开始执行的时间开始计算），以及逾期未完成该项作业的罚款数为p1,p2,pn。 带罚款的作业调度问题：求一种调度方案，即求1,2,n 的一种排列，使得按这种顺序完成n项作业所付出的罚款数最小。,一些难解问题,（5）可满足性问
12、题 这个问题也称合取范式的可满足问题。 一个合取范式形如：A1A2An（即若干子句的逻辑乘） 子句Ai形如：a1a2ak,其中aj(1=j=k)为某一布尔变量或是该变量的非。 合取范式的可满足性问题：是否有一组对所有命题变量的赋值（F或T)，使得整个CNF取值为真（T）。,一些难解问题,（6）图的团集问题 图G=的团集，是指G的一个完全子图，即该子图中任意两个互异的顶点都有一条边相连。 无向图G=的团集问题：求G的最大子团。,v2,v1,v3,v5,v4,一些难解问题,（7）Hamiltonian回路问题和hamiltonian路径 Hamiltonian回路：图G=的hamiltonian回
13、路是指由G的n条边组成的经过G的每一个顶点且仅经过一次的周游路线。 Hamiltonian回路问题：求G=V,E的Hamiltonian回路。 Hamiltonian路径：图G=的Hamiltonian路径是指经过G的所有顶点且经过一次的路径。,（8）旅行商问题 这个问题实际上是一个带权图的hamiltonian问题。 。,多项式界与P类问题,一、多项式（时间）界 区分难解问题与易解问题的界限就是多项式（时间）界。 计算复杂性理论的两个基本论题： Church-Turing 论题 Cook-Karp 论题 Church-Turing论题利用Turing机指出了那些问题是可计算的，这个“可计算的
14、”问题类非常大，几乎所有的问题都是可计算的，反例不多。 Cook-Karp论题则是：在可计算的问题（函数）中，只有在多项式阶时间内可计算的问题才是实际可计算的，称为该计算是可行的或该问题是易解的。这个易解问题类就称为P类，是可计算问题类的一个很小的子集。,多项式界与P类问题,算法A是多项式（时间）界的，是指算法A的最坏情形时间复杂度是一个问题输入长度为n的多项式函数p(n)，即算法A总能在p(n)步之内结束。有时也简称A为多项式算法。 问题P是多项式（时间）界的，是指问题P有一个多项式（时间）界的算法。问题P一般称为P类问题，或易解问题。,多项式界与P类问题,为什么把复杂度函数是否可表示为多项
15、式函数作为区分易解和难解的分界线？可有下面的讨论中得到启示。 （1）多项式函数与指数函数的增长率确实有本质的差别。 （2）计算机自身性能的提高，对于多项式界问题和非多项式界问题的解决的影响也是不同的。 （3）多项式界的划分，忽略了n的阶数和系数的影响。,多项式界与P类问题,表10.1 多项式函数与非多项式（指数）函数的性能比较,多项式界与P类问题,（4）从理论上来说，多项式具有两个性质： “闭包”性质：许多实际问题是一些子问题的组合或重叠。而多项式函数通过算术运算的组合或重叠（即多项式函数的多项式函数），得到的仍然是多项式界的。 不同计算模型的“独立”性或不依赖性：即某一问题在一种计算模型（如
16、Turing机）下有多项式算法，那么它一定也在其它几种模型下有多项式算法。,问题求解与判定问题,可满足性问题要求回答“yes”或 “no”。这类问题称为判定问题。 判定问题实际上是要判定一个元素或对象是否属于某一特定的集合，如可满足性问题。问题求解或函数计算的概念比判定问题更广泛，如着色问题、旅行商问题等。,问题求解与判定问题,以着色问题为例： 1、求解形式 已知n个顶点的图G=,求对G的n个顶点进行着色的一种方案。 问题的答案是一种着色方案。为每个顶点赋一种颜色。 2、求值形式 已知n个顶点的图G=,求对G的n个顶点进行着色的一种方案。 问题的答案是一个值。 3、判定形式 已知n个顶点的图G=,问G是否可以用k种颜色着色？ 答案是：yes或no,P类与NP类问题,一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。 有许多问题，至今人们还
