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

1,第9章 NP完全性理论与近似算法,2,学习要点 理解RAM，RASP和图灵机计算模型 理解非确定性图灵机的概念 理解P类与NP类语言的概念 理解NP完全问题的概念 理解近似算法的性能比及多项式时间近似格式的概念 通过范例学习NP完全问题的近似算法 （1）顶点覆盖问题； （2）旅行售货员问题； （3）集合覆盖问题； （4）子集和问题。,3,在计算机算法理论中，最深刻的问题之一是： 从计算的观点来看，要解决的问题的内在复杂性如何，它是“易”计算的还是“难”计算的。,若知道了一个问题的计算时间下界，就可以较正确地评价解决该问题的各种算法的效率，进而确定对已有算法还有多少改进的余地。,在许多情况下，要确定一个问题的内在复杂性是相当困难的。但问题的计算复杂性可以通过解决该问题所需计算量的多少来度量。,4,如何区分一个问题是“难”还是“易”？,人们通常将在多项式时间内解决的问题看作是“易”解决的问题，而将需要指数时间解决的问题看作是“难”问题。（这里是针对问题的规模而言）,对于实际遇到的很多问题，人们至今未确切地了解其内在的计算复杂性。,只能用分类的方法, 将计算复杂性大致相同的问题, 归类研究。,5,计算模型,在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。 建立计算模型的目的, 是为了使问题的计算复杂性分析, 有一个共同的客观尺度。 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个数学问题. 这次是由“柯莱数学研究所” (http:/www.claymath.org/,Clay Math. Inst., Cambridge, MA, USA,)宣布, 为7个问题中的任一个解答设立一百万美元奖金.,8,在这7个问题中，排在第一位的是P与NP问题。即 P问题即是可被“运行多项式时间的”一个算法解决的问题 (多项式时间: 运行时间最多是输入量的多项式函数). NP问题即是有一个“可用多项式时间检验的”解答的问题. P = NP ?,9,2 黎曼假设 (Riemann Hypothesis): 黎曼Zeta函数的非平凡零点的实部都是1/2 . 3庞加莱猜想 (Poincare Conjecture): 任意闭单连通3-流型同胚于3-球. 4霍奇猜想 (Hodge Conjecture): 在非奇异复射影代数簇上, 任一霍奇类是代数闭链类的有理线性组合. 5BSD猜想 (Birch and Swinnerton-Dyer Conjecture) 6奈维尔斯托克斯方程 (Navier-Stokes Equatoins) 7杨米尔斯理论 (Yang-Mills Theory): 证明诸量子杨米尔斯场存在而且有一个大缺口.,10,背 景,计算机处理能力受限于内存大小与中央处理器速度等，导致算法本身的数据结构对于其执行效率有很大的影响。 在分析算法时，主要以时间复杂度与空间复杂度两者为分析依据。 随着计算器发展迅速，算法的空间复杂度已经不是那么重要的一件事，目前分析主要是在时间复杂度方面。,P问题：线性时间或者多项式时间内能够解决的问题。如能够在O(n)、O(nlog2n)、O(nk)数量级内解决的问题。它们都是以多项式时间为上界。 NP问题：不能在多项式时间内解决的问题。如计算时间数量级为O(n!)、O(2n)。 不可解问题：“图灵停机问题” 任何计算机耗费任意时间不能解决。逻辑学家阿朗索丘奇证明了所谓的判定问题也是不可解的：判定一个已知的语句是否表达一个算术的真值，决不可能有一般的过程。换句话说，能够输出所有算术真值的计算机是不存在的 。,P与NP问题,图灵、图灵奖及图灵奖获得者简介,1912年6月23日，出生于英国伦敦。 1931年-1934年，在英国剑桥大学国王学院学习。 1932年-1935年，研究量子力学、概率论和逻辑学。 1935年，由于独立发现中心极限定理，获Smith奖，年仅23岁被选为剑桥大学国王学院院士。 1936年，研究可计算理论，提出“图灵机”的构想。,1936年-1938年，主要在美国普林斯顿大学做博士研究，涉及逻辑学、代数和数论等领域。 1938年-1939年，返回剑桥从事研究工作，并应邀加入英国政府破译二战德军密码的工作。 1940年-1942年，作为主要参与者和贡献者之一，在破译纳粹德国通讯密码的工作上成就杰出，并成功破译了德军U-潜艇密码，为扭转二战盟军的大西洋战场战局立下汗马功劳。,1943年-1945年，担任英美密码破译部门的总顾问。 1945年,应邀在英国国家物理实验室从事计算机理论研究工作。 1946年，图灵在计算机和程序设计原始理论上的构思和成果，已经确定了他的理论开创者的地位。由于图灵的杰出贡献，他被英国皇室授予OBE爵士勋衔。 1947年-1948年，主要从事计算机程序理论的研究，并同时在神经网络和人工智能领域做出开创性的理论研究。,1948年，应邀加入英国曼彻斯特大学从事研究工作，担任曼彻斯特大学计算实验室副主任。 1949年，成为世上第一位把计算机实际用于数学研究的科学家。 1950年，发表论文“计算机器与智能”，为后来的人工智能科学提供了开创性的构思。提出著名的“图灵测试”理论。,1951年，提出生物增长的非线性理论研究。年仅39岁即被选为英国皇家学会会员。 1953年-1954年，继续在生物和物理学等方面的研究。 1954年6月7日，42岁，图灵死于家中的床上，床头有一个咬了一半的、在氰化物溶液中浸泡过的苹果，警方调查结论是自杀。 一代英灵，就此过早离去，成为人类科学史上的一大遗憾。,Turing Award,被公认为是计算机科学界的诺贝尔奖最高奖项.奖励在计算机科学技术研究中做出了创造性贡献的杰出科学家. 1966年开始由ACM设立（美国计算机协会，1947年成立，与IEEE Computer Society并列为计算机界最著名的两大国际学术组织），用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）：算法最早的奠基人之一，现代“算法”与“数据结构”等名词及内涵的提出，KMP算法，多卷算法巨著的作者，LR(k)文法，Tex编辑器等。 1976，M.O.Rabin（以色列人）&D.S.Scott（英国人）师兄弟（导师A.Church）：非确定有穷自动机的提出、判定问题等。Rabin：计算复杂性概念的雏形、随机算法的思想奠定、寻找及判定素数算法、单向函数等。Scott: 语义学等。 1978，R.W.Floyd（Stanford）：Heap-sort算法、求最短路径的Floyd动态规划算法等，编译及优化（优先文法等），程序正确性证明等。,1982，S.A.Cook（加Toronto大学）：“NP-完全”概念的提出与理论的奠定，算法复杂性等。 1984，N.Wirth（瑞士苏黎世高工）：“程序=算法+数据结构”，结构化程序设计分、创始人，Extended BNF等, “Pascal之父”。. 1985，R.M.Karp（UC-Berkeley）：计算机系、数学系、工业工程运筹学系“三栖教授”，哈佛文学士、理学硕士、数学博士。分枝限界法的创始人（与Held），Rabin-Karp子串匹配算法，求网络最大流的Edmonds-Karp算法，NP-完全理论（Karp规约等），随机算法，并行算法等。,1986，J.E.Hopcroft(Cornell) &R.E.Tarjan（Princeton）：图论算法(e.g. 深度优先算法，连通性、平面图判定), 数据结构Hopcroft：形式语言与自动机名著作者（与Ullman），算法名著作者（与Aho、Ullman），算法好坏的衡量尺度（渐进时间复杂性），2-3树，机器人等。Tarjan：D.E.Knuth的博士生，集合的Union-find算法，平摊分析，持久性数据结构及各种数据结构（e.g. 动态树、”八字型”树，自调整结构）.,1993，J.Hartmanis(Cornell) & R.E.Stearns (Albany)：计算复杂性理论的主要奠基人：系统化的理论体系及命名。Hartmanis：Hartmanis矩阵乘法，Hartmanis快速离散傅立叶变换。Stearns：首先提出将上下文无关文法理论应用于编译器设计等。 2000，AndrewYao（姚期智，Princeton，现在清华）：计算复杂性，量子计算，密码学（e.g. 单向函数）、通信理论等。 2002，Ronald L.Rivest,Adi Shamir, Leonard M. Adelman：公共密钥算法（RSA算法是当前在互联网传输、银行以及信用卡产业中被广泛使用的安全基本机制）.,22,图灵机,A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质： 该模型的每个过程都是有穷可描述的；过程必须是由离散的、可以机械执行的步骤组成。,图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。 通过研究TM来研究递归可枚举集和部分递归函数, 为算法和可计算性研究提供了形式化描述工具。,Finite,control,X,1,B,B,.,X,2,X,n,X,i,带（tape）,单元格（cell）,带符（tape symbol）,读写头在每一时刻扫描带上的一个单元 带有一个最左单元，向右则是无限的。 带的每个单元可容纳一个带符号 开始时，最左边n个单元装着输入（n0，n为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但不是输入符号。,图灵机的基本模型,24,图灵机的工作机制,在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作 改变状态 在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号. 将带头向左或者右移一个单元。,* 图灵机和双向有限自动机的区别：图灵机能改变它带上的符号。,图灵机的形式化描述,有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合,q0 Q T B T F Q,转移函数 : Q Q L,R ,形式定义 一个图灵机 TM (Turing machine) 是一个七元组 M = (Q, T, , , q0 , B , F ).,函数示例： Q QL ,R (q,ai)=(p,B,L) q, p Q (q,ai)=(p,b,R) ai b 格局 用w1q w2描述图灵机的瞬间工作状态（瞬像） q为M的当前状态， w1w2 * w1w2是当前时刻从开始端（因为可写）到右边空白符号为止的内容 当读写头已达到带的右端，则w1w2为读写头以左的内容。 约定：w1q w2表示读写头正扫描w2的最左字符 w2 则表示读写头正扫描一个空白字符。,图灵机的函数与格局,27,图灵机的格局,给定图灵机 M = (Q, T, , , q0 , B , F ) ，定义格局之间的推导关系M 如下： 1. 设 (q, Xi ) = (p, Y , L )，则有 X1X2Xi-1qXiXi+1Xn M X1X2Xi-2pXi-1YXn ， 但有如下两个例外 ： （1）i=1时， qX1X2Xn M qYX2Xn ，和 （2）i=n及 Y=B 时， X1X2Xn-1qXn M X1X2Xn-2p Xn-1 B.,28,2. 设 (q, Xi ) = (p, Y , R )，则有 X1X2Xi-1 q XiXi+1Xn M X1X2Xi-1Y p Xi+1Xn ， 但有如下两个例外 ： （1）i=n时， X1X2Xn-1q Xn M X1X2Xn-1Y p B ，和 （2）i=1及 Y=B 时， q X1X2XnM B p X2Xn-1Xn,图灵机接受的语言,L(M) = T*且q0* 1 p 2 ,pF, 12* 图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q0，且M的带头处在最左单元上，这些字符串将使M进入某个终止状态。 假定： 当输入被接受时，图灵机将停止，没有下一个动作。,任给图灵机 M = (Q, T, , , q0 , B , F ) ，以及输入字符 串wT*. 试问：对于w，M 是否停机？ 停机是指图灵机不存在下一个移动步（move）. 结论: 图灵机的停机问题是不可解的（即不可判定的）. 结论: 任给图灵机 M ，很容易构造一个图灵机 M，使得L(M)= L(M )，并满足：如果wL(M) ，则对于 w，M 接受w并一定停机. 如果没有特别指出，总是假定图灵机到达终态（接受态）后一定停机.但是 ，对不能接受的字符串，图灵机可能永不停止.（只要M还在某个输入上运行，无法知道是因为运行的时间不够长而没有被接受，还是根本就不会停机）,图灵机的停机问题,图灵机举例,例1：设语言 L=an bnn=1，设计图灵机接受L 。 思路：最初带上为 a a a b b b B B B n个a n个b 首先用x替换M最左边的a，再右移至最左边的b用y替换之，左移寻找最右的x，然后右移一单元到最左的a，重复循环。 如果 （1）当在搜寻b时，M找到了空白符B，则M停止，不接受该串。 （此时，a的个数大于b的个数） （2） 当将b改为y后，左边再也找不到a，此时,若右边再无b，接受；若仍有b，则b的个数大于a的个数，不接受。,举例 L=an bnn=1,(q0 ,a)=(q1 ,x,R) (q0 ,y)=(q3 ,y,R) (q1 ,a)=(q1 ,a,R) (q1 ,y)=(q1 ,y,R) (q1 ,b)=(q2 ,y,L) (q2 ,a)=(q2 ,a,L) (q2 ,y)=(q2 ,y,L) (q2 ,x)=(q0 ,x,R) (q3 ,y)=(q3 ,y,R) (q3 ,B)=(q4 ,B,R),例：aabb的接收格局序列 q0aabb xq1abb xaq1bb xq2ayb q2xaybxq0aybxxq1yb xxyq1bxxq2yyxq2xyyxxq0yyxxyq3yxxyyq3Bxxyyq4,例2 L = 0n1n2n n 1.,该图灵机的七元组形式为： M = (q0 , q1 , q2 , q3 , q4 , q5 , q6, 0,1,2, 0,1,2,X,Y,Z,B, , q0 , B , q6). 转移函数可由上图的转移图形式给出.,转移图与转移表,35,其他图灵机模型,“实际的”的图灵机模型 单带图灵机（1TM） 多带图灵机（kTM） 随机存取机（RAM） “实际的” 单位时间内完成的工作量有一个多项式上界 所有“实际的”计算模型多项式时间等价,36,多带图灵机,37,图灵机M的时间复杂性T(n),是它处理所有长度为n的输入,所需的最大计算步数。 如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。,图灵机的空间复杂性S(n),是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。 如果某个读写头无限地向右移动而不停机，S(n)也无定义。,图灵机既可作为语言接受器，也可作为计算函数的装置。,38,问题变换与计算复杂性归约,通过问题变换技巧，可以将2个不同问题的计算复杂性联系在一起。 将一个问题的计算复杂性,归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约。,39,假设有2个问题A和B，将问题A变换为问题B是指： 将问题A的输入, 变换为问题B的适当输入。 解出问题B 把问题B的输出, 变换为问题A的正确解。,40,若用O(n)时间能完成上述变换的第(1)和(3)步，则称问题A是(n)时间可变换到问题B，且简记为A(n)B。其中n通常为问题A的规模(大小)。 当(n)为n的多项式时，称问题A可在多项式时间内变换为问题B。 特别地，当(n)为n的线性函数时，称问题A可线性地变换为问题B。,41,命题1(计算时间下界归约)：若已知问题A的计算时间下界为T(n)，且问题A是(n)可变换到问题B，即A(n)B，则T(n)-O(n)为问题B的一个计算时间下界。,命题2(计算时间上界归约)：若已知问题B的计算时间上界为T(n)，且问题A是(n)可变换到问题B，即A(n)B，则T(n)+O(n)是问题A的一个计算时间上界。,问题变换与问题计算复杂性归约的关系,在命题1和2中，当(n)=o(T(n)时，问题A的下界归约为问题B的下界，问题B的上界归约为问题A的上界。,42,P类与NP类问题,非确定性图灵机 P类与NP类语言 多项式时间验证,43,确定性图灵机,在图灵机计算模型中，是单值的，即对于QTk中的每一个值，当它属于的定义域时，Q(TL，R，S)k中只有惟一的值与之对应，称这种图灵机为确定性图灵机，简记为DTM (Deterministic Turing Machine)。,44,非确定性图灵机（ NDTM ）：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，b，q0，qf)。 非确定性图灵机允许具有不确定性，即对于QTk中每一个值(q;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 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 (MSA) (多重序列比对) ,一些NP-complete问题,51,定理9-2：设L是NP完全的，则 (1)LP当且仅当PNP； (2)若Lp ，且 NP，则 是NP完全的。,(2)可用来证明问题的NP完全性。但前提是：要有第一个NP完全问题L。,52,NP完全问题已有300多个研究方向,对某个NPC得到确定算法，NP=P,证明某个NPC不存在确定算法,发现新的NPC问题,53,Thats All,