计算机算法分析与设计第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:/,Clay Math.Inst.,Cambridge,MA,USA,)宣布,为7个问题中的任一个解答设立一百万美元奖金.,8,在这7个问题中，排在第一位的是P与NP问题。即P问题即是可被“运行多项式时间的”一个算法解决的问题(多项式时间:运行时间最多是输入量的多项式函数).NP问题即是有一个“可用多项式时间检验的”解答的问题.P=NP?,9,2黎曼假设(RiemannHypothesis):黎曼Zeta函数的非平凡零点的实部都是1/2.3庞加莱猜想(PoincareConjecture):任意闭单连通3-流型同胚于3-球.4霍奇猜想(HodgeConjecture):在非奇异复射影代数簇上,任一霍奇类是代数闭链类的有理线性组合.5BSD猜想(BirchandSwinnerton-DyerConjecture)6奈维尔斯托克斯方程(Navier-StokesEquatoins)7杨米尔斯理论(Yang-MillsTheory):证明诸量子杨米尔斯场存在而且有一个大缺口.,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，（美Burroughs公司）：求最短路径的Dijkstra算法，PV操作，结构化程序设计，“goto有害”等1974，（stanford）：算法最早的奠基人之一，现代“算法”与“数据结构”等名词及内涵的提出，KMP算法，多卷算法巨著的作者，LR(k)文法，Tex编辑器等。1976，（以色列人）（英国人）师兄弟（导师A.Church）：非确定有穷自动机的提出、判定问题等。Rabin：计算复杂性概念的雏形、随机算法的思想奠定、寻找及判定素数算法、单向函数等。Scott:语义学等。1978，（Stanford）：Heap-sort算法、求最短路径的Floyd动态规划算法等，编译及优化（优先文法等），程序正确性证明等。,1982，（加Toronto大学）：“NP-完全”概念的提出与理论的奠定，算法复杂性等。1984，N.Wirth（瑞士苏黎世高工）：“程序=算法+数据结构”，结构化程序设计分、创始人，Extended BNF等,“Pascal之父”。.1985，（UC-Berkeley）：计算机系、数学系、工业工程运筹学系“三栖教授”，哈佛文学士、理学硕士、数学博士。分枝限界法的创始人（与Held），Rabin-Karp子串匹配算法，求网络最大流的Edmonds-Karp算法，NP-完全理论（Karp规约等），随机算法，并行算法等。,1986，J.E.Hopcroft(Cornell)&（Princeton）：图论算法(e.g.深度优先算法，连通性、平面图判定),数据结构Hopcroft：形式语言与自动机名著作者（与Ullman），算法名著作者（与Aho、Ullman），算法好坏的衡量尺度（渐进时间复杂性），2-3树，机器人等。Tarjan：的博士生，集合的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-2pXn-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 knapsackTraveling salesperson(TSP)Graph coloringSum of subsetsMulticasting(多播)Hamiltonian cycleMaximum cliqueMultiple 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,