计算机数学-前沿报告0227

1、计算机数学：计算复杂性与难组合优化问题近似算法导论,为 什 么 要 做 这 个 报 告 ？！,From M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness,From M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness,From M.R. Garey, D.S. Johnson, Computers and Intr

2、actability: A guide to the theory of NP-completeness,本报告主要内容,计算复杂性理论（Theory of Computational Complexity）介绍 一些经典的NP-难组合优化问题的近似算法设计（Approximation Algorithm）及设计近似算法的常用技巧和方法介绍。,引言,什么是组合最优化？ (Combinatorial Optimization) 什么是“好的算法”？ “好的算法”的组合优化的例子。 什么是P，NP？什么是NPC，NP-hard？ 什么是近似算法？ 几个经典的近似算法例子。,引言,“芝麻”开门： 阿

3、里巴巴来到一个装满宝石的山洞里，这里的每块宝石都标着精确的数据：价值和体积。阿里巴巴随身只带了一个口袋。 问：他选取哪些宝石装入口袋才能使得带走的宝石价值最大？ 背包问题(Knapsack)： 给定件物品I1,I2,In，其体积与价值各为si和ci，背包的体积为V。这里引入0-1变量。 数学描述：,组合优化的例子,公路连接问题： 某地区有若干主要城市，现在要修建一些高速公路将这些城市连起来，使得从任何一个城市都能够经过高速公路直接或间接地到达另一个城市。假定已经知道任何两个城市之间修建高速公路的成本。 问：如何修建高速公路网，才能使得总的成本花费最小？,组合优化的例子,最短路问题（Shorte

4、st Path problem）： 一名货运司机要把货物从甲地运往乙地，从甲地到乙地公路从横交错，如下图示。 问：他如何选择行走路线，才能使甲地和乙地之间路径的距离最短？,组合优化的例子,旅行商问题（Traveling Salesman Problem, TSP): 一名推销员要到若干个城市去洽谈业务。假设已经知道这若干个城市中的任意两个城市之间的距离。 请为其设计一个旅行线路，使得他从某一城市出发经过每个城市一次且仅一次，最后又回到出发城市。并且他所走过的旅行线路最短。,组合优化的例子,最优指派问题（Assignment Problem）： 一个公司有N个职员和N 项工作，现在要安排每人做一

5、项工作。假定员工i做工作j产生的效益为wij。 问：如何安排每个职工的工作，才能使整个公司的总效益最大？,j1,j2,j3,j5,j4,p2,p1,p5,p3,p4,组合优化的例子,顶点覆盖问题（vertex cover）： 给定无向简单图G =（V，E）。 要求：找顶点个数最少的V的子集V， 使得E中每条边的两个端点中至少有一个端点在V中。,组合优化问题的共同特点,它们研究的对象是离散的，研究的目标一般也都是从有限个可能的方案中选择某种最优方案。 上述实例中，除了背包问题外，其余都可用图来描述。 与图有关的组合优化问题，一般称其为网络优化问题。 由于所有可能的方案都有限，当然可以用枚举方法来

6、选择最优方案。但是当问题规模较大时，枚举法花费的计算量就会太大。因此，我们需要设计“好”的算法。,问题的实例,一个优化问题的实例（instance）： 它是一个二元组(F，c)。其中F是由全部/部分可行解组成的集合；c是费用函数, c: FR 。 (最小化)问题： 是找到一个f F使得对任意的y F都有c(f)c(y)。 优化问题：由所有实例组成的集合。 通俗地，实例是某一个输入的数据，如在背包问题中，实例是背包的容量，以及所有宝石的价值和体积。 背包问题就是要求对所有的实例都给出一个统一的算法；而不是对于一组特定的输入数据，计算出一个结果。,算法及其优劣,为各种组合优化问题设计出好的算法，是

7、组合最优化研究领域中的核心问题。 算法： 对于优化问题的任一个实例I， 经过一个计算过程A(I)得到问题的最优解OPT(I)。 算法的好与坏的衡量标准： 解答问题时花费的时间(时间复杂性)的多少，和占用的存储单元的数量(空间复杂性)。 时间复杂性和空间复杂性统称计算复杂性。,时间复杂性,时间复杂性：依赖于计算模型和实例大小。 因为不同配置的计算机的运行速度不同，实例的大小不同则占用的存储空间也不同。 用f(n)表示计算一个输入规模为n的实例I时，算法A需要完成的基本操作(加、减、乘、除，比较等)的数量。可以f(n)来衡量A解答I时花费的时间，即时间复杂性。 f(n)是算法A解答任意输入规模为n

