计算机算法分析与设计第9章.ppt

1、1,第9章 NP完全性理论与近似算法,2,学习要点 理解RAM，RASP和图灵机计算模型 理解非确定性图灵机的概念 理解P类与NP类语言的概念 理解NP完全问题的概念 理解近似算法的性能比及多项式时间近似格式的概念 通过范例学习NP完全问题的近似算法 （1）顶点覆盖问题； （2）旅行售货员问题； （3）集合覆盖问题； （4）子集和问题。,3,在计算机算法理论中，最深刻的问题之一是： 从计算的观点来看，要解决的问题的内在复杂性如何，它是“易”计算的还是“难”计算的。,若知道了一个问题的计算时间下界，就可以较正确地评价解决该问题的各种算法的效率，进而确定对已有算法还有多少改进的余地。,在许多情况下

2、，要确定一个问题的内在复杂性是相当困难的。但问题的计算复杂性可以通过解决该问题所需计算量的多少来度量。,4,如何区分一个问题是“难”还是“易”？,人们通常将在多项式时间内解决的问题看作是“易”解决的问题，而将需要指数时间解决的问题看作是“难”问题。（这里是针对问题的规模而言）,对于实际遇到的很多问题，人们至今未确切地了解其内在的计算复杂性。,只能用分类的方法, 将计算复杂性大致相同的问题, 归类研究。,5,计算模型,在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。 建立计算模型的目的, 是为了使问题的计算复杂性分析, 有一个共同的客观尺度

3、。 3个基本计算模型： 随机存取机RAM(Random Access Machine)； 随机存取存储程序机RASP(Random Access Stored Program Machine) 图灵机(Turing Machine)。 这3个计算模型在计算能力上是等价的，但在计算速度上是不同的。,6,NP完全问题,7,新千年的七个数学问题,1900年在巴黎召开的“国际数学家大会”上, Hilbert提出著名的23个数学问题, 深刻影响(和推动)了20世纪的数学发展. 在新千年来临之际, 2000年5月24日，就在希尔伯特提出23个世纪难题之后的整整一百年后, 在巴黎又宣布了新的7个数学问题.

4、这次是由“柯莱数学研究所” (/,Clay Math. Inst., Cambridge, MA, USA,)宣布, 为7个问题中的任一个解答设立一百万美元奖金.,8,在这7个问题中，排在第一位的是P与NP问题。即 P问题即是可被“运行多项式时间的”一个算法解决的问题 (多项式时间: 运行时间最多是输入量的多项式函数). NP问题即是有一个“可用多项式时间检验的”解答的问题. P = NP ?,9,2黎曼假设(RiemannHypothesis):黎曼Zeta函数的非平凡零点的实部都是1/2.3庞加莱猜想(PoincareConjecture):任意

5、闭单连通3-流型同胚于3-球.4霍奇猜想(HodgeConjecture):在非奇异复射影代数簇上,任一霍奇类是代数闭链类的有理线性组合.5BSD猜想(BirchandSwinnerton-DyerConjecture) 6奈维尔斯托克斯方程(Navier-StokesEquatoins) 7杨米尔斯理论(Yang-MillsTheory):证明诸量子杨米尔斯场存在而且有一个大缺口.,10,背 景,计算机处理能力受限于内存大小与中央处理器速度等，导致算法本身的数据结构对于其执行效率有很大的影响。 在分析算法时，主要以时间复杂度与空间复杂度两者为分析依据。 随着计算器发展迅速，算法的空间复杂度已

6、经不是那么重要的一件事，目前分析主要是在时间复杂度方面。,P问题：线性时间或者多项式时间内能够解决的问题。如能够在O(n)、O(nlog2n)、O(nk)数量级内解决的问题。它们都是以多项式时间为上界。 NP问题：不能在多项式时间内解决的问题。如计算时间数量级为O(n!)、O(2n)。 不可解问题：“图灵停机问题” 任何计算机耗费任意时间不能解决。逻辑学家阿朗索丘奇证明了所谓的判定问题也是不可解的：判定一个已知的语句是否表达一个算术的真值，决不可能有一般的过程。换句话说，能够输出所有算术真值的计算机是不存在的 。,P与NP问题,图灵、图灵奖及图灵奖获得者简介,1912年6月23日，出生于英国伦

