按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
算法的功能之一是其能用于一个问题的所有实例。例如加法算法可以算出任何两个整数的和。你虽然花费时间去详尽写出一种算法的全部细节，但你却得到了一种能够保证工作的方法。计算机的程序或是单一的算法或是系列的算法。如果没有指令告诉该算法的每一步骤应该做些什么，那么计算机就同不能模拟系好鞋带一样，也不能进行两数相加的计算。程序设计员的作用在于编好完整的指令，换句话说，要编好完整的算法。当程序设计员责怪其程序中的错误时，他的意思是指在编写详尽算法或把算法译成计算机语言时，他犯了一个错误。
必须强调的是，算法的用户不管是一部机器还是一个人，不需要对算法做出判断。例如，加法算法的使用，不需要“什么是数字”这一概念。要应用算法时，你可以盲目地按照法则进行。比方说，你不必知道，5是跟在4之后，7是大于3等等，甚至你也不必知道你是在使用十进制的数制。哲学文献中已有许多篇幅谈论过，就计算机的思考能力而言，缺乏判断会意味着什么。但是，探讨这样一个引人兴趣的说法则使我们离题太远了。
数学家们都不大关心旅行推销员这一专题。对于一系列较小的城市与公路网络，由于没有多少可能的路线需要审查，因而找到解法是很容易的。甚至对于大的城市与公路网络，那也可能幸运地或者偶然地找到最佳的路程。当数学家们宣称某问题实际上是不可解时，他们的意思是，仅仅知道保证解法的许多方法，就像穷举搜索所有可能性的方法一样低效，即使对于最高级的超级计算机来说，这种穷举搜索法也是太慢的。
数学的行家对于快速（与可用）的算法和慢速（与不可用）的算法都有严格的确定方法。假设数字n是某问题大小的量度（对于旅行推销员问题，n是城市与公路数目的量度）。对于快速的算法，随着计算问题规模的增大，完成算法所需的时间的增长不会大于n（表示计算规模）的某个多项式。多项式是一种数学函数，诸如2n（加倍）、3n（3倍）、n2（平方）、n3（立方）、3n10和64n100等。而对于慢速的算法，例如用于解旅行推销员问题的穷举搜索法，则其执行时间将按问题规模增加的指数增加，即2n、6n或12n等。
当n的值小时（也就是说，对于简单的问题），已知的多项式函数可以等于甚至超过已知的指数函数，但是当n的值大时，任何指数函数都将迅速地超过任何多项式函数。例如，当n等于2时，多项式函数n2等于4，它等于指数函数2n。但当n等于10时，n2只等于100，而2n却会像火箭上天那样猛增到1，024。毫无疑问，指数函数的增加会大大超过多项式函数的增加，这曾使托马斯。马尔萨斯感到忧虑，因为他发现人类的人口是以指数函数增长的，而与之相比，食物的供应则只以多项式函数增长。
解旅行推销员问题，仅有已知的一种方法是按指数减慢的方法，即审查所有可能旅程的方法，这一事实意味着，在当今这个年代里，我们已不能对看来如此简单的问题有真正的了解。综合性理论学家总想试图证明这个迷惑人的猜想：不管我们如何努力尝试，我们对它都不会有任何了解，因为它就是不能理解的。
看来与旅行推销员问题似乎有点相似的许多问题，数学家们对它们已经有所了解。例如，请考虑，一位公路检查员，他负责检查某段公路网，旅行推销员可能就在这段公路网上驱车。这位检查员渴望回家去看妻子和孩子，他想知道，是否有一条来回的路程，只须经过每条马路一次，只经过一次。但他并不关心城市，他只是想自己能走过公路的每个路段，而且还不重复。而从另一方面来说，旅行推销员却不关心公路，他只想去每个城市，每个城市只去一次，这样可把其汽车里程减到最短。
伦哈德。欧拉1736年的研究工作，轻而易举地回答了公路检查员的问题。欧拉是一位29岁的普鲁士数学奇才。原普鲁士城市柯尼斯堡（现为苏联城市加里宁格勒）位于普雷盖尔河的两岸，并且包括克尼霍夫岛以及河流岔口中部的一块狭长陆地。城市的4个区域由7座桥梁的网络连接起来。
据说，伊曼纽尔。坎特习惯于环绕城市进行长路程的保健散步运动，而且居民们也都想知道，是否可能有一条进行散步的来回路线，可以穿过所有7座桥梁，而每座桥梁只能穿过一次。由于桥梁的数目很小，这个问题可以用列举所有可能路线的方法（否定的方法）去求解，也就是说采用类似于旅行推销员这个小问题的、没有预见性的穷举法。
这个问题由多产数学家欧拉去解，欧拉是一位有13个孩子的父亲，同时还著有80本书的数学研究成果。传说，许多研究报告都是在第一次与第二次叫他去吃饭之间的30分钟时间内写出来的，他预见性地证明这种路程问题无解。数学的灵魂大力提倡分析最普通的例子。因此，欧拉不仅想为柯尼斯堡的居民，也想为各地喜欢桥梁散步的人们解决问题，他试图解答一个普遍性的问题：“有若干河流及其分支穿过某一地区，并在其上架设任意数量的桥梁，已知河流与桥梁的布局，求是否有可能在每座桥梁只穿过一次的情况下，穿过所有的桥梁。”如果你把陆地区域看成城市，把桥梁看成公路，那么你就可以认为，这个一般性问题与公路检查员所面临的问题相同。
为了解柯尼斯堡桥梁问题，欧拉用几何线表示每座桥梁，用几何点表示每块陆地。
在这幅图中，欧拉已把问题简化成基本线条，去掉了所有无关紧要的内容。比方说，线与点的表示无法区别桥梁是宽还是窄，是特定的桥梁还是连接同一陆地区域的其他桥梁，是大块陆地还是小块陆地，乃至是岛屿还是河岸等。这些区别也许在其他方面非常重要，但与穷举的非重复性散步方法无关。这是一种漂亮的数学表示法：它仅需要在手边保留那些有关的情况，从而使数学家免受枝节问题的干扰，更能集中注意力于问题本身。
欧拉已能证明，只有当点（陆地区域）为0或2，形成的线（桥梁）为奇数时，才可以进行穿过所有桥梁的非重复散步。你只要稍加思考就可支持这一结论。如果你穿过一座桥梁到另一处陆地去，必须还有一座桥梁让你离去，否则你将被困在那里。大片陆地需带有偶数桥梁才能确保那里有一条进去的路，另有一条离去的路。要是大片陆地只带有奇数的桥梁，那只有在旅程的终点（在那里你不需要一座桥梁离去）和旅程的起点（在那里你不需要一座桥梁进去）才有可能进行非重复的旅行。由于只有一个起点和一个终点，因此只有两处陆地才能有奇数的桥梁。在柯尼斯堡，4处陆地区域的每一处都连接了奇数的桥梁，即使没有比较严格的来回旅程条件，那么完全的非重复散步显然是不可能的。
欧拉关于任意数桥梁与任意数陆地区域的结论要比归纳成普通的常识重要得多，认识到这一点很重要。我们的推论只是简要地说明，如果欧拉所断定的条件不能够满足，则非重复的旅行将是不可能的。欧拉的结论是很强有力的，直观上却不是很明显的：他证明了，如果这一简单条件得到满足，也就是说，当陆地区域数为0或2，而且连接它们的桥梁数为奇数时，非重复的行程总是可能的。
要把欧拉的分析应用于一般情况，需要数出每处陆地区域的桥梁数。由于每座桥梁都要连接两处陆地区域，因此桥梁要两倍计数。如果桥梁数为n，那么欧拉的分析需要2n个步骤。桥梁的计数可以作为一种算法列出公式，而且它将成为一种非常有效的算法，因为虽然问题变得越来越复杂，演算所花费的时间却仅多了一倍。而从另一方面看，所有可能旅程的穷举搜索法则将成指数地迅速增长为2n。在旅行推销员问题中，对效率很低的穷举搜索法仍无简捷的方法。比方说，你仍不能计数出连接于每条公路的城市数，并根据这些数是奇数还是偶数来做出某种结论，或者就此而言，也不能根据这些数的其他性质得出结论。而且，这还不仅是我们不知道寻求那些性质的问题。还有可能是这些性质本来就不存在。这正是综合性理论学家都在努力证明的问题。
旅行推销员问题不仅仅是惟一的计算问题，许多数学家都不理解其快速算法。还有一整套叫做NP…完全的问题，对于这类问题，人们仅知道其计算所需时间以指数方式激增。①在NP…完全的问题中，另有一个众所周知的例子称为人群问题：已知有一大群人，比方说，共100人，他们之间是否有许多人，比方说，有50个人，全都彼此认识吗？
“你可以解这种问题，”美国麻省理工学院综合性理论学家迈克尔。赛普泽说道，“先投出 100个点，每点表示一个人，然后在相应的彼此认识的两人的点之间划一直线。”于是你将希望这组的50个点全都有连线。赛普泽接着又说：“看起来它很像一个有关计算机方面的重大问题，然而它不是。我们知道，如何去解这种问题，仅有的一种方法实质上是查看50人小组的所有连线，它们的数量非常多，就像10的29次方。要解出这个问题，即使应用快速的计算机，也要好几百年。”
旅行推销员的问题、人群问题、以及所有其他NP…完全的问题，都有难以理解的共同特点：如果有人声称，他对于这类问题中的任何一个特殊事例已经有了解法，那么要检验这个解法则是很容易的事。对于旅行推销员问题，只要检查所提出的旅程，并查明是否包括了每个城市一次。对于人群的问题，则要双向检查已被辨认全都互相认识而成群体的50个人。美国伯克利市加利福尼亚大学计算机科学教授理查德。卡普把 NP…完