第十五讲NP完全性理论与近似算法 内容提要 口理解RAM,RASP和图灵机计算模型 口理解非确定性图灵机的概念 口理解P类与NP类语言的概念 口理解NP完全问题的概念 口理解近似算法的性能比及多项式时间近似格式的概念 口通过范例学习NP完全问题的近似算法 (1)顶点覆盖问题(2)旅行售货员问题 (3)集合覆盖问题4)子集和问题
1 内容提要 理解RAM，RASP和图灵机计算模型 理解非确定性图灵机的概念 理解P类与NP类语言的概念 理解NP完全问题的概念 理解近似算法的性能比及多项式时间近似格式的概念 通过范例学习NP完全问题的近似算法 （1）顶点覆盖问题 （2）旅行售货员问题 （3）集合覆盖问题 （4）子集和问题。 第十五讲 NP完全性理论与近似算法
15.1计算模型 ·在进行问题的计算复杂性分析之前,首先必须建立求解问题 所用的计算模型,包括定义该计算模型中所用的基本运算。 目的:为了使问题的计算复杂性分析有一个共同的客观尺度。 ·3个基本计算模型: 随机存取机RAM( Random access machine); 随机存取存储程序机RASP( Random Access stored Program Machine) 图灵机( Turing Machine) √这3个计算模型在计算能力上是等价的,但在计算速度上是不 同的
2 15.1 计算模型 • 在进行问题的计算复杂性分析之前，首先必须建立求解问题 所用的计算模型，包括定义该计算模型中所用的基本运算。 • 目的: 为了使问题的计算复杂性分析有一个共同的客观尺度。 • 3个基本计算模型： – 随机存取机RAM (Random Access Machine)； – 随机存取存储程序机RASP (Random Access Stored Program Machine) – 图灵机(Turing Machine)。 ✓ 这3个计算模型在计算能力上是等价的，但在计算速度上是不 同的
1511随机存取机RAM 1、RAM的结构 只读输入带 累加器 指令计数器程序存储部件 内存储器 y站·「只写输出带
3 15.1.1 随机存取机RAM 1、RAM的结构
1511随机存取机RAM 2、RAM程序 个RAM程序定义了从输入带到输出带的一个映射。可以对 这种映射关系作2种不同的解释。 解释一:把RAM程序看成是计算一个函数 若一个RAM程序P总是从输入带前η个方格中读入n个整数 X1 X ,n,并且在输出带的第一个方格上输出一个整数 后停机,那么就说程序P计算了函数fx1,x2…,xn)=y 解释二:把RAM程序当作一个语言接受器。 将字符串S=a1a2an放在输入带上。在输入带的第一个方 格中放入符号a1,第二个方格中放入符号a2…,第n个方格中 放入符号an。然后在第n+1个方格中放入0,作为输入串的结束标 志符。如果一个RAM程序P读了字符串S及结束标志符0后,在输岀 带的第一格输出—个1并停机,就说程序P接受字符串S。4
4 15.1.1 随机存取机RAM 2、RAM程序 一个RAM程序定义了从输入带到输出带的一个映射。可以对 这种映射关系作2种不同的解释。 解释一：把RAM程序看成是计算一个函数 若一个RAM程序P总是从输入带前n个方格中读入n个整数 x1，x2，…，xn，并且在输出带的第一个方格上输出一个整数y 后停机，那么就说程序P计算了函数f(x1，x2，…，xn )=y 解释二：把RAM程序当作一个语言接受器。 将字符串S=a1 a2…an放在输入带上。在输入带的第一个方 格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中 放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标 志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出 带的第一格输出一个1并停机，就说程序P接受字符串S
151.1随机存取机RAM 3、RAM程序的耗费标准 标准一:均匀耗费标准 在均匀耗费标准下,每条RAM指令需要一个单位时间;每 个寄存器占用一个单位空间。以后除特别注明,RAM程序的复杂 性将按照均匀耗费标ⅶ准衡量。 标准二:对数耗费标准 对数耗费标准是基于这样的假定,即执行一条指令的耗费 与以二进制表示的指令的操作数长度成比例。在RAM计算模型下 假定一个寄存器可存放一个任意大小的整数。因此若设(是整 数所占的二进制位数,则 ogZ l≠
5 15.1.1 随机存取机RAM 3、 RAM程序的耗费标准 标准一：均匀耗费标准 在均匀耗费标准下，每条RAM指令需要一个单位时间；每 个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂 性将按照均匀耗费标准衡量。 标准二：对数耗费标准 对数耗费标准是基于这样的假定，即执行一条指令的耗费 与以二进制表示的指令的操作数长度成比例。在RAM计算模型下， 假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整 数i所占的二进制位数，则 0 0 1 log | | ( ) = = i i i l i
1512随机存取存储程序机RASP 1、RASP的结构 RASP的整体结构类似于RAM,所不同的是RASP的程序是 储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个 寄存器存放操作码的编码,第二个寄存器存放地址。RASP指令用 整数进行编码。 2、RASP程序的复杂性 不管是在均匀耗费标准下,还是在对数耗费标准下,RAM 程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下 T(m)时间内完成的输入-输出映射可在另一个计算模型下模拟, 并在kT(m)时间内完成。其中k是一个常数因子。空间复杂性的情 况也是类似的
6 15.1.2 随机存取存储程序机RASP 1、RASP的结构 RASP的整体结构类似于RAM，所不同的是RASP的程序是存 储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个 寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用 整数进行编码。 2、RASP程序的复杂性 不管是在均匀耗费标准下，还是在对数耗费标准下，RAM 程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下 T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟， 并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情 况也是类似的
1513图灵机 有限状态 控制器 带1 带2□… 带k
7 15.1.3 图灵机
1513图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号,图灵机的一 个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头,向左移动一个方格(L或向右移动一个 方格(R)或停在当前单元不动(S)。 k带图灵机可邢式化地描述为一个7元组(Q,T,I,S,b,q,q,其中 (1)Q是有限个状态的集合。(2)T是有限个带符号的集合 (3)I是输入符号的集合,IT。(4)b是唯一的空白符,b∈T-I (5)q是初始状态。 (6)q是终止(或接受)状态。 (7)6是移动函数。它是从QxT的某一子集映射到Q×(T×{L,R,S})的函数
8 15.1.3 图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一 个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个 方格(R)或停在当前单元不动(S)。 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)δ是移动函数。它是从QTk的某一子集映射到Q (T{L，R，S})k的函数
1513图灵机 与RAM模型类似,图灵机既可作为语言接受器,也可作为 计算函数的装置。 图灵机M的时间复杂性T(n)是它处理所有长度为n的输入 所需的最大计算步数。如果对某个长度为η的输入,图灵机不停 机,T(n)对这个n值无定义。 图灵机的空间复杂性S(n是它处理所有长度为n的输入时, 在k条带上所使用过的方格数的总和。如果某个读写头无限地向 右移动而不停机,S(n)也无定义
9 15.1.3 图灵机 图灵机M的时间复杂性T(n)是它处理所有长度为n的输入 所需的最大计算步数。如果对某个长度为n的输入，图灵机不停 机，T(n)对这个n值无定义。 图灵机的空间复杂性S(n)是它处理所有长度为n的输入时， 在k条带上所使用过的方格数的总和。如果某个读写头无限地向 右移动而不停机，S(n)也无定义。 与RAM模型类似，图灵机既可作为语言接受器，也可作为 计算函数的装置
152P类与NP类问题 ·可由多项式时间算法求解的问题→易处理的问题 需要超多项式时间才能求解的问题→难处理的问题。 有许多问题,从表面上看似乎并不比排序或图的搜索等问题更 困难,然而至今人们还没有找到解决这些问题的多项式时间算 法,也没有人能够证明这些问题需要超多项式时间下界 在图灵机计算模型下,这类问题的计算复杂性至今未知 为了研究这类问题的计算复杂性,人们提出了另一个能力更强 的计算模型,即非确定性图灵机计算模型,简记为NDTM (Nondeterministic Turing Machine) ·在非确定性图灵机计算模型下,许多问题可以在多项式时间内 求解
10 15.2 P类与NP类问题 • 可由多项式时间算法求解的问题→易处理的问题， 需要超多项式时间才能求解的问题→难处理的问题。 • 有许多问题，从表面上看似乎并不比排序或图的搜索等问题更 困难，然而至今人们还没有找到解决这些问题的多项式时间算 法，也没有人能够证明这些问题需要超多项式时间下界。 • 在图灵机计算模型下，这类问题的计算复杂性至今未知。 • 为了研究这类问题的计算复杂性，人们提出了另一个能力更强 的计算模型，即非确定性图灵机计算模型，简记为NDTM (Nondeterministic Turing Machine)。 • 在非确定性图灵机计算模型下，许多问题可以在多项式时间内 求解