「推销员问题」之谜初步解开

【英国《金融时报》５月２８日文章】题：数学领域中的推销员问题
英国电信公司科学家说，名为“出差推销员问题”的数学谜题可能已被揭开神秘的面纱。
他们承认尚没有实际解决该问题，只是找到了使计算机能产生迄今为止最佳和最快路径的方式。
这个谜题虽然很简单，但是６０年来它一直困扰着世界上一些最有实力的科学家以及功能最强的电脑。这个谜题就是：一个推销员要前往３个、或４个、或１０个、或１００个地方。什么是最短的、或者说是最佳的路线？
在去３个地方的情况下，有６种可能路线。１０个地点时，则有３６２８８００种可能路线。１００个地点时，可能的路线则有１０。
由英国电信公司实验所沙拉·阿米和乔斯·马丁创造的目前最佳的方法，在１．６秒时间内可以走遍１００个地方。走完１０００个地方，也不超过３分钟。
他们说，这项答案将发表在７月号的《神经计算技术》杂志上。他们将不会披露所用的算法，但是其他数学家会发现如何着手工作的线索。
该技术还能用于军事目的。英国电信公司实验所的彼得·库克雷恩教授说，可以想象，当一名喷气式飞机驾驶员同时受到地对空导弹和敌机攻击时，“你所要解决的是电脑空间问题。这就是：确定前进方向；先打击什么目标和攻击顺序，以求将自己的危险降至最低和最大限度地杀伤敌人”。但是该技术的现时价值则在于设计计算机电路分布。