计算机数学-前沿报告0227.pptVIP

希尔伯特(Hilbert)第十问题 在这些有关算法的研究中，数学家们还提出了一个重要的概念：递归可枚举集(Recursively Enumerable Set)，它是由可以有效计算的函数所生成的自然数的集合。 对于一个集合来说，最基本的问题就是判断一个元素是否属于该集合。递归可枚举集也不例外。当数学家们研究递归可枚举集的时候，发现了一个十分微妙的结果：对于某些递归可枚举集，无法判定一个自然数是否属于该集合！即这些递归可枚举集是不可判定的。这一结果将对算法的研究与判定问题联系了起来，为后来解决希尔伯特第十问题埋下了重要的伏笔。 希尔伯特(Hilbert)第十问题 到了1937年，在数学中存在无法判定的命题已经不再新鲜。因为早在5年前哥德尔就已经证明了他的不完全性定理，即任何足够复杂并且自洽的数学体系都必定包含不可判定的命题.但当时已知的不可判定命题多集中在逻辑领域。 那么，在数学的其他领域中，哪些命题不可判定呢？ 这个问题在整整10年之后才开始有答案。 1947年美国数学家波斯特(EmilPost，1897～1954)找到了第一个逻辑领域以外的不可判定命题。波斯特是一位有着深刻洞察力的逻辑学家，7岁时随父母从波兰移民到美国,是美国逻辑学的先驱之一。 希尔伯特(Hilbert)第十问题 波斯特大约早10年就得到了与哥德尔不完全性定理相似的结果，但由于想对结果作更全面的分析而没有及时发表。 1936年，几乎与哥德尔、丘奇及图灵同时，波斯特独立提出了类似于图灵的结果，因此他也是最早意识到希尔伯特第十问题可能会有否定答案的数学家之一。 1944年，在纽约市立大学任教的波斯特明确提出：希尔伯特第十问题“期待一个不可解性的证明”。这一观点深深打动了他的一位学生，并且也走上了毕生钻研希尔伯特第十问题的征途。这位学生名叫戴维斯(MartinDavis，1928～)，是解决希尔伯特第十问题的关键人物。 如何求解NPC， NP-难问题 既然人们普遍认为 ，那么遇到NPC，NP-hard问题又如何求解呢？ 对于小规模的问题，可采用指数时间复杂性的算法求解。 给原问题加上某些限制条件，求其加了限制条件的子问题的最优解。例如，最大独立集问题，如果限制其为平面图(或二部图)的话，那么就可以在多项式时间内求解。 利用启发式算法(heuristic)，求出问题的一个可行解。如遗传算法，模拟退火算法，局部有哪些信誉好的足球投注网站算法等。 设计多项式时间近似算法(Approximation Algorithms)。 Approximation Algorithm 对于NPC，NP-hard问题，启发式算法(heuristic)与近似算法(Approximation Algorithm)的主要区别在于: 前者无法在理论上给出所求的解与真正最优解的差距(即算法有多好或多坏？)，一般仅通过数值模拟来判定算法的好坏。 后者强调对所给问题的任意一个实例，都能够在多项式时间内求出一个可行解，并且该可行解所对应的目标函数值与最优值的偏差在理论上有充分的保证(可给出理论上的证明)。 下面简要介绍NP-难组合优化问题的近似算法设计。 这是目前在组合优化及理论计算领域中研究的一个比较多的课题。 近似比 近似算法的好坏通常由近似比(performance ratio， per-formance guarantee，worst-case ratio)来衡量。 对于最小化问题，近似比定义为： 。 其中sup为上确界。 若近似比为 ，则 对任何实例I都成立。 总是大于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的一个匹配，若再加入E\M中的任意一条边，则M就变得不再匹配，则称M为极大匹配。 算法1： 找图G的一个极大匹配M。令C为M中边的顶点组成的集合。 定理：算法1得