从中国象棋到NP完全问题..doc

从中国象棋到NP完全问题 【摘要】 数学发展到21世纪，便和计算机的发展有了不解之缘。文章从古老的象棋谈起，围绕计算机的的灵魂——算法，也是数学最古老的本质论题，谈到了数学机械化的可能性。通过对可计算理论和复杂性理论的阐述，引出“千禧年数学难题”中最重要的问题之一——NP完全问题的基本理论和研究思想，在加深对NP完全性的理解之上，探讨我们所生活的这个世界的本质所在，我们所研究的数学问题的本质所在以及它的终极结论。全文涉及到很多基本概念，主要内容是围绕算法谈论NP完全问题的来龙去脉，从思想上深入理解这一千年难题的根本所指。 【关键字】 算法 机械证明 数学千年难题 计算复杂性 NP完全性 终极理论 0. 引言 这个世界的本质是什么？这是一个无人能回答的问题，也是一个值得人们永无止尽地去探求的问题。也许借助于“数学”这个人类至今所发明的最强有力的工具，我们会离答案更近一点。 从万物的起源谈起，人类总不忘尝试着去复原那远古混沌的图景，也渴望着发现终极理论来诠释我们所在的宇宙。数学先于人类诞生，毋庸置疑！数学就是那万物得以有序运行的机制所在，数学就是我们所渴求的终极理论的美妙琴弦！霍金借助于数学工具，写出《时间简史》，增进了我们认识宇宙的深度；菜场上的老大娘默默念叨着菜价，为生计精打细算；华尔街的金融师做着大量的分析和计算，预测出全球金融市场的风起云涌；活跃在21世纪IT舞台的精英们也在尝试着把人类的实际需求转化成一个个的程序，交给计算机去处理…… 由此可见，数学的深入发展与人类的命运息息相关，不管是对个人还是群体。纵观数学辉煌的发展史，在各类简单的或是复杂的数学问题中，有没有共通的东西呢？有！那就是算法！你会惊讶地发现，算法似乎就是数学的本质！任何在数学上已解决了的问题都可以交给算法去处理，任何运行的机制和运动的物体都可以用算法来描述！于是我们就有了这样一个疑问：是否任何问题的解决都可以归结为寻求到相应的算法？然而，情况并不乐观，仍然存在着大量的不可计算的问题，也就是不能用算法来描述的问题让人们困惑不已。 事实上，我们现在所掌握的数学并不是完美的。就像我们建立的现代科学体系，数学也只是对客观世界的近似刻画，是人类为获得外界信息所发明的一个有力工具。类似于语言，数学使得先辈们的生活经验得以记录下来，数学符号使得人们精确思维有了载体。数学的不完美性和持续发展性也能够从数学史上的三大悖论窥得，而每一个难题的解决则是人类思维升华、大脑进化的必然过程！数学需要深刻的思考，而正是这深入的思考促进了社会的发展。当不可思议的悖论发生的时候，那必然是我们的工具出了漏洞，在苦苦思索之后，我们的蒙昧与无知得到洗涤，我们对世界的认识也更加深入了。 本文较系统地阐述了算法的一个高级话题——NP难问题——的其来龙去脉。文章从古老的中国象棋谈起，深入认识算法的本质，并由此延伸到数学的机械化。在对当今世界数学七大难题核心思想的了解下，进一步探析了计算复杂性的理论。文章最后围绕NP难问题，尝试着使其在思维上明朗化，以摆脱框框条条的束缚，站在哲学的高度来审视数学的本质所在，从而提高我们认识世界的广度和深度。 1. 美妙的算法 1997年5月深蓝次挑战国际象棋世界冠军卡斯巴罗夫，比赛在5月11日结束，最终深蓝电脑以3.52.5击败卡斯巴罗夫，成为首个在标准比赛时限内击败国际象棋世界冠军的电脑系统。 图1-0 中国象棋 图1-1 棋谱 1.1 算法的定义 那么到底什么是算法呢？算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。 定义1.1 算法是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。 正是由于算法的这种特性，才使得计算不仅可以由人，而且可以由计算机来完成。这也是深蓝得以战胜人脑的依据所在。用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。 1.2 算法的历史 中国古代的筹算口诀与珠算口诀及其执行规则就是算法的雏形，这里，所解决的问题类是算术运算。古希腊数学家欧几里得在公元前3世纪就提出了一个算法，来寻求两个正整数的最大公约数，这就是有名的欧几里得算法，亦称辗转相除法。中国早已有“算术”、“算法”等词汇，但是它们的含义是指当时的全部数学知识和计算技能，与现代算法的含义不尽相同。英文algorithm(算法)一词也经历了一个演变过程，最初的拼法为algorism或algoritmi，原意为用阿拉伯数字进行计算的过程。这个词源于公元 9世纪波斯数字家阿尔·花