计算机算法设计与分析 第9章 np完全性理论与近似算法

《计算机算法设计与分析 第9章 np完全性理论与近似算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章NP完全性理论与近似算法1学习要点理解RAM，RASP和图灵机计算模型理解非确定性图灵机的概念理解P类与NP类语言的概念理解NP完全问题的概念理解近似算法的性能比及多项式时间近似格式的概念通过范例学习NP完全问题的近似算法（1）顶点覆盖问题；（2）旅行售货员问题；（3）集合覆盖问题；（4）子集和问题。29.1计算模型在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。3个基本计算模型：随机存取机RAM(RandomAccessM

2、achine)；随机存取存储程序机RASP(RandomAccessStoredProgramMachine)图灵机(TuringMachine)。这3个计算模型在计算能力上是等价的，但在计算速度上是不同的。39.1.1随机存取机RAM1、RAM的结构49.1.1随机存取机RAM2、RAM程序一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把RAM程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，…，xn，并且在输出带的第一个方格上输出一个整数y后停机，那么就说程序P计算

3、了函数f(x1，x2，…，xn)=y解释二：把RAM程序当作一个语言接受器。将字符串S=a1a2…an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。59.1.1随机存取机RAM3、RAM程序的耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂性将按

4、照均匀耗费标准衡量。标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数，则69.1.2随机存取存储程序机RASP1、RASP的结构RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行编码。2、RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RA

5、M程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。79.1.3图灵机89.1.3图灵机根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。(1)改变有限状态控制器中的状态。(2)清除当前读写头下的方格中原有带符号并写上新的带符号。(3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。k带图灵机可形式化地描

6、述为一个7元组(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限个状态的集合。(2)T是有限个带符号的集合。(3)I是输入符号的集合，IT。(4)b是唯一的空白符，b∈T-I。(5)q0是初始状态。(6)qf是终止(或接受)状态。(7)δ是移动函数。它是从QTk的某一子集映射到Q(T{L，R，S})k的函数。99.1.3图灵机图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的

7、方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。109.2P类与NP类问题一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。在图灵机计算模型下，这类问题的计算复杂性至今未知。为了研究这类问题的计算复杂性，人们提出了另一个能力更强的计算模型，即非确

8、定性图灵机计算模型，简记为NDTM(NondeterministicTuringMachine