8、的实例时，在最坏情况(worst case)下必须完成的基本操作的数量。 我们感兴趣的是n充分大时，算法A的时间复杂性。,问题实例的规模,问题实例的“大小”(size)，可理解为将该实例的所有信息输入计算机时需要的(二进制)字节数。 显然，对于同一个实例，不同的信息编码方案可能会产生不同长度的实例编码。但是若选择的编码方案合理，则其编码长度不会相差太大，不至于影响我们分析算法的时间复杂性。 例如，对于实例I，设某种编码方案的编码长度是f(n)，则另一种编码方案的编码长度至多为f(p(n)，这里p(n)是一个关于n的多项式。,合理的实例大小,背包问题实例I大小： 高速公路连接问题： 最短路问题：

9、 旅行商问题： Vertex-Cover：,不合理的实例大小,例：Composite Number Problem Instance：整数n1。 Question：是否存在p,q1，使得n=pq ? 合理：|I|= log2n 。 不合理：|I|=n。 在该不合理输入大小下，复合数判定问题就有一个“好的”算法(见后面讨论)：检查所有不大于 的自然数能否整除n,所需时间=O( )=O( )。,不同 的计算时间比较,假定计算机运行速度是1百万次/秒,多项式时间算法,若采用算法A解答任何一个规模为n的实例时，其基本操作步骤数f(n)能够被一个多项式函数所界定，即 f(n)=O(n)，则称算法A是一个

10、多项式时间算法。 n(logn)和n2.8都是多项式时间算法。 计算时间随着n的增长不超过多项式的算法被认为是“好的”算法（Edmonds，1965）。 在实践中，若 3，则O(n)的算法对规模较大的问题 (n10000)是有效的。,在多项式时间内可解的组合优化问题,最小生成树问题(Minimum Spanning Tree，MST)： 给定无向简单图G =(V，E)，G的每条边有权值w(e)0,eE。 求G的一个总权值最小的生成树。 高速公路连接问题在本质上就是最小生成树问题。 求MST的Kruskal算法(1956)： 1将所有边按照权值从小到大排序w(e1)w(e2) w(em)。 2从

11、e1开始不断按顺序添加边，且保证不形成圈。 3直到最后无法再添加边为止。,求最小生成树的例子,求最小生成树的例子,算法的正确性,生成树T的基本性质： (1)是有n个顶点，n-1条边的连通图； (2)若任添加一条边，则得到的图恰好含有一个圈； (3)去掉该圈中任一边，则得到另一颗生成树。 假定 是最小生成树问题的最优解，且 ，可以证明由T*可以得到一棵树T，该树总权重不大于T*，且与Kruskal算法产生的树一样。,证明反证法,时间复杂性分析,对m条边按权重排序，花费的时间为 判断加入一条边后是否会形成圈，花费的时间为 。 该算法时间复杂性为： 因此Kruskal是多项式时间算法，从而是好的算法

12、。,多项式时间可解的问题(P类问题),一个图中任意两点间的最短距离的Dijkstra算法； 指派问题(赋权匹配问题)的Kuhn算法； 最大流-最小割(Max flow-Min cut)的Ford and Fulkerson算法 ,多项式时间可解的问题(P类问题),TSP, Knapsack及Vertex-Cover 是P问题吗?,NP类问题,P代表多项式时间可解的一类问题。 NP代表什么呢? 是“不存在多项式时间算法的一类问题吗”？,优化问题及其判定形式,TSP问题的优化形式： Instance：给定n各城市c1,c2,cn ，以及它们两两之间的距离表d(ci,cj), i,j=1,2,n。

13、Question：求一个置换，使得 TSP问题的判定形式： Instance：给定n各城市c1,c2,cn，以及它们两两之间的距离表d(ci,cj),i,j=1,2,n，以及整数k0 Question：是否存在一个置换， 使得 ?,NP类问题,NP是一大类判定问题，其准确含义是可在一种假想的机器非确定型Turing机上在多项式时间内可求解的问题，或者说NP类问题可由非确定型算法在多项式时间可解。 通俗地将讲，有这么一大类判定问题，譬如TSP问题的判定形式，求解它很困难。但是，若有人告诉你，他找到了该问题的解, 则你能够很容易验证他的对错。 NP问题是在多项式时间内可以检验的问题。,NP-com

14、plete，NP-hard,显然 ,但 吗? 1970年左右，Cook发现了一些组合优化问题可在多项式时间内相互转化。如果其中一个是P问题，那么其他问题也属于P问题，反之亦然。 如TSP, Vertex-Cover，Knapsack等问题都属于NP问题类。目前的NP类中已证包含几千个被证明的组合优化问题。,NP-complete，NP-hard,显然 ,但 吗? 1970年左右，Cook发现了一些组合优化问题可在多项式时间内相互转化。如果其中一个是P问题，那么其他问题也属于P问题，反之亦然。 如TSP, Vertex-Cover，Knapsack等问题都属于NP问题类。目前的NP类中已证包含几

15、千个被证明的组合优化问题。 NP-难问题的定义： 若NP里面的每一个问题都可在多项式时间内归约到S，则S被称为NP-难(NP-hard)。S是NP-难表示了S不比NP里面的任何问题易解(NP-难并不是意味着在NP里面而且很难)。,NP-complete，NP-hard,若S既是NP-难，又是NP里面的问题，则S就称为NP-完全问题。 也有的书上这样描述NP-完全问题：人们无法为这些问题找到好的算法，从而证明其属于P类；又无法证明其不属于类。这些NP问题就统称为NP-完全问题。 因此，NP-完全有两个条件：一是SNP;二是S为NP-难。 NP-完全的含义也有两个： 非确定型算法多项式时间可解答。

16、该属性来源于NP-完全问题属于NP类，因此存在非确定型多项式时间算法。 完全。解决一个，便解决所有。该属性来源于NP-难的定义,所有NP里面的问题都可归约到S。因此，解答了S(即找到确定型多项式时间算法)，就解答了NP里面的所有问题。,NP-complete，NP-hard,定理 若有一个NP-难问题存在多项式时间算法，则P= NP。 证明：令O为某一NP-难优化问题，w.l.g.，设O为最小优化问题。A是解答O的一个多项式时间算法。设与O对应的判定问题为D，则D的一个实例I将具有形式(I,c)，这里c是一个界值。 则可采用下面的办法解答D的实例I： 用A解答I得到一个解；检查这个解的解值是否

17、超过c。 因此，判定问题D存在多项式时间算法。 由NP-完全的定义得知P=NP。,一些经典的NPC问题,TSP； Knapsack； 顶点覆盖（Vertex Cover)； 集合覆盖（Set Cover）； Hamilton 回路（Hamiltionian Cycle）； 最小控制集问题（Dominating Set）； 最大独立集（Maximum Independent Set)； 最大团（Maximum Clique）； 着色数(Chromatic Number) ； 整数规划； ,P vs NP,如果 ， 不利因素是，则现代社会依赖的网上银行、网上交易等密码系统随即崩溃。 积极的方面是，