7、敦。 1931年-1934年，在英国剑桥大学国王学院学习。 1932年-1935年，研究量子力学、概率论和逻辑学。 1935年，由于独立发现中心极限定理，获Smith奖，年仅23岁被选为剑桥大学国王学院院士。 1936年，研究可计算理论，提出“图灵机”的构想。,1936年-1938年，主要在美国普林斯顿大学做博士研究，涉及逻辑学、代数和数论等领域。 1938年-1939年，返回剑桥从事研究工作，并应邀加入英国政府破译二战德军密码的工作。 1940年-1942年，作为主要参与者和贡献者之一，在破译纳粹德国通讯密码的工作上成就杰出，并成功破译了德军U-潜艇密码，为扭转二战盟军的大西洋战场战局立下汗

8、马功劳。,1943年-1945年，担任英美密码破译部门的总顾问。 1945年,应邀在英国国家物理实验室从事计算机理论研究工作。 1946年，图灵在计算机和程序设计原始理论上的构思和成果，已经确定了他的理论开创者的地位。由于图灵的杰出贡献，他被英国皇室授予OBE爵士勋衔。 1947年-1948年，主要从事计算机程序理论的研究，并同时在神经网络和人工智能领域做出开创性的理论研究。,1948年，应邀加入英国曼彻斯特大学从事研究工作，担任曼彻斯特大学计算实验室副主任。 1949年，成为世上第一位把计算机实际用于数学研究的科学家。 1950年，发表论文“计算机器与智能”，为后来的人工智能科学提供了开创性

9、的构思。提出著名的“图灵测试”理论。,1951年，提出生物增长的非线性理论研究。年仅39岁即被选为英国皇家学会会员。 1953年-1954年，继续在生物和物理学等方面的研究。 1954年6月7日，42岁，图灵死于家中的床上，床头有一个咬了一半的、在氰化物溶液中浸泡过的苹果，警方调查结论是自杀。 一代英灵，就此过早离去，成为人类科学史上的一大遗憾。,Turing Award,被公认为是计算机科学界的诺贝尔奖最高奖项.奖励在计算机科学技术研究中做出了创造性贡献的杰出科学家. 1966年开始由ACM设立（美国计算机协会，1947年成立，与IEEE Computer Society并列为计算机界最著名

10、的两大国际学术组织），用Turing的名字来命名该奖，以纪念这位伟人对于计算机科学技术发展的功绩。 通常每年1名获奖者, 偶尔2名(同方向)，02年3名(RSA,Rivest,Shamir,Adelman). 虽未明确规定, 但授奖较偏重于计算机科学理论和软件技术方面作出贡献的科学家. 唯一华人获奖者是姚期智(Andrew Yao, 美籍, 2000年),1972，E.W.Dijkstra（美Burroughs公司）：求最短路径的Dijkstra算法，PV操作，结构化程序设计，“goto有害”等 1974，D.E.Knuth（stanford）：算法最早的奠基人之一，现代“算法”与“数据结构”

11、等名词及内涵的提出，KMP算法，多卷算法巨著的作者，LR(k)文法，Tex编辑器等。 1976，M.O.Rabin（以色列人）x1,x2,xk)，当它属于的定义域时，Q(TL，R，S)k中有惟一子集(q;x1,x2,xk)与之对应。可以在(q;x1,x2,xk)中随意选定一个值作为它的函数值。,非确定性图灵机,45,P类与NP类语言,P=L|L是一个能在多项式时间内被一台DTM所接受的语言 NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言,由于一台确定性图灵机,可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言,也可在多项式时间内被非确定性图灵机接受。故P

12、NP。,46,多项式时间变换,设 ， 是2个语言。所谓语言 能在多项式时间内变换为语言 (简记为 p )是指存在映身f: ，且f满足： (1)有一个计算f的多项式时间确定性图灵机； (2)对于所有x ，x ，当且仅当f(x) 。,47,语言L是NP完全的当且仅当 (1)LNP； (2)对于所有LNP有L p L。 如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NP难的。 所有NP完全语言构成的语言类, 称为NP完全语言类，记为NPC。,48,PNP？ P属于NP，NP属于P？ NPC性质：任意一个NPC能在多项式时间解决，则所有的NP问题都多项式可解。即PNP。,49,Cook定理（第一个NP完全问题）,(Cook定理)：布尔表达式的可满足性问题是NP完全的。,0/1 knapsack Traveling salesperson (TSP) Graph coloring Sum of subsets Multicasting (多播) Hamiltonian cycle Maximum clique Multiple sequence alignment (MS