各种算法集合讲解章完全理论

算法设计与分析授课教师：王秋芬办公地点：7307Email:第九章NP完全理论目录易解问题和难解问题三种计算模型P类和NP类问题NP完全问题NP完全问题的近似算法教学目标理解易解问题和难解问题了解三种计算模型理解P类与NP类的概念（重点）理解NP完全问题的概念（重点）理解近似算法的近似比及相对误差的概念通过实例掌握部分NP完全问题的近似算法（重点）9.1易解问题和难解问题易解问题：在多项式时间内解决的问题排序（冒泡排序、合并排序、快速排序）会场安排问题单源最短路径问题哈夫曼编码最小生成树二分查找矩阵连乘问题难解问题：在指数时间内解决的问题不可判定问题（太难了，不存在任何算法求解）图灵机停机问题（1936年被证明是不可判定问题）希尔伯特第十问题（整数多项式方程的可解性问题在1970年由苏、美数学家证明Hilbert所期望的一般算法是不存在的，是不可判定问题）非决定的难处理问题旅行商问题汉诺塔为什么把多项式时间复杂性作为易解问题和难解问题的分界线？1．多项式时间与指数时间随问题规模增长的增长率有本质的差别2．计算机性能的提高对多项式时间算法和指数时间算法的影响不同3．多项式时间复杂性忽略了系数，但不影响易解问题和难解问题的划分4．多项式时间复杂性的闭包性5．多项式时间复杂性的分析结果，对于常用的各种计算机形式模型具有不变性。补：三种计算模型（RAM,RASP,TM）随机存取机RAM(RandomAccessMachine)的构造累加器指令计数器程序存储部件内存储器r0r1r2…只读输入带……只写输出带RAM定义了输入带到输出带的映射：（1）计算函数装置（2）语言接受器RAM的复杂性标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。标准二：对数耗费标准对数耗费标准是执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。随机存取机RAM随机存取存储程序机RASP随机存取存储程序机RASP(RandomAccessStoredProgramMachine)1、RASP的结构RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中且能修改自身。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。2、RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。即T(n)与KT(n)图灵机(TuringMachine)图灵机（TuringMachine）的构造图灵机原型……输入带有限状态控制器磁头1.改变有限状态控制器的状态2.清除读写头下方的原有符号，并写上新的符号3.读写头向左或者向右移动一个方格，或不动TM的数学描述Q：有限状态的集合；T：有限个带符号的集合；IT：是输入符号的集合；δ：Q×Tk→Q×(T×{L,R,S})k为转移函数；B：唯一的空白符，b∈T–I；q0：初始状态qf：终止状态。M=(Q,T,I,δ,b,q0,qf)其中：图灵机的语言图灵机的解释语言接受器：当且仅当从指定的初始状态q0开始，经过一系列计算步后，最终进入终止状态qf时，称图灵机接受这个输入符号串。图灵机识别的一个语言：所有这台图灵机能接受的输入符号串的集合计算函数的装置：函数的自变量可编码成一字符串输入到一条输入带上，用一特殊符号＃隔开。若图灵机经过有限步后，在一条指定的带上输出整数y并停机，则可以说图灵机计算出了f(x)=y。图灵机的复杂性时间复杂性T(n)是输入规模为n时所需的最大计算步数。如果图灵机不停机，T(n)对这个n值无定义。空间复杂性S(n)是输入规模为n时，在输入带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)无定义图灵机的变形多道图灵机(输入带上有多个道)。双向图灵机(输入带被视为左右均是无穷的)。多带图灵机(具有多条输入带)。多头图灵机(具有多个磁头)。多维图灵机(输入带是多维的)。不确定的图灵机(有限控制器是不确定的NDTM)。已经证明各类变形图灵机在可计算的能力上等价于原型图灵机。但是在复杂性是有区别的。9.2P类和NP类问题判定问题是仅仅要求回答“yes”或“no”的问题判定问题的重要特性验证比求解容易判定问题→语言的识别问题→计算模型许多问题以自然形式出现时并不是判定问题，但是可以转化为判定问题图的m可着色优化问题旅行商问题0-1背包问题装载问题单源最短路径问题P类问题和NP类问题是针对语言识别问题基于图灵机计算模型给出的。确定性算法与P类问题定义1设A是求解问题Π的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性（Determinism）算法。定义2如果对于某个判定问题Π，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到yes或no的答案，则该判定问题Π是一个P

类（Polynomial）问题。所有易解问题的判定问题都是P类问题如最短路径的判定问题属于P类问题非确定性算法与NP类问题定义3设A是求解问题Π的一个算法，如果算法A以如下猜测并验证的方式工作，就称算法A非确定性算法：（1）猜测阶段：在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。（2）验证阶段：在这个阶段，用一个确定性算法验证：①检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no；②如果串y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。如旅行商问题，最大团问题，图的m可着色判定问题。非确定性算法与NP类问题★定义4如果对于某个判定问题，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个不确定算法，得到是或否的答案，则该判定问题是一个NP类问题。NP类问题是一类能够用不确定算法在多项式时间内求解的判定问题。对于NP类判定问题，它必须存在一个确定算法，能够以多项式时间来检查和验证在猜测阶段所产生的答案。思考：哈密顿回路判定问题是不是NP类问题？汉诺塔问题是不是NP类问题？P类问题和NP类问题的关系（1）P类问题可以用多项式时间的确定性算法来进行判定或求解。（2）NP类问题可以用多项式时间的不确定性算法来进行判定或求解，关键是存在一个确定算法，能够以多项式的时间来验证在猜测阶段所产生的答案。显然，因为DTMNDTM(是一个特例)，所以PNP。是否有P=NP？问题求解难于问题验证，故大多数研究者相信NP类是比P类要大得多的集合，故P≠NP但是，时至今日，还没有任何人能证明：在NP类中有哪个问题不属于P类目前也没有任何人能为NP类中的众多难题里面的哪怕是一个难题，找到一个多项式时间算法。P=NP？这至今仍然是一个悬而未决的问题

