从中国象棋到NP完全问题

从中国象棋到NP完全问题【摘要】数学发展到21世纪，便和计算机的发展有了不解之缘。文章从古老的象棋谈起，围绕计算机的的灵魂——算法，也是数学最古老的本质论题，谈到了数学机械化的可能性。通过对可计算理论和复杂性理论的阐述，引出“千禧年数学难题”中最重要的问题之一——NP完全问题的基本理论和研究思想，在加深对NP完全性的理解之上，探讨我们所生活的这个世界的本质所在，我们所研究的数学问题的本质所在以及它的终极结论。全文涉及到很多基本概念，主要内容是围绕算法谈论NP完全问题的来龙去脉，从思想上深入理解这一千年难题的根本所指。【关键字】算法机械证明数学千年难题计算复杂性NP完全性终极理论0.引言这个世界的本质是什么？这是一个无人能回答的问题，也是一个值得人们永无止尽地去探求的问题。也许借助于“数学”这个人类至今所发明的最强有力的工具，我们会离答案更近一点。从万物的起源谈起，人类总不忘尝试着去复原那远古混沌的图景，也渴望着发现终极理论来诠释我们所在的宇宙。数学先于人类诞生，毋庸置疑！数学就是那万物得以有序运行的机制所在，数学就是我们所渴求的终极理论的美妙琴弦！霍金借助于数学工具，写出《时间简史》，增进了我们认识宇宙的深度；菜场上的老大娘默默念叨着菜价，为生计精打细算；华尔街的金融师做着大量的分析和计算，预测出全球金融市场的风起云涌；活跃在21世纪IT舞台的精英们也在尝试着把人类的实际需求转化成一个个的程序，交给计算机去处理……由此可见，数学的深入发展与人类的命运息息相关，不管是对个人还是群体。纵观数学辉煌的发展史，在各类简单的或是复杂的数学问题中，有没有共通的东西呢？有！那就是算法！你会惊讶地发现，算法似乎就是数学的本质！任何在数学上已解决了的问题都可以交给算法去处理，任何运行的机制和运动的物体都可以用算法来描述！于是我们就有了这样一个疑问：是否任何问题的解决都可以归结为寻求到相应的算法？然而，情况并不乐观，仍然存在着大量的不可计算的问题，也就是不能用算法来描述的问题让人们困惑不已。事实上，我们现在所掌握的数学并不是完美的。就像我们建立的现代科学体系，数学也只是对客观世界的近似刻画，是人类为获得外界信息所发明的一个有力工具。类似于语言，数学使得先辈们的生活经验得以记录下来，数学符号使得人们精确思维有了载体。数学的不完美性和持续发展性也能够从数学史上的三大悖论窥得，而每一个难题的解决则是人类思维升华、大脑进化的必然过程！数学需要深刻的思考，而正是这深入的思考促进了社会的发展。当不可思议的悖论发生的时候，那必然是我们的工具出了漏洞，在苦苦思索之后，我们的蒙昧与无知得到洗涤，我们对世界的认识也更加深入了。本文较系统地阐述了算法的一个高级话题——NP难问题——的其来龙去脉。文章从古老的中国象棋谈起，深入认识算法的本质，并由此延伸到数学的机械化。在对当今世界数学七大难题核心思想的了解下，进一步探析了计算复杂性的理论。文章最后围绕NP难问题，尝试着使其在思维上明朗化，以摆脱框框条条的束缚，站在哲学的高度来审视数学的本质所在，从而提高我们认识世界的广度和深度。1.美妙的算法1997年5月，深蓝第二次次挑战国际象棋世界冠军卡斯巴罗夫，比赛在5月11日结束，最终深蓝电脑以3.5：2.5击败卡斯巴罗夫，成为首个在标准比赛时限内击败国际象棋世界冠军的电脑系统。深蓝战胜人脑的根本所在在于它使用了更加优良的算法，而国际象棋大师的脑海中也储存了大量的棋谱和固有的逻辑推理。中国古代象棋也是一种基于推理的益智游戏，它是对古代战争的抽象模拟，对提高战将们的逻辑推理和思维的严密性很有帮助。弈棋高手大都熟悉很多棋谱（如下图所示），而那一张张棋谱实际上就是某一算法确定的一步，谁的算法更优，谁就能赢得棋局。图1-0中国象棋图1-1棋谱1.1算法的定义那么到底什么是算法呢？算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。定义1.1算法是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。正是由于算法的这种特性，才使得计算不仅可以由人，而且可以由计算机来完成。这也是深蓝得以战胜人脑的依据所在。用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。1.2算法的历史中国古代的筹算口诀与珠算口诀及其执行规则就是算法的雏形，这里，所解决的问题类是算术运算。古希腊数学家欧几里得在公元前3世纪就提出了一个算法，来寻求两个正整数的最大公约数，这就是有名的欧几里得算法，亦称辗转相除法。中国早已有“算术”、“算法”等词汇，但是它们的含义是指当时的全部数学知识和计算技能，与现代算法的含义不尽相同。英文algorithm(算法)一词也经历了一个演变过程，最初的拼法为algorism或algoritmi，原意为用阿拉伯数字进行计算的过程。这个词源于公元9世纪波斯数字家阿尔·花拉子米的名字的最后一部分。在古代，计算通常是指数值计算。现代计算已经远远地突破了数值计算的范围，包括大量的非数值计算，例如检索、表格处理、判断、决策、形式逻辑演绎等。欧几里得算法被人们认为是史上第一个算法。第一次编写程序是AdaByron于1842年为巴贝奇分析机编写求解伯努利方程的程序，因此AdaByron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(CharlesBabbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。因为“well-definedprocedure”缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用的。在20世纪以前，人们普遍地认为，所有的问题类都是有算法的。20世纪初，数字家们发现有的问题类是不存在算法的，遂开始进行可行性研究。在这一研究中，现代算法的概念逐步明确起来。30年代，数字家们提出了递归函数、图灵机等计算模型，并提出了丘奇－图灵论题，这才有可能把算法概念形式化。按照丘奇-图灵论题，任意一个算法都可以用一个图灵机来实现，反之，任意一个图灵机都表示一个算法。按照上述理解，算法是由有限多个步骤组成的，它有下述两个基本特征：每个步骤都明确地规定要执行何种操作；每个步骤都可以被人或机器在有限的时间内完成。人们对于算法还有另一种不同的理解，它要求算法除了上述两个基本特征外，还要具有第三个基本特征：虽然有些步骤可能被反复执行多次，但是在执行有限多次之后，就一定能够得到问题的解答。也就是说，一个处处停机（即对任意输入都停机）的图灵机才表示一个算法，而每个算法都可以被一个处处停机的图灵机来实现1.3算法分类算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法等。算法还可以宏泛的分为三类：有限的，确定性算法这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。有限的，非确定算法这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。无限的算法是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。1.4算法的特征一个算法应该具有以下五个方面的重要特征：输入一个算法有零个或多个输入，以刻画运算对象的初始情况。例如，在欧几里得算法中，有两个输入，即m和n。确定性算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。例如，欧几里得算法中，步骤1中明确规定”以m除以n，而不能有类似以m除n以或n除以m这类有两种可能做法的规定。有穷性一个算法在执行有穷步滞后必须结束。也就是说，一个算法，它所包含的计算步骤是有限的。例如，在欧几里得算法中，m和n均为正整数，在步骤1之后，r必小于n，若r不等于0，下一次进行步骤1时，n的值已经减小，而正整数的递降序列最后必然要终止。因此，无论给定m和n的原始值有多大，步骤1的执行都是有穷次。输出算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。例如，在欧几里得算法中只有一个输出，即步骤2中的n。可行性算法中有待执行的运算和操作必须是相当基本的，换言之，他们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。1.5算法的基本方法下面简单介绍算法的一些基本方法，而基于这些方法的分治策略、贪心策略、动态规划策略、分支限界法、回溯法等则是五种通用的算法设计技术。递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的。递归法递归指的是一个过程：函数不断引用自身，直到引用的对象已知。穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。贪婪法贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。分治法分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。动态规划法动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。迭代法迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。分支界限法与贪婪算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。1.6典型算法举例算法可以用自然语言描述。自然语言是人们日常所用的语言，如汉语、英语、德语等。使用这些语言不用专门训练，所描述的算法也通俗易懂。算法也可以用流程图描述。在数学课程里，我们学习了用程序框图来描述算法。在程序框图中流程图是描述算法的常用工具，即由一些图形符号来表示算法。算法还可以用伪代码描述。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此，书写方便、格式紧凑，易于理解，便于向计算机程序设计语言过度。公元前250年古希腊的数学家埃拉托塞尼提出一种筛法来求素数，下面我们用自然语言来描述该算法：Step1要得到不大于某个自然数N的所有素数，只要在2～N中将不大于√N的素数的倍数全部划去即可。Step2将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1d≤√N”。Step3再将Step2的内容等价转换：“若自然数N不能被不大于√N的任何素数整除，则N是一个素数”。Step4这句话的汉字可以等价转换成为用英文字母表达的公式：N=p1m1+a1=p2m2+a2=…=pkmk+ak.(1)其中p1，p2，…，pk表示顺序素数2，3，5，…，a≠0。即N不能是2m+0，3m+0，5m+0，…，pkm+0