18、大量的组合优化问题可找到好的算法，对人们生产、生活的影响将不可估量。数学定理的证明也将由计算机来完成；一个平常人也可以象默扎特、贝多芬一样谱写传世的音乐作品。 你们希望P=?NP吗？,P vs NP,对于P=?NP的问题，尽管目前还没人能给出令人信服的证明，但人们还是普遍倾向于认为 。 主要原因： (1)基于NP-完全理论，人们发现大量(几千个)的组合优化问题，它们有着一样的难解性。对这些问题而言，如果一个问题可以在多项式时间内求解，则所有的问题都可多项式内求解。但又没有人能够给出任何一个NP-完全问题的多项式时间算法。 (2)如果P=NP，这个世界与我们所想象的大不一样！ 当然，P是否等于N

19、P尚没有最后定论，解决它需要新的重大突破。,七个千禧年大奖难题,千禧年大奖难题(Millennium Prize Problems)(又称世界七大数学难题)，在2000年5月24日由美国克雷数学研究所(Clay Mathematics Institute,CMI)对外公布。 克雷数学研究所规定：这些难题的解答必须发表在数学期刊上，且需要经过各方验证(验证期两年)。每破解一道难题，获得奖金1,000,000美元。 这些难题是与1900年德国数学家大卫希尔伯特在巴黎提出的23个历史性数学难题相呼应的。一百年过去了，许多难题已获得解答。而千禧年大奖难题的破解，极有可能为密码学,航天，通讯等领域带来突

