第9章 NP完全性理论与近似 算法1学习要点理解RAM，RASP和图灵机计算模型理解非确定性图灵机的概念理解P类与NP类语言的概念 理解NP完全问题的概念理解近似算法的性能比及多项式时间近似格式的概念通过范例学习NP完全问题的近似算法（1）顶点覆盖问题；（2）旅行售货员问题；（3）集合覆盖问题；（4）子集和问题。29.1 计算模型n在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。n建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。n3个基本计算模型：n随机存取机RAM(Random Access Machine)；n随机存取存储程序机RASP(Random Access Stored Program Machine)n图灵机(Turing Machine)。n这3个计算模型在计算能力上是等价的，但在计算速度上是不同的。39.1.1 随机存取机RAM1、RAM的结构49.1.1 随机存取机RAM2、RAM程序一个RAM程序定义了从输入带到输出带的一个映射。可以对 这种映射关系作2种不同的解释。解释一：把RAM程序看成是计算一个函数 若一个RAM程序P总是从输入带前n个方格中读入n个整数 x1，x2，xn，并且在输出带的第一个方格上输出一个整数y 后停机，那么就说程序P计算了函数f(x1，x2，xn)=y 解释二：把RAM程序当作一个语言接受器。 将字符串S=a1a2an放在输入带上。在输入带的第一个方 格中放入符号a1，第二个方格中放入符号a2，第n个方格中 放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标 志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出 带的第一格输出一个1并停机，就说程序P接受字符串S。 59.1.1 随机存取机RAM3、 RAM程序的耗费标准标准一：均匀耗费标准 在均匀耗费标准下，每条RAM指令需要一个单位时间；每 个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂 性将按照均匀耗费标准衡量。 标准二：对数耗费标准 对数耗费标准是基于这样的假定，即执行一条指令的耗费 与以二进制表示的指令的操作数长度成比例。在RAM计算模型下， 假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整 数i所占的二进制位数，则 69.1.2 随机存取存储程序机RASP1、RASP的结构RASP的整体结构类似于RAM，所不同的是RASP的程序是存 储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个 寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用 整数进行编码。 2、RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RAM 程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下 T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟， 并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情 况也是类似的。 79.1.3 图灵机89.1.3 图灵机根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。(1)改变有限状态控制器中的状态。(2)清除当前读写头下的方格中原有带符号并写上新的带符号。(3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移 动一个方格(R)或停在当前单元不动(S)。 k带图灵机可形式化地描述为一个7元组(Q，T，I，b，q0，qf)，其中: (1)Q是有限个状态的集合。 (2)T是有限个带符号的集合。 (3)I是输入符号的集合，IT。(4)b是唯一的空白符，bT-I。 (5)q0是初始状态。 (6)qf是终止(或接受)状态。 (7)是移动函数。它是从QTk的某一子集映射到Q (TL，R，S)k的函数。 99.1.3 图灵机图灵机M的时间复杂性T(n)是它处理所有长度为n的 输入所需的最大计算步数。如果对某个长度为n的输入，图 灵机不停机，T(n)对这个n值无定义。 图灵机的空间复杂性S(n)是它处理所有长度为n的 输入时，在k条带上所使用过的方格数的总和。如果某个 读写头无限地向右移动而不停机，S(n)也无定义。 与RAM模型类似，图灵机既可作为语言接受器，也可 作为计算函数的装置。 109.2 P类与NP类问题n一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。n有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。n在图灵机计算模型下，这类问题的计算复杂性至今未知。n为了研究这类问题的计算复杂性，人们提出了另一个能力更强的计算模型，即非确定性图灵机计算模型，简记为 NDTM(Nondeterministic Turing Machine)。n在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。119.2.1 非确定性图灵机非确定性图灵机（ NDTM ）：一个k带的非确定性图 灵机M是一个7元组：(Q，T，I，b，q0，qf)。与确定性 图灵机不同的是非确定性图灵机允许移动函数具有不确定 性，即对于QTk中的每一个值(q;x1,x2,xk)，当它属于 的定义域时，Q(TL，R，S)k中有唯一的一个子集 (q;x1,x2,xk)与之对应。可以在(q;x1,x2,xk)中随 意选定一个值作为它的函数值。在图灵机计算模型中，移动函数是单值的，即对 于QTk中的每一个值，当它属于的定义域时，Q(TL， R，S)k中只有唯一的值与之对应，称这种图灵机为确定性 图灵机，简记为DTM(Deterministic Turing Machine)。 129.2.2 P类与NP类语言P类和NP类语言的定义：P=L|L是一个能在多项式时间内被一台DTM所 接受的语言 NP=L|L是一个能在多项式时间内被一台NDTM 所接受的语言由于一台确定性图灵机可看作是非确定性图 灵机的特例，所以可在多项式时间内被确定性图灵 机接受的语言也可在多项式时间内被非确定性图灵 机接受。故P NP。 139.2.2 P类与NP类语言NP类语言举例无向图的团问题。该问题的输入是一个有n个顶点的无向图G=(V， E)和一个整数k。要求判定图G是否包含一个k顶点 的完全子图(团)，即判定是否存在VV， |V|=k，且对于所有的u，vV，有(u，v)E 。若用邻接矩阵表示图G，用二进制串表示整数k ，则团问题的一个实例可以用长度为 的 二进位串表示。因此，团问题可表示为语言：CLIQUE=w#v|w，v0，1*，以w为邻接矩 阵的图G有一个k顶点的团，其中v是k的二进制表示 。 149.2.2 P类与NP类语言接受该语言CLIQUE的非确定性算法：用非确定性选择指令选 出包含k个顶点的候选顶点子集V，然后确定性地检查该子集是否 是团问题的一个解。算法分为3个阶段： 算法的第一阶段将输入串w#v分解，并计算出n= ，以及 用v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就 拒绝该输入。显而易见，第一阶段可 在时间内完成。在算法的第二阶段中，非确定性地选择V的一个k元子集 VV。 算法的第三阶段是确定性地检查V的团性质。若V是一个 团则接受输入，否则拒绝输入。这显然可以在 时间内完成 。因此，整个算法的时间复杂性为 。非确定性算法在多项式时间内接受语言CLIQUE，故 CLIQUENP。 159.2.3 多项式时间验证VP=L|L*，为一有限字符集，存在一个多项式p 和一个多项式时间验证算法A(X，Y)使得对任意X*， XL当且仅当存在Y*，|Y|p(|X|)且A(X，Y)=1。 多项式时间可验证语言类VP可定义为： 定理9-1：VP=NP。例如(哈密顿回路问题)：一个无向图G含有哈密顿回路吗?无向图G的哈密顿回路是通过G的每个顶点恰好一次的简单 回路。可用语言HAM-CYCLE 定义该问题如下： HAM-CYCLE=G|G含有哈密顿回路 169.3 NP完全问题nPNP。n直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。n大多数的计算机科学家认为NP类中包含了不属于P类的语言，即PNP。nNP完全问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。n目前还没有一个NP完全问题有多项式时间算法。179.3.1 多项式时间变换定义：语言L是NP完全的当且仅当(1)LNP；(2)对于所有LNP有L p L。如果有一个语言L满足上述性质(2)，但不一定满足性质(1)， 则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全 语言类，记为NPC。 设 ， 是2个语言。所谓语言 能在多项式 时间内变换为语言 (简记为 p )是指存在映身f: ， 且f满足： (1)有一个计算f的多项式时间确定性图灵机；(2)对于所有x ，x ，当且仅当f(x) 。 189.3.1 多项式时间变换定理9-2：设L是NP完全的，则(1)LP当且仅当PNP；(2)若Lp ，且 NP，则 是NP完全的。 定理的(2)可用来 证明问题的NP完全 性。但前提是：要 有第一个NP完全问 题L。199. 3.2 一些典型的NP完全问题部分NP完全问题树 20迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解(5)用启发式方法求解 9.4 NP完全问题的近似算法219.4.1 近似算法的性能若一个最优化问题的最优值为c*，求解该问题的一个 近似算法求得的近似最优解相应的目标函数值为c，则将 该近似算法的性能比定义为= 。在通常情况 下，该性能比是问题输入规模n的一个函数(n)，即 (n)。该近似算法的相对误差定义为= 。若对问题 的输入规模n，有一函数(n)使得 (n)，则称 (n)为该近似算法的相对误差界。近似算法的性能比 (n)与相对误差界(n)之间显然有如下关系： (n)(n)-1。 229.4.2 顶点覆盖问题的近似算法问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V 的一个子集VV，使得若(u,v)是G的一条边，则vV 或uV。顶点覆盖V的大小是它所包含的顶点个数 |V|。 VertexSet approxVertexCover ( Graph g ) cset=；e1=g.e；while (e1 != ) 从e1中任取一条边(u,v)；cset=csetu,v；从e1中删去与u和v相关联的所有边；return c Cset用来存储顶点 覆盖中的各顶点。初 始为空，不断从边集 e1中选取一边(u,v) ，将边的端点加入 cset中，并将e1中已 被u和v覆盖的边删去 ，直至cset已覆盖所 有边。即e1为空。 239.4.2 顶点覆盖问题的近似算法图(a)(e)说明 了算法的运行过程 及结果。(e)表示 算法产生的近似最 优顶点覆盖cset， 它由顶点 b,c,d,e,f,g所组 成。(f)是图G的一 个最小顶点覆盖， 它只含有3个顶点 ：b,d和e。 算法approxVertexCover的