9.3NP完全问题（NPC）

NP完全问题是NP类问题的一个子类，是更为复杂的问题。奇特的性质如果一个NP完全问题能在多项式时间内得到解决，那么NP类中的每个问题都可以在多项式时间内得到解决，即P=NP成立！。思考：为什么一个NP完全问题能在多项式时间内解决，NP类中的每一个问题都可以在多项式时间内解决？多项式变换技术（问题的变换）

若问题Q1的求解能够变换成问题Q2的求解且变换的时间为O(τ(n))，则称Q1是τ(n)时间变换为Q2，简记为Q1∝τ(n)Q2，其中n为问题Q1的规模。若Q1∝τ(n)Q2

，当τ(n)为多项式时，称Q1可多项式变换为问题Q2

，记为Q1∝pQ2问题Q1问题Q2

算法AI

输入转换I'O'O

输出转换问题变换的一般过程多项式变换的两个性质：(1)A∝pB且B∈P，则A∈P。(2)若A∝pB且B∝pC，则A∝pC例：配对问题到排序问题的变换排序问题——输入I'是一组整数X=(x1,x2,…,xn)，输出O'是这组整数的一个排列xi1≤xi2≤…≤xin。配对问题——输入I是两组整数X=(x1,x2,…,xn)和Y=(y1,y2,…,yn)，输出O是两组整数的元素配对，即X中的最小值与Y中的最小值配对，X中的次小值与Y中的次小值配对，依此类推。

NPC与NP困难定义5令Q是一个判定问题，如果：（1）Q∈NP，即问题Q属于NP类问题（2）对NP中的所有问题Q’，都有Q’∝pQ则称判定问题Q是一个NP完全问题（NPcompleteproblem），简记为NPC。定义6：对于问题Q，如果任意问题Q’∈NP，都有Q’∝pQ，则称问题Q是NP困难的。P、NP、NPC、NP困难之间的关系如果P≠NP，则P、NP、NPC之间的关系或许如下图所示。NPPNPC若判定问题属于NP完全问题，则相应的最优化问题属于NP难问题。NP难问题若干NP完全的问题Cook在1971年证明了第一个NP完全的问题。Cook定理：布尔表达式的可满足性SAT是NP完全的。基于该问题，逐渐生成了一棵以它为根的NP完全问题树。1979年只证明了300多个NP完全问题目前，已证明的NP完全问题有几千个，且在继续增加。这一事实，增强了人们对P≠NP的猜测。但遗憾的是，这个猜测迄今仍然还只是个猜测。部分NP完全问题树9.4NP完全问题的近似算法近似算法所适应的问题是最优化问题。对于一个规模为n的问题，近似算法应该满足下面两个基本的要求：（1）算法的时间复杂性：要求算法能在n的多项式时间内完成。（2）解的近似程度：算法的近似解应满足一定的精度。衡量精度的标准近似比相对误差NP完全问题的近似解法（1）近似比若一个最优化问题的最优值为C，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的近似比定义为在通常情况下，该近似比是问题输入规模n的一个函数ρ(n)，即（2）相对误差该近似算法的相对误差定义为若对问题的输入规模n，有一函数ε(n)使得则称ε(n)为该近似算法的相对误差界。近似算法的近似比ρ(n)与相对误差界ε(n)之间显然有如下关系：

ε(n)≥ρ(n)-1。1.顶点覆盖问题问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。算法描述VertexSetapproxVertexCover(Graphg){cset=

；e1=g.e；while(e1!=

){从e1中任取一条边(u,v)；cset=cset∪{u,v}；从e1中删去与u和v相关联的所有边；}returnc}顶点覆盖问题的近似算法的性能比为2。图(a)～(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。2.装箱问题问题描述：设有n个物品w1,w2,…,wn和若干个体积均为C的箱子b1,b2,…,bk,…。n个物品的体积分别为s1,s2,…,sn且有si≤C(1≤i≤n)。要求把所有物品分别装入箱子且物品不能分割，使得占用箱子数最少的装箱方案。近似算法：首次适宜法、最适宜法、首次适宜降序法和最适应降序法3.旅行商问题问题描述：给定一个无向带权图G=(V，E)，对每一个边(u，v)E，都有一个非负的常数费用c(u，v)>0，求G中费用最小的哈密尔顿回路。两种类型旅行商问题欧几里德旅行商问题（对于图中的任意3个顶点u、v、w，其费用函数具有三角不等式性质：c(u，v)≤c(u，w)+c(w，v)一般的旅行商问题欧几里德旅行商问题的近似算法算法的设计思想：在图中任选一个顶点u，用Prim