20、破性进展。,七个千禧年大奖难题,(1)Riemann Hypothesis 黎曼(Riemann)假设 有些数具有不能表示为两个更小的数的乘积的特殊性质,例如2,3,5,7等等，这样的数称为素数。它们在纯数学及其应用中都起着重要作用。在所有的自然数集中,素数的分布没有规律;然而德国数学家黎曼(18261866)观察到，素数出现的频率与一个精心构造的所谓黎曼蔡塔函数(s)的性态相关。 著名的黎曼假设断言，方程(s)=0的所有有意义的解都在一条直线上(已经被开始的1,500,000,000个解验证过)。 若(能够证明)该断言对每一个有意义的解都成立，则将为和素数分布相关的许多奥秘带来一线光明。,七

21、个千禧年大奖难题,(2)Poincares Conjecture 庞加莱(Poincare)猜想 若伸缩一个围绕苹果表面的橡皮带，则可在既不扯断它又不让它离开表面的条件下，使它慢慢移动收缩为一个点。 相似地，若同样的橡皮带以适当的方向被伸缩在一个轮胎表面上，在不扯断橡皮带或者轮胎面的条件下，则无法将其收缩到一点。因为苹果表面是“单连通的”,轮胎表面则不是。 一百年前，庞加莱已经知道，二维球面在本质上可由单连通性来刻画，并提出三维球面(四维空间中距原点有单位距离的点的集合)的对应问题。这个问题立即变得无比困难，从那时起，数学家们就在为此奋斗。(该问题已由Perelman解决),七个千禧年大奖难题

22、,(3) P vs NP 在应邀参加的一个盛大晚会上，你想知道是否有你已经认识的人。你的主人向你说，你一定认识那位正在甜点盘附近的罗丝女士。不费1秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，若没有这样的暗示，你就必须环顾整个大厅，一个个地审视，看是否有你认识的人。 斯蒂文库克(Stephen-Cook)于1971年提出：找到问题的一个解通常比验证一个给定的解要花费更多的时间。这被看作是逻辑和计算机科学中最突出的问题之一。,七个千禧年大奖难题,(4)Navier-Stokes Equation 纳维叶-斯托克斯方程的存在性与光滑性 当驾着小船在湖中蜿蜒穿梭的时候，小船的后面跟随着起伏

23、的波浪；当喷气式飞机飞行的时候，飞机的后面跟随着湍急的气流。 数学家和物理学家深信，无论是微风还是湍流，都可通过纳维叶-斯托克斯方程的解对其解释和预言。 这些方程是19世纪写下的，但我们对它们的理解仍然极少。其挑战型就在于对数学理论作出实质性的进展，使我们能解开隐藏在纳维叶斯托克斯方程中的奥秘。,七个千禧年大奖难题,(5)Yang-Mills Theory 杨-米尔斯(Yang-Mills)的存在性和质量缺口 在基本粒子世界中，量子物理的定律显然成立(但其观点与经典力学的牛顿定律对宏观世界的方式相同)。 半个世纪前，杨振宁和米尔斯发现，量子物理揭示了在基本粒子的物理与几何对象的数学之间有着令人

24、注目的关系。 基于杨-米尔斯方程的预言已经在实验室(布罗克哈文、斯坦福、欧洲粒子物理研究所和筑波)中所完成的高能实验中被证实。 但是被物理学家认可并用来解释“夸克”的不可见性的“质量缺口”假设却从来没有得到一个数学上令人满意的证实。 解决这一问题需要在物理学和数学上引进全新的观念。,七个千禧年大奖难题,(6)Hodge conjeture 霍奇(Hodge)猜想 20世纪的数学家找到了研究复杂对象的形状的强有力的办法。基本想法是：用把维数不断增加的简单几何营造块粘合在一起的办法，得到给定对象的形状。(在怎样的程度上?) 用很多种方式来推广这种技巧，便开发出一些强有力的工具。这些工具极大地方便了

25、数学家对形形色色的对象的分类。但也很不幸，在推广中程序的几何出发点变得模糊起来，为此，必须加上某些没有任何几何解释的部件。 霍奇猜想断言，对于像射影代数簇这种特别完美的空间类型，称作霍奇闭链的部件实际上是代数闭链的几何部件的(有理线性)组合。,七个千禧年大奖难题,(7)Birch and Swinnerton-Dyer Conjecture 贝赫(Birch)和斯维讷通-戴尔(Swinnerton-Dyer)猜想 数学家总是着迷诸如方程 x2 + y2 = z2 的所有整数解的刻画问题。欧几里德对这一方程给出了完全的解答，但这种方法很难解答那些复杂的方程。 马蒂雅谢维奇(Yu.V.Matiya

26、sevich)曾经指出：希尔伯特第十问题是不可解的，即不存在一般的方法来确定这样的方程是否有整数解。,七个千禧年大奖难题,(7)Birch and Swinnerton-Dyer Conjecture 贝赫(Birch)和斯维讷通-戴尔(Swinnerton-Dyer)猜想 当解是一个阿贝尔簇的点时，贝赫和斯维讷通-戴尔猜想认为,有理点的群的大小与蔡塔函数z(s)在点s=1附近的性态有关。 这个有趣的猜想认为，若z=0，则存在无限多个有理点(解). 若z0，则只存在有限多个这样的点。 阿贝尔(Abel)簇是代数几何学中的一个重要的研究对象，它既是一个代数簇，又具有阿贝尔群的结构。,希尔伯特(H

27、ilbert)第十问题,希尔伯特(Hilbert)第十问题(中国青年报) 据说，有人曾建议德国数学家希尔伯特(18621943)去解决费马猜想，以夺取为这一猜想而设立的沃尔夫斯凯尔奖金(Wolfskehl Prize)。希尔伯特笑着说:“我为什么要杀掉一只会下金蛋的鹅呢？”在希尔伯特看来，费马猜想这样的数学问题对数学的价值无可估量。 希尔伯特不仅舍不得“杀鹅”，而且还怀着极大的热诚为20世纪的数学界做了一回“寻鹅之人”。1900年在巴黎举行的国际数学家大会上，他以“数学问题”为题目作了一次演讲.会上，他列举了23个具有重要意义的数学问题，这些问题被后人称为“希尔伯特问题”。,希尔伯特(Hilb

28、ert)第十问题,希尔伯特第十问题是一个与解方程有关的问题。 比如，方程2x2y1和x2y2z2的共同特点是只包含未知数的整数次幂，且系数也都是整数。称这类方程为整系数代数多项式方程。 数学家们对这类方程的研究有着漫长的历史。公元3世纪，希腊数学家丢番图发表了长篇巨著算术。经过1700多年的漫长岁月，这部13卷的著作流传至今的只有六卷。丢番图在这部著作中对整系数代数多项式方程进行的大量研究，对代数与数论的发展有着先驱性的贡献。后人为纪念他，把整系数代数多项式方程称为丢番图方程。,希尔伯特(Hilbert)第十问题,对于丢番图方程，数学家们最感兴趣的是它是否有整数解(或自然数解)。对那些简单的方

29、程很容易找到答案。如， x2y2z2有整数解(早在3000多年前，我国的数学家就给出了一组解：即勾三股四弦五)。 2x2y1则没有整数解(方程的左边为偶数，右边为奇数)。但对于一般的丢番图方程来说，判断它是否有整数解却极其困难，其中最著名的例子就是费马猜想，即xnynzn在n2时没有非零整数解。这个猜想直到300多年后才得到证明。,希尔伯特(Hilbert)第十问题,长期以来，人们仅对特定形式的丢番图方程是否有整数解进行了研究。如何判定一般的丢番图方程是否有整数解呢？这就是著名的希尔伯特第十问题。这样的问题在数学上被称为判定问题(Decision Problem)，因为它寻求的是对数学命题进行

30、判定的算法。 希尔伯特提出这一问题时，没有用“是否存在这样的算法”作为问题的表述，而是直接要求数学家们寻找这样的算法，可见他对存在一个肯定的答案怀有期待。这种期待与他在其他方面对数学的乐观看法一脉相承。,希尔伯特(Hilbert)第十问题,不可判定命题的启示： 希尔伯特第十问题要求寻找判定丢番图方程是否有解的算法,然而，在该问题提出后的整整30年内没有取得任何进展。 直到20世纪30年代，对算法的研究才逐渐深入。 因为算法是(通过有限多的步骤)对数学函数进行有效计算的方法，所以研究算法的一个重要切入点是寻找可以有效计算的函数。 什么是可有效计算的函数呢？数学家们开始时只知道，一些最简单的函数以

31、及用这些函数通过若干简单规则组合出的函数是可有效计算的函数(把这类函数叫做递归函数)。,希尔伯特(Hilbert)第十问题,1931年，法国数学家赫尔布兰德(Jacques Herbrand，19081931)对递归函数进行了研究，并给著名逻辑学家哥德尔(19 061978)写信叙述了自己的研究结果。因哥德尔当时正在研究自己一生中最重大的成果哥德尔不完全性定理，就没有对赫尔布兰德的工作立即回应。就在那一年的夏天，年仅23岁的赫尔布兰德在攀登阿尔卑斯山的时候不幸遇难，他的工作因此也被暂时埋没了。,希尔伯特(Hilbert)第十问题,20世纪30年代初(几乎与赫尔布兰德的研究同时)，普林斯顿大学的

32、美国逻辑学家丘奇(AlonzoChurch,19031995)也在积极从事逻辑及算法的研究，并且提出了一种新的逻辑体系。他让自己的两个学生克林(StephenKleene,19091994)与罗瑟(JohnRosser，19071989)对这一体系进行细致的研究。两个学生都是一流的好手，后来克林也成为一流的逻辑学家.他们研究出的结果大大出乎丘奇的意料。他们发现丘奇的那套体系竟然是自相矛盾的！ 命运似乎只有一个：放弃。,希尔伯特(Hilbert)第十问题,幸运的是，丘奇的那套体系中有一个组成部分是自洽(self-con sistent,自相一致)的 ，因此被保留了下来，这部分叫做兰姆达运算(ca

33、lculus)。 这种兰姆达运算可以用来定义函数，而所有用兰姆达运算定义的函数都是具备有效计算的特点。在对兰姆达运算做了研究之后，丘奇提出了一个大胆的猜测：所有可以有效计算的函数都可以用兰姆达运算来定义。 1934年，丘奇向到普林斯顿大学访问的哥德尔介绍了这一猜测，哥德尔却不以为然。丘奇不服气，请哥德尔给出一个他认为合适的描述。,希尔伯特(Hilbert)第十问题,两个月后，哥德尔就给出了一种完全不同的描述，这种描述的基础正是3年前赫尔布兰德在给他的信中叙述的结果。后来哥德尔对这一结果进行了完善，被后人称之为赫尔布兰德哥德尔递归函数。 这样，丘奇与哥德尔分别给出了描述可以有效计算的函数的体系。

34、并且丘奇与克林很快就证明了这两种描述方式的等价性。这大大增强了丘奇的信心，并且相信人们已经找到了可以有效计算的函数的普遍定义。但是哥德尔及其他一些人对此却仍然怀有疑虑。最终打消这种疑虑的是英国数学家图灵(AlanTuring，19121954)。,希尔伯特(Hilbert)第十问题,图灵当时对丘奇及哥德尔在这方面的研究并不知情。他所研究的课题是什么样的运算可以用机器来实现。他的这一研究对后来计算机科学的发展产生了深远的影响。 在图灵的研究工作接近完成的时候，他的导师注意到了丘奇与哥德尔的工作。图灵对彼此的工作进行了比较后，发现丘奇与哥德尔所定义的那些函数与他的抽象计算机可以计算的函数恰好吻合！

35、图灵把这一结果作为附录加进了自己的论文.这就使得哥德尔心悦诚服了。,希尔伯特(Hilbert)第十问题,在这些有关算法的研究中，数学家们还提出了一个重要的概念：递归可枚举集(Recursively Enumerable Set)，它是由可以有效计算的函数所生成的自然数的集合。 对于一个集合来说，最基本的问题就是判断一个元素是否属于该集合。递归可枚举集也不例外。当数学家们研究递归可枚举集的时候，发现了一个十分微妙的结果：对于某些递归可枚举集，无法判定一个自然数是否属于该集合！即这些递归可枚举集是不可判定的。这一结果将对算法的研究与判定问题联系了起来，为后来解决希尔伯特第十问题埋下了重要的伏笔。,

36、希尔伯特(Hilbert)第十问题,到了1937年，在数学中存在无法判定的命题已经不再新鲜。因为早在5年前哥德尔就已经证明了他的不完全性定理，即任何足够复杂并且自洽的数学体系都必定包含不可判定的命题.但当时已知的不可判定命题多集中在逻辑领域。 那么，在数学的其他领域中，哪些命题不可判定呢？ 这个问题在整整10年之后才开始有答案。 1947年美国数学家波斯特(EmilPost，18971954)找到了第一个逻辑领域以外的不可判定命题。波斯特是一位有着深刻洞察力的逻辑学家，7岁时随父母从波兰移民到美国,是美国逻辑学的先驱之一。,希尔伯特(Hilbert)第十问题,波斯特大约早10年就得到了与哥德尔

37、不完全性定理相似的结果，但由于想对结果作更全面的分析而没有及时发表。 1936年，几乎与哥德尔、丘奇及图灵同时，波斯特独立提出了类似于图灵的结果，因此他也是最早意识到希尔伯特第十问题可能会有否定答案的数学家之一。 1944年，在纽约市立大学任教的波斯特明确提出：希尔伯特第十问题“期待一个不可解性的证明”。这一观点深深打动了他的一位学生，并且也走上了毕生钻研希尔伯特第十问题的征途。这位学生名叫戴维斯(MartinDavis，1928)，是解决希尔伯特第十问题的关键人物。,如何求解NPC， NP-难问题,既然人们普遍认为 ，那么遇到NPC，NP-hard问题又如何求解呢？ 对于小规模的问题，可采用

38、指数时间复杂性的算法求解。 给原问题加上某些限制条件，求其加了限制条件的子问题的最优解。例如，最大独立集问题，如果限制其为平面图(或二部图)的话，那么就可以在多项式时间内求解。 利用启发式算法(heuristic)，求出问题的一个可行解。如遗传算法，模拟退火算法，局部搜索算法等。 设计多项式时间近似算法(Approximation Algorithms)。,Approximation Algorithm,对于NPC，NP-hard问题，启发式算法(heuristic)与近似算法(Approximation Algorithm)的主要区别在于: 前者无法在理论上给出所求的解与真正最优解的差距(即

39、算法有多好或多坏？)，一般仅通过数值模拟来判定算法的好坏。 后者强调对所给问题的任意一个实例，都能够在多项式时间内求出一个可行解，并且该可行解所对应的目标函数值与最优值的偏差在理论上有充分的保证(可给出理论上的证明)。 下面简要介绍NP-难组合优化问题的近似算法设计。 这是目前在组合优化及理论计算领域中研究的一个比较多的课题。,近似比,近似算法的好坏通常由近似比(performance ratio， per-formance guarantee，worst-case ratio)来衡量。 对于最小化问题，近似比定义为： 。 其中sup为上确界。 若近似比为 ，则 对任何实例I都成立。 总是大于

40、1，越接近于1，近似效果越好。若 等于1，则就得到了精确解。 对于最大化问题，近似比定义为 。 对任何实例I，总有 。,(按近似比进行的)近似算法的分类,常数倍近似算法： 存在一个常数c，使得对任意实例I，都有 多项式时间近似方案(Polynomial Time Approximation Scheme, PTAS): 对于 ，存在一个多项式时间近似算法 ，使得对任意实例I，都有 (完)全多项式时间近似方案(FPTAS)： 如果在上式中多项式时间仅依赖于输入的大小和 ，则称其为FPTAS。,几个经典问题的近似算法设计,顶点覆盖（vertex cover）的近似算法； 背包问题的近似算法； 带度量的TSP的近似算法。,顶点覆盖问题近似算法,定义： 在图G=(V,E)中，若G的边子集M中的任意两条边都没有公共顶点，则称M为G的一个匹配(matching)。 M为G的一个匹配，若再加入EM中的任