山东师范大学计算机实验教学中心精品实验课程>>算法设计与分析第九章 NP完全性理论与近似算法

算法设计与分析

第九章 NP完全性理论与近似算法

任课教师：徐连诚

关于NP完全性理论

理解RAM，RASP和图灵机计算模型
理解非确定性图灵机的概念
理解P类与NP类语言的概念
理解NP完全问题的概念

关于近似算法

理解近似算法的性能比及多项式时间近似格式的概念
通过范例学习NP完全问题的近似算法
- 顶点覆盖问题；
- 旅行售货员问题；
- 集合覆盖问题；
- 子集和问题。

计算模型

在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。
建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。
3个基本计算模型：
- 随机存取机RAM(Random Access Machine)
- 随机存取存储程序机RASP(Random Access Stored Program Machine)
- 图灵机(Turing Machine)
- 这3个计算模型在计算能力上是等价的，但在计算速度上是不同的。

随机存取机RAM

RAM的结构

RAM程序

一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。
解释一：把RAM程序看成是计算一个函数。
- 若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，…，xn
- 并且在输出带的第一个方格上输出一个整数y后停机
- 那么就说程序P计算了函数f(x1，x2，…，xn)=y
解释二：把RAM程序当作一个语言接受器。
- 将字符串S=a1a2…an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中放入符号an。
- 然后在第n+1个方格中放入0，作为输入串的结束标志符。
- 如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。

RAM程序的耗费标准

标准一：均匀耗费标准
- 在均匀耗费标准下，每条RAM指令需要一个单位时间
- 每个寄存器占用一个单位空间
- 以后除特别注明，RAM程序的复杂性将按照均匀耗费标准衡量
标准二：对数耗费标准
- 对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例
- 在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数
- 因此若设l(i)是整数i所占的二进制位数，则

随机存取存储程序机RASP

RASP的结构
- RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的
- 每条RASP指令占据2个连续的寄存器
- 第一个寄存器存放操作码的编码，第二个寄存器存放地址
- RASP指令用整数进行编码

RASP程序的复杂性
- 不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子
- 在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成
- 其中k是一个常数因子。空间复杂性的情况也是类似的

图灵机(2)

根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部
- (1)改变有限状态控制器中的状态
- (2)清除当前读写头下的方格中原有带符号并写上新的带符号
- (3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)

图灵机(3)

k带图灵机可形式化地描述为一个7元组(Q，T，I，δ，b，q0，qf)，其中:
- (1)Q是有限个状态的集合
- (2)T是有限个带符号的集合
- (3)I是输入符号的集合，IT
- (4)b是唯一的空白符，b∈T-I
- (5)q0是初始状态
- (6)qf是终止(或接受)状态
- (7)δ是移动函数。它是从的某一子集映射到的函数

图灵机(4)

与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。
图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。
图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。

P类与NP类问题

一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。
有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。
在图灵机计算模型下，这类问题的计算复杂性至今未知。
为了研究这类问题的计算复杂性，人们提出了另一个能力更强的计算模型，即非确定性图灵机计算模型，简记为NDTM(Nondeterministic Turing Machine)。
在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。

非确定性图灵机

在图灵机计算模型中，移动函数δ是单值的，即对于的每一个值，当它属于δ的定义域时，中只有唯一的值与之对应，称这种图灵机为确定性图灵机，简记为DTM(Deterministic Turing Machine)。
非确定性图灵机（ NDTM ）：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，δ，b，q0，qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数δ具有不确定性，即对于中的每一个值(q;x1,x2,…,xk)，当它属于δ的定义域时，中有唯一的一个子集δ(q;x1,x2,…,xk)与之对应。可以在δ(q;x1,x2,…,xk)中随意选定一个值作为它的函数值。

P类与NP类语言

P类和NP类语言的定义：
- P={L|L是一个能在多项式时间内被一台DTM所接受的语言}
- NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}
由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故PNP。

NP类语言举例——无向图的团问题(1)

