10.htm

阿基米德的报复

　　这个问题由多产数学家欧拉去解，欧拉是一位有13个孩子的父亲，同时还著有80本书的数学研究成果。传说，许多研究报告都是在第一次与第二次叫他去吃饭之间的30分钟时间内写出来的，他预见性地证明这种路程问题无解。数学的灵魂大力提倡分析最普通的例子。因此，欧拉不仅想为柯尼斯堡的居民，也想为各地喜欢桥梁散步的人们解决问题，他试图解答一个普遍性的问题：“有若干河流及其分支穿过某一地区，并在其上架设任意数量的桥梁，已知河流与桥梁的布局，求是否有可能在每座桥梁只穿过一次的情况下，穿过所有的桥梁。”如果你把陆地区域看成城市，把桥梁看成公路，那么你就可以认为，这个一般性问题与公路检查员所面临的问题相同。<br><br>
<img src=10-02.gif><br><br>
　　为了解柯尼斯堡桥梁问题，欧拉用几何线表示每座桥梁，用几何点表示每块陆地。<br><br>
　　在这幅图中，欧拉已把问题简化成基本线条，去掉了所有无关紧要的内容。比方说，线与点的表示无法区别桥梁是宽还是窄，是特定的桥梁还是连接同一陆地区域的其他桥梁，是大块陆地还是小块陆地，乃至是岛屿还是河岸等。这些区别也许在其他方面非常重要，但与穷举的非重复性散步方法无关。这是一种漂亮的数学表示法：它仅需要在手边保留那些有关的情况，从而使数学家免受枝节问题的干扰，更能集中注意力于问题本身。<br><br>
　　欧拉已能证明，只有当点（陆地区域）为0或2，形成的线（桥梁）为奇数时，才可以进行穿过所有桥梁的非重复散步。你只要稍加思考就可支持这一结论。如果你穿过一座桥梁到另一处陆地去，必须还有一座桥梁让你离去，否则你将被困在那里。大片陆地需带有偶数桥梁才能确保那里有一条进去的路，另有一条离去的路。要是大片陆地只带有奇数的桥梁，那只有在旅程的终点（在那里你不需要一座桥梁离去）和旅程的起点（在那里你不需要一座桥梁进去）才有可能进行非重复的旅行。由于只有一个起点和一个终点，因此只有两处陆地才能有奇数的桥梁。在柯尼斯堡，4处陆地区域的每一处都连接了奇数的桥梁，即使没有比较严格的来回旅程条件，那么完全的非重复散步显然是不可能的。<br><br>
　　欧拉关于任意数桥梁与任意数陆地区域的结论要比归纳成普通的常识重要得多，认识到这一点很重要。我们的推论只是简要地说明，如果欧拉所断定的条件不能够满足，则非重复的旅行将是不可能的。欧拉的结论是很强有力的，直观上却不是很明显的：他证明了，如果这一简单条件得到满足，也就是说，当陆地区域数为0或2，而且连接它们的桥梁数为奇数时，非重复的行程总是可能的。<br><br>
　　要把欧拉的分析应用于一般情况，需要数出每处陆地区域的桥梁数。由于每座桥梁都要连接两处陆地区域，因此桥梁要两倍计数。如果桥梁数为n，那么欧拉的分析需要2n个步骤。桥梁的计数可以作为一种算法列出公式，而且它将成为一种非常有效的算法，因为虽然问题变得越来越复杂，演算所花费的时间却仅多了一倍。而从另一方面看，所有可能旅程的穷举搜索法则将成指数地迅速增长为2<sup>n</sup>。<br><br>
　　在旅行推销员问题中，对效率很低的穷举搜索法仍无简捷的方法。比方说，你仍不能计数出连接于每条公路的城市数，并根据这些数是奇数还是偶数来做出某种结论，或者就此而言，也不能根据这些数的其他性质得出结论。而且，这还不仅是我们不<b>知道</b>寻求那些性质的问题。还有可能是这些性质本来就不存在。这正是综合性理论学家都在努力证明的问题。<br><br>
　　旅行推销员问题不仅仅是惟一的计算问题，许多数学家都不理解其快速算法。还有一整套叫做NP-完全的问题，对于这类问题，人们仅知道其计算所需时间以指数方式激增。<sup>①</sup>在NP-完全的问题中，另有一个众所周知的例子称为人群问题：已知有一大群人，比方说，共100人，他们之间是否有许多人，比方说，有50个人，全都彼此认识吗？<br><br>
　　“你可以解这种问题，”美国麻省理工学院综合性理论学家迈克尔·赛普泽说道，“先投出   100个点，每点表示一个人，然后在相应的彼此认识的两人的点之间划一直线。”于是你将希望这组的50个点全都有连线。赛普泽接着又说：“看起来它很像一个有关计算机方面的重大问题，然而它不是。我们知道，如何去解这种问题，仅有的一种方法实质上是查看50人小组的所有连线，它们的数量非常多，就像10的29次方。要解出这个问题，即使应用快速的计算机，也要好几百年。”<br><br>
　　旅行推销员的问题、人群问题、以及所有其他NP-完全的问题，都有难以理解的共同特点：如果有人声称，他对于这类问题中的任何一个特殊事例已经有了解法，那么要检验这个解法则是很容易的事。对于旅行推销员问题，只要检查所提出的旅程，并查明是否包括了每个城市一次。对于人群的问题，则要双向检查已被辨认全都互相认识而成群体的50个人。美国伯克利市加利福尼亚大学计算机科学教授理查德·卡普把  NP-完全的问题比作拼图玩具：“它们可能难于组合，但是当有人向你展示一幅完全的拼图时，你就能一下子知道问题已有正确解。”<br><br>
　　NP-完全的问题还有一个醒目的特点，如果这类问题中的任何一个问题能够用快速算法求解，那么其他问题也都能用此法解出。而且，对于某类NP-完全问题采用快速算法毫不费力，而且稍加改进，就可用于解任何其他NP-完全问题。例如，如果人们发现了一种用于解旅行推销员问题的快速算法，那么数学家们就会自如地运用快速方法去解人群问题和所有其他的NP-完全问题。因此，旅行推销员问题是否有快速解法与NP-完全问题是否真的像看上去那样难这一较大问题有关。<br><br>
　　美国电话电报公司的戴维·约翰逊说道：“我认为，现在每位数学家实际上都认为NP-完全问题有内在的困难。”约翰逊是这一领域的权威人士，著有《计算机和难处理性：NP-完全理论指南》一书。他还说：“真正的问题是证明它。”<br><br>
　　这种论点动摇了一些数学家的想法，他们认为他们也许能够证明旅行推销员问题及同类的其他问题都不会有快速解法——从来就没有过——即使未来让爱因斯坦一类大师来绞脑汁也不会有。他们怎么会提出要证明这样的问题？<br><br>
　　目前的工作都集中在逻辑门上，它已被认为是计算机硬件中最基本的单元。在电子计算机内，逻辑门是一种组件，由任意数目的输入引线与一根输出引线组成。逻辑门也是一种二进制器件：每根引线中的信号都被认为或是1、或是0。（在电子学术语中，高电平对应于1，低电平对应于0。）<br><br>
　　每一个逻辑门都能完成3种基本运算中的1种：“非”、“与”或“或”。这3种运算的名称都是根据布尔代数中已经使用的词“非”、“与”和“或”而得来的。布尔代数是19世纪40年代由乔治·布尔研究出来的一种开拓性的形式逻辑体系。布尔是一个贫穷补鞋匠的儿子，他自学数学，研究出符号逻辑体系，其中1表示真的，0表示假的。尽管布尔的研究工作使他获得了爱尔兰科克大学的数学教授职位，但直到100多年后第一部电子计算机问世之后，他的逻辑体系才得到数学界的完全赏识。<br><br>
　　在形式逻辑中（和日常的英语中），词“非”加在前面可把真语句变成假语句，而且反过来也一样。把它换成布尔代数的术语，则是“非”可把1转换为0，0转换为1。因此，“非”逻辑门有一根输入引线，并把输入信号转变为其相反信号，即如果输入是1，则输为0，而如果输入为0，则输出就为1。<br><br>
<img src=10-03.gif><br><br>
　　当然，词“与”用于连接单个语句成为复合语句，即如果每个组元都是真的，那么复合组元也是真的。现举一简单例子，“朱尔斯吃豆腐与吉姆吃多夫条形面包”，只有当朱尔斯和吉姆两个人都在吃上述的食物时，它才是一个真实语句。由于同样的理由，“与”门可接受两个或多个信号输入，如果所有的输入都是1时，那么输出也是1，否则，则输出为0。<br><br>
<img src=10-04.gif><br><br>
　　词“或”也是用于连接语句成为复合语句，但只要一个或几个组元都是真的，则其复合组元也是真的。如果朱尔斯或者吉姆（或者他们两人）在吃他们各自的食物，那么“朱尔斯吃豆腐或吉姆吃多夫条形面包”才是真语句。同样地，“或”门可以接受两个或几个信号输入，但只要至少输入之一是1时，则其输出也是1。<br><br>
<img src=10-05.gif><br><br>
　　布尔代数的绝妙之处在于，1和0不仅表示真的和假的，而且还可以表示任何两种不同的状态。例如在旅行推销员问题中，0和1可以表示城市之间的相应关系：如果两个城市由一条公路连接，则以1表示，如果它们没有公路连接，则以0表示。在人群的问题中，1可以表示两个人成为朋友的状态（或者在该问题的图解表示法中，表示由一条线连接的两点），0表示他们不是朋友的状态（表示没有线连接的两点）。<br><br>
　　在计算机中，任何数目的“与”门、“或”门和“非”门都可以连接在一起，形成一种电路。例如下图示出4个“与”门和1个“或”门组成的一种小型电路，它可以用来求解人群问题的普通实例：在4个人的一组中，有3个人是朋友吗？<br><br>
<img src=10-06.gif><br><br>
　　然而，随着人群问题的人数增加，用于已知解法的电路大小（也是逻辑门的数目）将按指数方式激增。如果数学家们能够证明，对于任何可能已知或未知解法，电路必按指数方式增大，那么他们就能证明人群问题没有快速算法。<br><br>
　　数学家们还不知道如何开始这样的证明，已经转而考虑另一特殊的问题，这就是通常都有快速算法的奇偶函数，而且他们还试图以某些基本方式来限制电路，使得快速算法不再产生作用。（奇偶函数可在一串的0与1中确定是否产生偶数或奇数。）这种方法看来也许有些怪，其实它并不怪。数学家们对于如何证明电路必须是大型的了解甚少，因此为此目的而做的任何证明，甚至是某种人为的情况，也都将会有所进展，而且可以提供证明真正论点所需的数学工具。赛普泽说道：“这是数学中的普通方法。如果问题很大，可试图把它限制到某些范围，并求解其中一部分，希望这种分部解法使人们对原来的问题会有更深的了解。”<br><br>
　　在这一领域内，早期的工作限制了电路的研究工作的深度，这里的深度是指逻辑门的层次数目。1981年取得了第一批成果，当时美国卡内基-梅隆大学的赛普泽及其两位同事证明了，如果他们限制用于奇偶函数的电路深度，那么电路宽度的扩展快于任何多项式。1985年，美国斯坦福大学的安德鲁·姚在这方面取得了更惊人的研究成果，他证明了电路的宽度不仅以超多项式的方式扩展，而且还以指数的方式扩展，这表明这种问题虽然受到人为的限制，但也有内在的困难。<br><br>
　　姚的成果很快地传遍了数学界。赛普泽这样说道：“每个人都认为这个结果很满意，但也是非常复杂的。”姚的方法为他人铺平了道路，好几个研究人员很快地对他的结果做了改进。美国电话电报公司贝尔实验室数学科学部主任罗纳德·格雷厄姆说：“这很像开车的头4分钟路程，一旦有人学会它，那么人人都可以学会它。”<br><br>
　　1985年8月，美国麻省理工学院计算机学科研究生约翰·哈斯特德采用了姚的基本理论，但是简化了他的论据。哈斯特德说道：“在工作过程中，我获得了比较有力的结果。（在这种有限制的问题中）我们所知道如何设计的最小电路并不比我在理论上曾经证明它们应有的规模大出很多。”后来的证明都表明：数学家们实际上知道如何设计出并不比他们在理论上所推断的最佳电路差很多的电路。对于这些有限制的问题来说，不是数学上的无知，而是问题的本身排除了快速的解法。<br><br>
　　苏联莫斯科大学的两位数学家阿·拉兹波洛夫和阿·安德烈耶夫在不限制电路深度但却限制所进行的运算方面取得了很大的成功。拉兹波洛夫又证明了如果不允许用“非”门的话，则用于人群问题的电路规模的增长将快于任何多项式的增长。而且，数学家们还在这里对这一结果做了改进，它表明电路必须是按指数方式增大。安德烈耶夫通过禁止用“非”门还能够证明另一类问题也需要大规模电路。<br><br>
　　这些成就使这一领域乐观起来，虽然还没有人知道怎样才能减少对电路的限制并证明在无限制的情况下，旅行推销员的问题的确很难。“还有很长的路程要走，”赛普泽这样说道，“6年以前，我曾与人打过赌，我希望他还记住，将在2000年得出证明。我仍然信心十足，还有12年多的时间。”格雷厄姆还抱有更大的希望：“在以后3年内得到证明也不会让我吃惊。”<br><br>
　　尽管人们普遍乐观，但在综合性理论方面（数学的一个分支学科，它表述了问题的难度）的研究人员，以他们的直觉已经知道他们会失败的。1985年冬天，美国麻省理工学院的数学研究生戴维·巴林顿曾证明，计算机能够运算的某些原始表示法会比该领域中任何人所能设想的更有功效。这种原始表示法不包含“与”门、“或”门和“非”门，但却包含一个分支门，它也有两根输出引线。当分支门受到触发时，如果输入信号具有一定的指定值，则分支门就会沿两根引线之一送出一个信号；对于所有其他输入信号，分支门沿另一根引线送出一个信号。换句话说，分支门能够处理计算机程序中的语句，诸如“如果x=5，转向步骤4；对于所有其他x，转向步骤7”。<br><br>
　　巴林顿又证明了，全部由门层次不超过5层的分支门构成的电路，可以解所谓的多数问题：在一串的0和1中，1是不是多数？综合性理论学家普遍地（并且错误地）认为分支门限制于任何固定高度，不可能求解多数问题，更不用说严苛的五层限制了。<br><br>
　　巴林顿说道：“我的证明很简单，但它令人惊奇，因为他们总是认为我所试图证明的都是假的。”巴林顿的结果也许没有多少实际用途——他又说：“除了它可以让我在一所好大学获得一个教师职位之外。”而且它还可以说服数学家们不要在复杂的综合性理论领域中如此自信。<br><br>
________<br>
　　① 如果你一定要知道的话，NP表示非决定性的多项式，而complete一词则意味着这些问题是该类问题中最难的。  
<br><br>
<div align=right><A HREF="index.htm" class=v1>回本书目录</a> | <A HREF="09.htm" class=v1>上一节</a> | <A HREF="11.htm" class=v1>下一节</a> | <a href="mailto:[e-mail]" class=v1>给编辑来信</a> | <a href="http://bbs.oursci.org" class=v1>三思科学论坛</a> | <a href="javascript:window.close()" class=v1>关闭窗口</a></div>
<br><br>
</td>

            <!-- 表格4第3列，正文右边的内容 -->
