《计算机算法分析与设计 第9章》由会员分享，可在线阅读，更多相关《计算机算法分析与设计 第9章（53页珍藏版）》请在金锄头文库上搜索。
1、第9章 NP完全性理论与近似算法1学习要点理解RAM，RASP和图灵机计算模型理解非确定性图灵机的概念理解P类与NP类语言的概念 理解NP完全问题的概念理解近似算法的性能比及多项式时间近似格式的概念通过范例学习NP完全问题的近似算法（1）顶点覆盖问题；（2）旅行售货员问题；（3）集合覆盖问题；（4）子集和问题。2n在计算机算法理论中，最深刻的问题之一是：n从计算的观点来看，要解决的问题的内在复杂性如何，它是“易” 计算的还是“难”计算的。n若知道了一个问题的计算时间下界，就可以较正确地 评价解决该问题的各种算法的效率，进而确定对已有算 法还有多少改进的余地。n在许多情况下，要确定一个问题的内在
2、复杂性是相当 困难的。但问题的计算复杂性可以通过解决该问题所需 计算量的多少来度量。3 如何区分一个问题是“难”还是“易”？ 人们通常将在多项式时间内解决的问题看作是“易”解决 的问题，而将需要指数时间解决的问题看作是“难”问题 。（这里是针对问题的规模而言） 对于实际遇到的很多问题，人们至今未确切地了解其 内在的计算复杂性。 只能用分类的方法, 将计算复杂性大致相同的问题, 归 类研究。4计算模型n在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。n建立计算模型的目的, 是为了使问题的计算复杂性分析, 有一个共同的客观尺度。n3个基本计算
3、模型：n随机存取机RAM(Random Access Machine)；n随机存取存储程序机RASP(Random Access Stored Program Machine)n图灵机(Turing Machine)。n这3个计算模型在计算能力上是等价的，但在计算速度上是不同的。56新千年的七个数学问题1900年在巴黎召开的“国际数学家大会”上 , Hilbert提出著名的23个数学问题, 深刻影响 (和推动)了20世纪的数学发展. 在新千年来临之际, 2000年5月24日，就在 希尔伯特提出23个世纪难题之后的整整一百年 后, 在巴黎又宣布了新的7个数学问题. 这次是 由“柯莱数学研究所”
4、(http:/www.claymath.org/,Clay Math. Inst., Cambridge, MA, USA,)宣布, 为7个问 题中的任一个解答设立一百万美元奖金. 7n在这7个问题中，排在第一位的 是P与NP问题。即uP问题即是可被“运行多项式 时间的”一个算法解决的问题 ( 多项式时间: 运行时间最多是输 入量的多项式函数).uNP问题即是有一个“可用多项 式时间检验的”解答的问题. uP = NP ? 8n 2 黎曼假设 (Riemann Hypothesis): 黎曼Zeta 函数的非平凡零点的实部都是1/2 .3庞加莱猜想 (Poincare Conjecture):
5、 任意闭单 连通3-流型同胚于3-球. 4霍奇猜想 (Hodge Conjecture): 在非奇异复射 影代数簇上, 任一霍奇类是代数闭链类的有理线性 组合. 5BSD猜想 (Birch and Swinnerton- Dyer Conjecture) n 6奈维尔斯托克斯方程 (Navier- Stokes Equatoins) n7杨米尔斯理论 (Yang-Mills Theory): 证明诸 量子杨米尔斯场存在而且有一个大缺口.9背 景n计算机处理能力受限于内存大小与中央处 理器速度等，导致算法本身的数据结构对于 其执行效率有很大的影响。n在分析算法时，主要以时间复杂度与空间 复杂度两
6、者为分析依据。n随着计算器发展迅速，算法的空间复杂度 已经不是那么重要的一件事，目前分析主要 是在时间复杂度方面。10nP问题：线性时间或者多项式时间内能够解决 的问题。如能够在O(n)、O(nlog2n)、O(nk)数量级 内解决的问题。它们都是以多项式时间为上界。nNP问题：不能在多项式时间内解决的问题。如 计算时间数量级为O(n!)、O(2n)。n不可解问题：“图灵停机问题” 任何计算机耗费 任意时间不能解决。逻辑逻辑 学家阿朗索丘奇证证明 了所谓谓的判定问题问题 也是不可解的：判定一个已知 的语句是否表达一个算术的真值，决不可能有一 般的过程。换换句话说话说 ，能够输够输 出所有算术术
7、真值值 的计计算机是不存在的 。P与NP问题11图灵、图灵奖及图灵奖获得者简介1912年6月23日，出生于英国伦敦。 1931年-1934年，在英国剑桥大学国王学 院学习。 1932年-1935年，研究量子力学、概率论 和逻辑学。 1935年，由于独立发现中心极限定理，获 Smith奖，年仅23岁被选为剑桥大学国王 学院院士。 1936年，研究可计算理论，提出“图灵机” 的构想。12n1936年-1938年，主要在美国普林斯顿大学做博士研究，涉及逻辑学、代数和数论等领域。n1938年-1939年，返回剑桥从事研究工作，并应邀加入英国政府破译二战德军密码的工作。n1940年-1942年，作为主要
8、参与者和贡献者之一，在破译纳粹德国通讯密码的工作上成就杰出，并成功破译了德军U-潜艇密码，为扭转二战盟军的大西洋战场战局立下汗马功劳。13n1943年-1945年，担任英美密码破译部门的总 顾问。n1945年,应邀在英国国家物理实验室从事计算 机理论研究工作。n1946年，图灵在计算机和程序设计原始理论上 的构思和成果，已经确定了他的理论开创者的地 位。由于图灵的杰出贡献，他被英国皇室授予 OBE爵士勋衔。n1947年-1948年，主要从事计算机程序理论的 研究，并同时在神经网络和人工智能领域做出开 创性的理论研究。14n1948年，应邀加入英国曼彻斯特大学从 事研究工作，担任曼彻斯特大学计算
9、实验 室副主任。n1949年，成为世上第一位把计算机实际 用于数学研究的科学家。n1950年，发表论文“计算机器与智能”， 为后来的人工智能科学提供了开创性的构 思。提出著名的“图灵测试”理论。15n1951年，提出生物增长的非线性理论研究。年 仅39岁即被选为英国皇家学会会员。n1953年-1954年，继续在生物和物理学等方面 的研究。n1954年6月7日，42岁，图灵死于家中的床上， 床头有一个咬了一半的、在氰化物溶液中浸泡过的苹果，警方调查结论是自杀。n一代英灵，就此过早离去，成为人类科学史上 的一大遗憾。16Turing Awardn被公认为是计算机科学界的诺贝尔奖最高 奖项.奖励在计
10、算机科学技术研究中做出了创造性 贡献的杰出科学家. n1966年开始由ACM设立（美国计算机协会， 1947年成立，与IEEE Computer Society并列为计 算机界最著名的两大国际学术组织），用Turing 的名字来命名该奖，以纪念这位伟人对于计算机 科学技术发展的功绩。n通常每年1名获奖者, 偶尔2名(同方向)，02年3 名(RSA,Rivest,Shamir,Adelman).n虽未明确规定, 但授奖较偏重于计算机科学理 论和软件技术方面作出贡献的科学家. 唯一华人 获奖者是姚期智(Andrew Yao, 美籍, 2000年)17n1972，E.W.Dijkstra（美Burr
11、oughs公司）：求 最短路径的Dijkstra算法，PV操作，结构化程序 设计，“goto有害”等n1974，D.E.Knuth（stanford）：算法最早的奠 基人之一，现代“算法”与“数据结构”等名词及内 涵的提出，KMP算法，多卷算法巨著的作者， LR(k)文法，Tex编辑器等。n1976，M.O.Rabin（以色列人）x1,x2,xk)，当它属于的定义 域时，Q(TL，R，S)k中有惟一子集 (q;x1,x2,xk)与之对应。可以在(q;x1,x2,xk)中 随意选定一个值作为它的函数值。非确定性图灵机44P类与NP类语言pP=L|L是一个能在多项式时间内被一台DTM 所接受的语言
12、 pNP=L|L是一个能在多项式时间内被一台 NDTM所接受的语言由于一台确定性图灵机,可看作是非确定性图灵机的 特例，所以可在多项式时间内被确定性图灵机接受 的语言,也可在多项式时间内被非确定性图灵机接受 。故P NP。 45多项式时间变换设 ， 是2个语言。所谓语 言 能在多项式时间内变换为语言 (简记为 p )是指存在映身f: ，且f满足： (1)有一个计算f的多项式时间确定性图灵 机；(2)对于所有x ，x ，当且仅当 f(x) 。 46p语言L是NP完全的当且仅当p (1)LNP；p (2)对于所有LNP有L p L。p 如果有一个语言L满足上述性质(2)，但不一定满足性质 (1)，
13、则称该语言是NP难的。p所有NP完全语言构成的语言类, 称为NP完全语言类，记 为NPC。 47NPNPCPPNP？ P属于NP，NP属于P？NPC性质：任意一个NPC能在多项式时间解决，则所有 的NP问题都多项式可解。即PNP。48Cook定理（第一个NP完全问题）(Cook定理)：布尔表达式的可满足性问题是 NP完全的。49n0/1 knapsacknTraveling salesperson (TSP)nGraph coloringnSum of subsetsnMulticasting (多播) nHamiltonian cyclenMaximum cliquenMultiple sequence alignment (MSA) (多重序列比对)n 一些NP-complete问题50定理9-2：设L是NP完全的，则(1)LP当且仅当PNP；(2)若Lp ，且 NP，则 是NP完全的。 (2)可用来证明问 题的NP完全性。但 前提是：要有第一 个NP完全问题L。51NP完全问题已有300多个研究方向对某个NPC 得到确定算 法，NP=P证明某个 NPC不存在 确定算法发现新的 NPC问题52nThats All53