该问题的输入是一个有n个顶点的无向图G=(V，E)和一个整数k。要求判定图G是否包含一个k顶点的完全子图(团)，即判定是否存在V’V，|V’|=k，且对于所有的u，v∈V’，有(u，v)∈E。
若用邻接矩阵表示图G，用二进制串表示整数k，则团问题的一个实例可以用长度为的二进位串表示。
因此，团问题可表示为语言：CLIQUE={w#v|w，v∈{0，1}*，以w为邻接矩阵的图G有一个k顶点的团，其中v是k的二进制表示。

NP类语言举例——无向图的团问题(2)

接受该语言CLIQUE的非确定性算法：用非确定性选择指令选出包含k个顶点的候选顶点子集V，然后确定性地检查该子集是否是团问题的一个解。
算法分为3个阶段：
- 算法的第一阶段将输入串w#v分解，并计算出n=，以及用v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就拒绝该输入。显而易见，第一阶段可在时间内完成。
- 在算法的第二阶段中，非确定性地选择V的一个k元子集V’V。
- 算法的第三阶段是确定性地检查V’的团性质。若V’是一个团则接受输入，否则拒绝输入。这显然可以在时间内完成。因此，整个算法的时间复杂性为。
非确定性算法在多项式时间内接受语言CLIQUE，故CLIQUE∈NP。

多项式时间验证

多项式时间可验证语言类VP可定义为：
- VP={L|L∈∑*，∑为一有限字符集，存在一个多项式p和一个多项式时间验证算法A(X，Y)使得对任意X∈∑*，X∈L当且仅当存在Y∈∑*，|Y|≤p(|X|)且A(X，Y)=1}。
定理9-1：VP=NP。
- 例如(哈密顿回路问题)：一个无向图G含有哈密顿回路吗？无向图G的哈密顿回路是通过G的每个顶点恰好一次的简单回路。可用语言HAM-CYCLE 定义该问题如下：HAM-CYCLE={G|G含有哈密顿回路}

NP完全问题

PNP。
直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。
大多数的计算机科学家认为NP类中包含了不属于P类的语言，即P≠NP。
NP完全问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。
目前还没有一个NP完全问题有多项式时间算法。

多项式时间变换(1)

设，是2个语言。所谓语言能在多项式时间内变换为语言( 简记为∝p) 是指存在映射f:，且f满足：
- (1)有一个计算f的多项式时间确定性图灵机
- (2)对于所有x∈，x∈，当且仅当f(x)∈
定义：语言L是NP完全的当且仅当
- (1)L∈NP
- (2)对于所有L’∈NP有L’ ∝p L
如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全语言类，记为NPC。

多项式时间变换(2)

定理9-2：设L是NP完全的，则
- (1)L∈P当且仅当P＝NP；
- (2)若L∝p，且∈NP，则是NP完全的。
定理的(2)可用来证明问题的NP完全性。但前提是：要有第一个NP完全问题。

一些典型的NP完全问题

部分NP完全问题树

NP完全问题的近似算法

迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略：
- (1)只对问题的特殊实例求解
- (2)用动态规划法或分支限界法求解
- (3)用概率算法求解
- (4)只求近似解
- (5)用启发式方法求解

近似算法的性能

若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为
- 在通常情况下，该性能比是问题输入规模n的一个函数ρ(n)，即
- 该近似算法的相对误差定义为
若对问题的输入规模n，有一函数ε(n)使得则称ε(n)为该近似算法的相对误差界。近似算法的性能比ρ(n)与相对误差界ε(n)之间显然有如下关系：ε(n)≤ρ(n)-1。

顶点覆盖问题的近似算法

问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’V，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。

算法描述

VertexSet approxVertexCover ( Graph g )
{
     cset=；
     e1=g.e；
     while (e1 !=)
     {
         从e1中任取一条边(u,v)；
         cset=cset∪{u,v}；
         从e1中删去与u和v相关联的所有边；
      }
      return c
 }

cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边，即e1为空。

顶点覆盖近似算法示例

算法approxVertexCover的性能比为2。

旅行售货员问题近似算法

问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。
旅行售货员问题的一些特殊性质：
- 比如，费用函数c往往具有三角不等式性质，即对任意的3个顶点u,v,w∈V，有c(u,w)≤c(u,v)+c(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质。

满足三角不等式的旅行售货员问题(1)

对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。

void approxTSP (Graph g)
{
    1)选择g的任一顶点r；
    2)用Prim算法找出带权图g的一棵以r为根的最小生成树T；
    3)前序遍历树T得到的顶点表L；
    4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；
}

当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。

示例

(b)表示找到的最小生成树I (c)表示对T作前序遍历的次序

(d)表示L产生的哈密顿回路H (e)是G的一个最小费用旅行售货员回路

一般的旅行售货员问题

在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NP。
换句话说，若P≠NP，则对任意常数ρ>1，不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法。

集合覆盖问题的近似算法

问题描述：集合覆盖问题时一个最优化问题，其原型是多资源选择问题。集合覆盖问题可以看作是图的顶点覆盖问题的推广，它也是一个NP难问题。
集合覆盖问题的一个实例〈X,F〉由一个有限集X及X的一个子集族F组成。
- 子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X=
- 对于F中的一个子集CF，若C中的X的子集覆盖了X，即X=则称C覆盖了X。
- 集合覆盖问题就是要找出F中覆盖X的最小子集C*，使得|C*|=min{|C||CF且C覆盖X}

