计算机算法设计与分析第9章.ppt
《计算机算法设计与分析第9章.ppt》由会员分享,可在线阅读,更多相关《计算机算法设计与分析第9章.ppt(37页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第9章 NP完全性理论与近似算法1 学习要点学习要点学习要点学习要点 理解理解RAMRAM,RASPRASP和图灵机计算模型和图灵机计算模型 理解非确定性图灵机的概念理解非确定性图灵机的概念 理解理解P P类与类与NPNP类语言的概念类语言的概念 理解理解NPNP完全问题的概念完全问题的概念 理解近似算法的性能比及多项式时间近似格式的概念理解近似算法的性能比及多项式时间近似格式的概念 通过范例学习通过范例学习NPNP完全问题的近似算法完全问题的近似算法(1 1)顶点覆盖问题;)顶点覆盖问题;(2 2)旅行售货员问题;)旅行售货员问题;(3 3)集合覆盖问题;)集合覆盖问题;(4 4)子集和问题
2、。)子集和问题。29.19.1 计算模型计算模型n n在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型,包括定在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型,包括定义该计算模型中所用的基本运算。义该计算模型中所用的基本运算。n n建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。n n3 3个基本计算模型:个基本计算模型:n n随机存取机随机存取机RAM(RandomRAM(Random Access Machine)Access Machine);n n随机存取存储程序
3、机随机存取存储程序机RASP(RandomRASP(Random Access Stored Program Machine)Access Stored Program Machine)n n图灵机图灵机(Turing Machine)(Turing Machine)。n n这这3 3个计算模型在计算能力上是等价的,但在计算速度上是不同的。个计算模型在计算能力上是等价的,但在计算速度上是不同的。39.1.1 随机存取机RAM1、RAMRAM的结构的结构49.1.1 随机存取机RAM2、RAMRAM程序程序 一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释
4、一:把解释一:把RAMRAM程序看成是计算一个函数程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1,x2,xn,并且在输出带的第一个方格上输出一个整数y后停机,那么就说程序P计算了函数f(xf(x1 1,x x2 2,x xn n)=y)=y 解释二:把解释二:把RAMRAM程序当作一个语言接受器。程序当作一个语言接受器。将字符串S=a1a2an放在输入带上。在输入带的第一个方格中放入符号a1,第二个方格中放入符号a2,第n个方格中放入符号an。然后在第n+1个方格中放入0,作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后,在输出带的第一
5、格输出一个1并停机,就说程序P接受字符串S。59.1.1 随机存取机RAM3、RAMRAM程序的耗费标准程序的耗费标准标准一:均匀耗费标准标准一:均匀耗费标准在均匀耗费标准下,每条RAM指令需要一个单位时间;每个寄存器占用一个单位空间。以后除特别注明,RAM程序的复杂性将按照均匀耗费标准衡量。标准二:对数耗费标准标准二:对数耗费标准对数耗费标准是基于这样的假定,即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下,假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数,则 69.1.2 随机存取存储程序机RASP1、RASPRASP的结构的结
6、构RASP的整体结构类似于RAM,所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码,第二个寄存器存放地址。RASP指令用整数进行编码。2、RASPRASP程序程序的复杂性的复杂性不管是在均匀耗费标准下,还是在对数耗费标准下,RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟,并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。79.1.3 图灵机89.1.3 图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号,图灵机的一个计算
7、步可实现下面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
8、(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入,图灵机不停机,T(n)对这个n值无定义。图灵机的空间复杂性S(n)是它处理所有长度为n的输入时,在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机,S(n)也无定义。与RAM模型类似,图灵机既可作为语言接受器,也可作为计算函数的装置。109.2 P类与NP类问题n n一一般般地地说说,将将可可由由多多项项式式时时间间算算法法求求解解的的问问题题看看作作是是易易处处理理的的问问题题,而而将将需需要要超超多多项项式时间才能求解的问题看作是难处理的问题。式时间才能求解的问题看作是难处理的问题。n n有有
9、许许多多问问题题,从从表表面面上上看看似似乎乎并并不不比比排排序序或或图图的的搜搜索索等等问问题题更更困困难难,然然而而至至今今人人们们还还没没有有找找到到解解决决这这些些问问题题的的多多项项式式时时间间算算法法,也也没没有有人人能能够够证证明明这这些些问问题题需需要要超超多多项项式式时间下界。时间下界。n n在图灵机计算模型下,这类问题的计算复杂性至今未知。在图灵机计算模型下,这类问题的计算复杂性至今未知。n n为为了了研研究究这这类类问问题题的的计计算算复复杂杂性性,人人们们提提出出了了另另一一个个能能力力更更强强的的计计算算模模型型,即即非非确确定定性图灵机计算模型,简记为性图灵机计算模
10、型,简记为NDTM(NondeterministicNDTM(Nondeterministic Turing Machine)Turing Machine)。n n在非确定性图灵机计算模型下,许多问题可以在多项式时间内求解。在非确定性图灵机计算模型下,许多问题可以在多项式时间内求解。119.2.1 非确定性图灵机非确定性图灵机非确定性图灵机(NDTMNDTM ):一个k带的非确定性图灵机M是一个7元组:(Q,T,I,b,q0,qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数具有不确定性具有不确定性,即对于QTk中的每一个值(q;x1,x2,xk),当它属于的定义域时,Q(TL,R,S)
11、k中有唯一的一个子集子集(q;x1,x2,xk)与之对应。可以在(q;x1,x2,xk)中随意选定一个值作为它的函数值。在图灵机计算模型中,移动函数是单值的是单值的,即对于QTk中的每一个值,当它属于的定义域时,Q(TL,R,S)k中只有唯一的值与之对应,称这种图灵机为确定性图灵机确定性图灵机,简记为DTMDTM(Deterministic Turing Machine)。129.2.2 P类与NP类语言 P类和NP类语言的定义:P=L|L是一个能在多项式时间内多项式时间内被一台DTMDTM所接受的语言 NP=L|L是一个能在多项式时间多项式时间内被一台NDTMNDTM所接受的语言由于一台确定
12、性图灵机可看作是非确定性图灵机的特例,所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故P P NP NP。139.2.2 P类与NP类语言 NPNP类语言举例类语言举例无向图的团问题无向图的团问题。该问题的输入是一个有n个顶点的无向图G=(V,E)和一个整数k。要求判定图G是否包含一个k顶点的完全子完全子图图(团团),即判定是否存在VV,|V|=k,且对于所有的u,vV,有(u,v)E。若用邻接矩阵表示图G,用二进制串表示整数k,则团问题的一个实例可以用长度为 的二进位串表示。因此,团问题可表示为语言:CLIQUE=w#v|w,v0,1*,以w为邻接矩阵的
13、图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是一个团则接受输入,否则拒绝输入。这显然可以在 时间内完成。因此,整个算法的时间复杂性为 。
14、非确定性算法在多项式时间内接受语言CLIQUE,故CLIQUENP。159.2.3 多项式时间验证 VP=L|L*,为一有限字符集,存在一个多项式p和一个多项式时间验证算法A(X,Y)使得对任意X*,XL当且仅当存在Y*,|Y|p(|X|)且A(X,Y)=1。多项式时间可验证语言类VP可定义为:定理定理9-19-1:VP=NP。例如(哈密顿回路问题哈密顿回路问题):一个无向图G含有哈密顿回路吗?无向图G的哈密顿回路是通过G的每个顶点恰好一次的简单回路。可用语言HAM-CYCLE 定义该问题如下:HAM-CYCLE=G|G含有哈密顿回路 169.3 NP完全问题n nP P NPNP。n n直直
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 算法 设计 分析
限制150内