第9章 NP完全理论.ppt

《第9章 NP完全理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章NP完全理论第九章NP完全理论目录易解问题和难解问题P类和NP类问题NP完全问题NP完全问题的近似算法教学目标理解易解问题和难解问题理解P类与NP类的概念理解NP完全问题的概念理解近似算法的性能比及相对误差的概念通过实例理解NP完全问题的近似算法在计算机算法理论中，最深刻的问题之一是：从计算的观点来看，我们要解决的问题的内在复杂性如何，它是“易”计算的还是“难”计算的。如果我们知道一个问题的计算时间下界，我们就可以较正确地评价解决该问题的各种算法的效率，进而确定对已有算法还有多少改进的余地

2、。在许多情况下，要确定一个问题的内在计算复杂性是很困难的。问题的计算复杂性可以通过解决问题所需计算量的多少来度量。如何区分一个问题是“易”还是“难”呢？人们通常将可以在多项式时间内解决的问题看作是“易”解问题，而将需要指数函数时间解决的问题看作是“难”问题。这里所说的多项式时间和指数函数时间是针对问题的规模而言的，即解决问题所需的时间是问题规模的多项式还是指数函数。为什么科学家要用多项式函数作为标准定义问题的难易程度？（1）为有过多时间要求的问题提供一个好的标准；（2）多项式函数在加、乘运算下是

3、自封闭的，并且在那些有用的分析算法复杂性函数类中，多项式函数是最小函数类；（3）多项式时间复杂性的分析结果，对于常用的各种计算机模型，具有不变性。存在多项式时间算法的问题称为易解问题，需要在指数时间内解决的问题称为难解问题。计算模型在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算，其目的是为了使问题的计算复杂性分析有一个共同的客观尺度。三种主要的计算模型：随机存取机RAM(RandomAccessMachine)随机存取存储程序机RASP(R

4、andomAccessStoredProgramMachine)图灵机(TuringMachine)这三个计算模型在计算能力上是等价的，但计算速度不同。随机存取机RAM随机存取机所描述的形式计算机是一台单累加器计算机。它不允许程序修改其自身。其结构如下：随机存取机RAM随机存取机：由只读输入带、只写输出带、程序存储部件、内存储器、指令计数器组成。注：输入带、输出带可无限长；内存储器由一系列寄存器组成，并且可存放任意大小的整数，寄存器个数无限。随机存取机RAMRAM的程序不是存放在内存储器中，程序

5、是一个带标号的指令序列。RAM设有：算术运算指令、输入输出指令、存取指令、转移指令。RAM的寻址方式：直接寻址和间接寻址。RAM的指令由操作码和操作数组成。操作数有三种形式:=i(直接数),i(直接地址),*i(间接地址)RAM的基本指令集(略)随机存取机RAM2.RAM程序一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把RAM程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，…，xn，并且在输出带的第一个方格上

6、输出一个整数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。随机存取机RAM3.RAM程序的耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指

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

8、的编码，第二个寄存器存放地址。RASP指令用整数进行编码。RASP指令集中不需要间接寻址，其余指令与RAM指令集一样。随机存取存储程序机RASP2.RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。图灵机1.多带图灵机图灵机1.多带图灵机根据有限状态控制器的当前状态及每个读写头读到