<td width=190 bgcolor=white background="ban6.gif" class=p1 valign=top>

  <table width=190 border="0" cellspacing="0" cellpadding="0" cols=2>
<tr><td width=35> </td>
<td width=155 class=p1>
<font color=thistle><b>本文有关信息：</b></font><br>
收录时间：2002.04<br>
作者：保罗·霍夫曼<br>
来源：转载<br><br><br>

<img src="hline.gif" height=1 width=150><br>
<font color=thistle><b>该作者其它作品：<br></b></font>
<br><br>

<img src="hline.gif" height=1 width=150><br>
<font color=thistle><b>其它相关阅读：<br></b></font>
<br><br>

<img src="hline.gif" height=1 width=150><br>
<font color=thistle><b>相关网站：<br></b></font>



</td></tr></table>

</td></tr></table></div>

<!-- 表格4结束 -->

<!-- 表格5，页面最下端部分 -->
  <table width=780 border="0" cellspacing="0" cellpadding="0">
    <tr> 
      <td bgcolor=gray align=center class=p4>         <font color="#FFFFFF"><font class=p4>
<a href="../../index.html" class=v2>首页</a> | <a href="../../copyright.htm" class=v2>版权声明</a> | <a href="../../map.htm" class=v2>本站导航</a> | <a href="../../about.htm" class=v2>关于本站</a> |  <a href="../../contact.htm" class=v2>联系我们</a>　&copy;1999-2002  
          <a href="http://www.oursci.org" class=v2>www.OurSci.org</a>,All Rights Reserved.　
</font></font>
   </td>   </tr>  </table>

</body></html>