📄 10.htm
字号:
image7a=new Image(); image7a.src="../.././image/bbs1.gif";
image7b=new Image(); image7b.src="../.././image/bbs2.gif";
image8a=new Image(); image8a.src="../.././image/link1.gif";
image8b=new Image(); image8b.src="../.././image/link2.gif";
</SCRIPT>
</head>
<!-- 文件头结束，正文部分开始 -->
<body bgcolor=white leftmargin="0" topmargin="0" marginwidth="0" marginheight="0" link=black alink=blue vlink=darkslateblue>
<!-- 表格1，页面最顶端的内容 -->
<table width=780 border="0" cellspacing="0" cellpadding="0">
<tr><td height=23 bgcolor=gray width="80%"><font color="#FFFFFF" class=p4> <b><a href="../../index.html" class=v2>Home</a>
| <a href="../../news.htm" class=v2>News</a> | <a href="../../mag.htm" class=v2>Magazine</a> | <a href="../../lib.htm" class=v2>Library</a> | <a href="../../ency.htm" class=v2>Encyclopedia</a> | <a href="../../review.htm" class=v2>Review</a> | <a href="../../essay.htm" class=v2>Essay</a> | <a href="http://bbs.oursci.org" class=v2>Forum</a> </font></b></td>
<td bgcolor=gray width="20%"><b>
<!-- 调用日期函数 -->
<div align="right"><font class=p4 color="#FFFFFF">2002<script language=JavaScript>document.write(rq);</script></font></div></b>
</td></tr></table><!-- 表格1结束 -->
<!-- 表格2，主LOGO上半部分及页面上方深底色区域 -->
<table width=780 border="0" cellspacing="0" cellpadding="0">
<tr><td background="./image/ban2.gif" width="100%" align=left>
<a href="../../index.html"><img src="archimedes1.gif" alt="返回首页" border=0></a></td>
</table><!-- 表格结束 -->
<!-- 表格3开始，主LOGO下半部分及蓝灰色过渡 -->
<table width=780 border="0" cellspacing="0" cellpadding="0" cols=2>
<tr>
<!-- 表格3左第一列，深色背景及主要栏目 -->
<td width=15% align=left valign=top bgcolor=white class=p1>
<table width="100%" border="0" cellspacing="0" cellpadding="0"><tr><td width=120>
<a href="../../index.html"><img src="archimedes2.gif" border=0></a></tr></td></table> <!-- 主LOGO下半部分>
</td>
<!-- 表格3左第1列结束，第2列开始 -->
<td with=85% class=p1 valign=top align=left>
<!-- 深底色与白色之间的灰蓝过渡色 -->
<table width="100%" border="0" cellspacing="0" cellpadding="0" cols=3>
<tr><td height=20 background="ban5.gif" width=20 class=p1 align=right>您</td><td bgcolor=lightsteelblue width=449 class=p1>所在的位置：三思→三思藏书架→<a href="index.htm" class=v1>阿基米德的报复</a></td><td width=190 bgcolor=lightsteelblue></td></tr>
<tr><td width=20 height=45 class=p1 align=right></td><td bgcolor=white width=449></td><td width=190 bgcolor=white background="ban6.gif"> </td></tr>
</table>
</td></tr></table> <!-- 表格3结束 -->
<!-- 表格4，网页主体内容开始 -->
<table cellpadding=0 cellspacing=0 border=0 width=780 cols=3>
<!-- 表格4第1列，正文左边的白边 -->
<tr><td width=40 bgcolor=white rowspan=2></td>
<!-- 表格4第2列，正文 -->
<td width=550 align=left class=p1>
<font class=p2>
<center><font color=green class=p3>第九章 威利·洛曼无辜地死去了吗？
</font><br><br><br>
</center><br><br>
从某种基本意义上讲，计算机和数学家只是不容易识别的图灵计算机，知道这一点也许令人泄气。但在另一方面，从表面上看过于简单的图灵计算机，由于证明能够解各种各样的计算问题，从而又可被认为是鼓舞人心的。数学家与计算机之间理论上的相似性不仅适用于他们能解出的各种问题，而且也适用于他们不能解出的各种问题。<br><br>
工业上每天都出现许多计算问题，若用任何已知的方法去解，则太费时间，现在都例行地由计算机去着手解决。然而工业需要的是对这些问题的解法，而计算机常常牵扯到程序设计人员的水平，他们往往不能编出最佳程序。其中有许多是众所周知的使旅行推销员感到为难的问题；已知一个城市与公路网络，要找一条推销员在往返旅程中到每个城市去一次的最短路线。仅有一种已知的算法用来解这种旅行推销员问题，就是可靠的逐步试探法，这种方法费力，缺乏预见性，只是对每一种可能性都进行尝试。看来，数学并未减轻威利·洛曼的烦恼。<br><br>
过去15年内，数学家们都感到迷惘，他们寻求巧妙的、较快的算法都告失败，这是由于他们无知呢，还是这种问题本身存在内在的困难？按照当前的知识水平，暂时还没有较快的算法，甚至在理论上也没有。目前还没有人能够证明这一点。对证明的研究已是理论计算机科学中最为热门的课题，而且在这个领域中工作的数学家已被公认为是复合型理论学家。<br><br>
当数学家们谈到保证解题方法时，他们的意思就是指算法。不要由于“算法”（algorithm）这个英语单词的发音令人生畏而摈弃它，它是9世纪波斯数学家阿布·贾法尔·穆罕默德·伊本穆萨·阿尔霍瓦里米的姓氏音译转讹而来的，他的语义遗产还包含有单词代数（algebra）在内。算法的音难读但不难懂。你早已了解什么是算法的直观概念。<br><br>
你可曾记得，在你读小学时，你的英语老师让你制定出一整套令人厌烦的规定，去做诸如系鞋带一类枯燥无味的琐事，然后老师叫约翰尼·怀斯盖严格按照你的规定去系他的鞋带（与此同时，这个讨厌的老师还会让你大声念你的那一套规定）。<br><br>
当然，他会立即出错——而且是个大错——因为你没有考虑一些看来好像是理所当然不成问题的基本步骤，就像系鞋带时理所当然要握住鞋带的塑料包头，而不是握住它的中部一样。如果你详详细细地写出，那么你就会得到一个有关系鞋带的规则系统，而这个规则系统不过是一个循序渐进的程序，在这个程序中，每一步都说得很明确，你可以按部就班地解决每个问题。每个步骤都要规定得清清楚楚，其间不允许留下任何靠可能、直觉、经验、解释或想象等方法来处理的细节。<br><br>
当然，数学家们对于计算问题的算法要比系鞋带更感兴趣。两个整数相加的算法，根据小学老师教给我们的方法，是用纸和铅笔按照如下的明确步骤进行：把整数写成一行，一个数写在另一个数的上方，两数右端对齐，在它们下方划一横线，从右到左地进行计算，有时还“进位”1，而且照此步骤计算许多其他数的相加，也是不成问题的。这种算法应该包括如下法则，像“如果一个数2在另一个数4的上方，可在其下写一个数6”和“如果一个数3在另一个数6的上方，可在其下写一个数9”等法则。<br><br>
算法的功能之一是其能用于一个问题的所有实例。例如加法算法可以算出任何两个整数的和。你虽然花费时间去详尽写出一种算法的全部细节，但你却得到了一种能够保证工作的方法。计算机的程序或是单一的算法或是系列的算法。如果没有指令告诉该算法的每一步骤应该做些什么，那么计算机就同不能模拟系好鞋带一样，也不能进行两数相加的计算。程序设计员的作用在于编好完整的指令，换句话说，要编好完整的算法。当程序设计员责怪其程序中的错误时，他的意思是指在编写详尽算法或把算法译成计算机语言时，他犯了一个错误。<br><br>
必须强调的是，算法的用户不管是一部机器还是一个人，不需要对算法做出判断。例如，加法算法的使用，不需要“什么是数字”这一概念。要应用算法时，你可以盲目地按照法则进行。比方说，你不必知道，5是跟在4之后，7是大于3等等，甚至你也不必知道你是在使用十进制的数制。哲学文献中已有许多篇幅谈论过，就计算机的思考能力而言，缺乏判断会意味着什么。但是，探讨这样一个引人兴趣的说法则使我们离题太远了。<br><br>
数学家们都不大关心旅行推销员这一专题。对于一系列较小的城市与公路网络，由于没有多少可能的路线需要审查，因而找到解法是很容易的。甚至对于大的城市与公路网络，那也可能幸运地或者偶然地找到最佳的路程。当数学家们宣称某问题实际上是不可解时，他们的意思是，仅仅知道保证解法的许多方法，就像穷举搜索所有可能性的方法一样低效，即使对于最高级的超级计算机来说，这种穷举搜索法也是太慢的。<br><br>
数学的行家对于快速（与可用）的算法和慢速（与不可用）的算法都有严格的确定方法。假设数字n是某问题大小的量度（对于旅行推销员问题，n是城市与公路数目的量度）。对于快速的算法，随着计算问题规模的增大，完成算法所需的时间的增长不会大于n（表示计算规模）的某个多项式。多项式是一种数学函数，诸如2n（加倍）、3n（3倍）、n<sup>2</sup>（平方）、n<sup>3</sup>（立方）、3n<sup>10</sup>和64n<sup>100</sup>等。而对于慢速的算法，例如用于解旅行推销员问题的穷举搜索法，则其执行时间将按问题规模增加的指数增加，即2<sup>n</sup>、6<sup>n</sup>或12<sup>n</sup>等。<br><br>
当n的值小时（也就是说，对于简单的问题），已知的多项式函数可以等于甚至超过已知的指数函数，但是当n的值大时，任何指数函数都将迅速地超过任何多项式函数。例如，当n等于2时，多项式函数n<sup>2</sup>等于4，它等于指数函数2<sup>n</sup>。但当n等于10时，n<sup>2</sup>只等于100，而2<sup>n</sup>却会像火箭上天那样猛增到1，024。毫无疑问，指数函数的增加会大大超过多项式函数的增加，这曾使托马斯·马尔萨斯感到忧虑，因为他发现人类的人口是以指数函数增长的，而与之相比，食物的供应则只以多项式函数增长。<br><br>
解旅行推销员问题，仅有已知的一种方法是按指数减慢的方法，即审查所有可能旅程的方法，这一事实意味着，在当今这个年代里，我们已不能对看来如此简单的问题有真正的了解。综合性理论学家总想试图证明这个迷惑人的猜想：不管我们如何努力尝试，我们对它都不会有任何了解，因为它就是不能理解的。<br><br>
看来与旅行推销员问题似乎有点相似的许多问题，数学家们对它们已经有所了解。例如，请考虑，一位公路检查员，他负责检查某段公路网，旅行推销员可能就在这段公路网上驱车。这位检查员渴望回家去看妻子和孩子，他想知道，是否有一条来回的路程，只须经过每条马路一次，只经过一次。但他并不关心城市，他只是想自己能走过公路的每个路段，而且还不重复。而从另一方面来说，旅行推销员却不关心公路，他只想去每个城市，每个城市只去一次，这样可把其汽车里程减到最短。<br><br>
伦哈德·欧拉1736年的研究工作，轻而易举地回答了公路检查员的问题。欧拉是一位29岁的普鲁士数学奇才。原普鲁士城市柯尼斯堡（现为苏联城市加里宁格勒）位于普雷盖尔河的两岸，并且包括克尼霍夫岛以及河流岔口中部的一块狭长陆地。城市的4个区域由7座桥梁的网络连接起来。<br><br>
<img src=10-01.gif><br><br>
据说，伊曼纽尔·坎特习惯于环绕城市进行长路程的保健散步运动，而且居民们也都想知道，是否可能有一条进行散步的来回路线，可以穿过所有7座桥梁，而每座桥梁只能穿过一次。由于桥梁的数目很小，这个问题可以用列举所有可能路线的方法（否定的方法）去求解，也就是说采用类似于旅行推销员这个小问题的、没有预见性的穷举法。<br><br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -