NP完全性理论与近似算法.ppt

NP完全性理论与近似算法.PPT第9章 NP完全性理论与近似算法
NP完全性理论与近似算法算法分析与设计Analysis and Design puter Algorithms
李纲 2008 宁波大学
信息科学与工程学院
学习要点
理解RAM,RASP和图灵机计算模型
理解非确定性图灵机的概念
理解P类与NP类语言的概念
理解NP完全问题的概念
理解近似算法的性能比及多项式时间近似格式的概念
通过范例学习NP完全问题的近似算法
(1)顶点覆盖问题;
(2)旅行售货员问题;
(3)集合覆盖问题;
(4)子集和问题。
计算模型
在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型,包括定义该计算模型中所用的基本运算。
建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。
3个基本计算模型:
随机存取机RAM(Random Access Machine);
随机存取存储程序机RASP(Random Access Stored Program Machine)
图灵机(Turing Machine)。
这3个计算模型在计算能力上是等价的,但在计算速度上是不同的。
随机存取机RAM
1、RAM的结构
随机存取机RAM
所有的计算在累加器r0中
RAM有直接寻址和间接寻址两种方式
每条RAM指令由操作码和操作数两部分组成,其中操作数有以下3种:
(1)=i(直接数型)
(2)i(直接地址,寄存器ri的内容)
(3)*i(间接地址)
RAM对无定义的指令做停机处理
随机存取机RAM
2、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
3、 RAM程序的耗费标准
标准一:均匀耗费标准
在均匀耗费标准下,每条RAM指令需要一个单位时间;每个寄存器占用一个单位空间。以后除特别注明,RAM程序的复杂性将按照均匀耗费标准衡量。
标准二:对数耗费标准 P345耗费表
对数耗费标准是基于这样的假定,即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下,假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数,则
随机存取存储程序机RASP
1、RASP的结构
RASP的整体结构类似于RAM,所不同的是RASP的程序是存储在寄存器中的(程序能修改自身)。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码,第二个寄存器存放地址。RASP指令用整数进行编码。
2、RASP程序的复杂性
不管是在均匀耗费标准下,还是在对数耗费标准下,RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟,并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。
图灵机
图灵机
根据有限状态控制器的当前状态及每个读写头读到的带符号,图灵机的一个计算步可实现下面3个操作之一或全部。
(1)改变有限状态控制器中的状态。
(2)清除当前读写头下的方格中原有带符号并写上新的带符号。
(3)独立地将任何一个或所有读写头,向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。
k带图灵机可形式化地描述为一个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的函数。