集合覆盖问题示例(1)

集合覆盖问题示例(2)

贪心算法

set greedySetCover (X,F)
{
U=X；
C=；
while (U !=)
{
选择F中使|S∩U|最大的子集S；
U=U-S；
C=C∪{S}；
}
return C；
}

算法的循环体最多执行min{|X|,|F|}次，而循环体内的计算俨然可在O(|X||F|)时间内完成。因此，算法的计算时间为O(|X||F|min{|X|,|F|})。由此即知，该算法是一个多项式时间算法。

子集和问题的近似算法

问题描述：
- 设子集和问题的一个实例为〈S,t〉。其中，S={x1，x2，…，xn}是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集S1，使得

子集和问题的指数时间算法(2)

int exactSubsetSum (S,t)
{
int n=|S|；
L[0]={0}；
for (int i=1；i<=n；i++)
{
L[i]=mergeLists(L[i-1],L[i-1]+S[i])；
删去L[i]中超过t的元素；
}
return max(L[n])；
}

算法以集合S={x1,x2,...,xn}和目标值t作为输入。算法中用到将2个有序表L1和L2合并成为一个新的有序表的算法mergeLists(L1,L2)。

子集和问题的完全多项式时间近似格式

基于算法exactSubsetSum，通过对表L[i]作适当的修整建立一个子集和问题的完全多项式时间近似格式。
在对表L[i]进行修整时，用到一个修整参数δ，0＜δ＜1。用参数δ修整一个表L是指从L中删去尽可能多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-δ)y≤z≤y。可以将z看作是被删去元素y在修整后的新表L1中的代表。
举例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,29〉，则用δ对L进行修整后得到L1=〈10，12，15，20，23，29〉。其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。

算法描述

对有序表L修整算法：

List trim(L,δ)
{
int m=|L|；
L1=〈L[1]〉；
int last=L[1]；
for (int i=2；i<=m；i++)
if (last<(1-δ)*L[i])
{
将L[i]加入表L1的尾部；
last=L[i]；
}
return L1；
}

算法描述(2)

子集和问题近似格式：

int approxSubsetSum(S,t,ε)
{
n=|S|；
L[0]=〈0〉；
for (int i=1；i<=n；i++)
{
L[i]=Merge-Lists(L[i-1], L[i-1]+S[i])；
L[i]=Trim(L[i],ε/n)；
删去L[i]中超过t的元素；
}
return max(L[n])；
}

示例

S=<104, 102, 201, 101>，t=308，i=1, 2, ..., n。
由算法确定的修整参数δ是ε/4=0.05。
初始时，L[0]=<0>。计算L[i]的3阶段结果：
- L[1]=<0, 104>
- L[1]=<0, 104>
- L[1]=<0, 104>
- L[2]=<0, 102, 104, 206>
- L[2]=<0, 102, 206>
- L[2]=<0, 102, 206>

示例(2)

初始时，L[0]=<0>。计算L[i]的3阶段结果(续)：
- L[3]=<0, 102, 201, 206, 303, 407>
- L[3]=<0, 102, 201, 303, 407>
- L[3]=<0, 102, 201, 303>
- L[4]=<0, 101, 102, 201, 203, 302, 303, 404>
- L[4]=<0, 101, 201, 302, 404>
- L[4]=<0, 101, 201, 302>
算法最后返回z=302最为近似解答。容易看出该例的最优解为104+102+101=307，误差≤2%。

算法设计与分析

第九章 NP完全性理论与近似算法

任课教师：徐连诚

关于NP完全性理论

关于近似算法

计算模型

随机存取机RAM

RAM程序

RAM程序的耗费标准

随机存取存储程序机RASP

图灵机(1)

图灵机(2)

图灵机(3)

图灵机(4)

P类与NP类问题

非确定性图灵机

P类与NP类语言

NP类语言举例——无向图的团问题(1)

NP类语言举例——无向图的团问题(2)

多项式时间验证

NP完全问题

多项式时间变换(1)

多项式时间变换(2)

一些典型的NP完全问题

NP完全问题的近似算法

近似算法的性能

顶点覆盖问题的近似算法

算法描述

顶点覆盖近似算法示例

旅行售货员问题近似算法

满足三角不等式的旅行售货员问题(1)

示例

一般的旅行售货员问题

集合覆盖问题的近似算法

集合覆盖问题示例(1)

集合覆盖问题示例(2)

子集和问题的近似算法

子集和问题的指数时间算法(2)

子集和问题的完全多项式时间近似格式

算法描述

算法描述(2)

示例

示例(2)