优化算法

　　优化算法

　　AndrewBoyd（安德鲁·博伊德）文 姜小龙译

　　早晨你发现上班路被封闭了，更糟的是许多相关路线都在维修，很难快速比较确定最短路径。没关系，你可以用电脑访问一个网站，寻问：家与办公室最短路径。网站秒算给出答案。如果你输入信息准确，程序将为你提供最短的路线。

　　网上程序是怎样计算出最佳路径的？算法并非计算出所有可能路径，然后比较出最短路线。即使借助计算机，这种穷尽算法在休斯敦这类城市，计算时间大约与地球年龄一样长。

　　网上程序使用一种特殊优化计算方法，只要所谓“最佳”被清晰定义出来，任何类似问题都能得到解决。

　　上班最短路线这类问题算法，与人们常用方法相似，先猜试一条路，然后改变路径与其比较，重复上述方法直到没有更近路线。人们会先选一条看上去不错的路线，然后不断试探不同捷径，直到你找不到更好路径了。但是你如何证明你找到路线是最短的呢？也许存在一条更短路径。与人尝试不同的是，优化程序不仅算出最短路径，同时证明没有更短的路线存在。最短距离问题算法不仅保证没有更短路线，同时计算速度非常之快。

　　并非所有问题都能找到最短距离这么简单的算法。以旅行商问题为例，商人寻找最短的路线，去拜访一个城市里所有的顾客。似乎我们可以用上述两点之间最短距离类似方法去解决这个旅行商问题，实际上最佳解决方案是非常之难。至今没有一个简单算法可以解决旅行商路径难题。

　　如果你难以理解这两个问题的巨大差别，这也是很正常的。半个世纪以来，许多最聪明的数学家试图证明旅行销售员问题与最短二点之间距离问题一样简单。但是迄今为止，尝试者全部铩羽而归。

　　在更普遍层面，旅行商问题在理论计算机科学领域被视为最重要难题。如果该难题能借助计算机快速解决，类似成千上万问题也将迎刃而解，每年可以为世界经济节省几千亿美元。解决问题算法是双刃剑，它可能危及现行网上交易，从而对世界金融体系造成巨大威胁。由于问题解决意义如此重大，解题奖金高达一百万美元，仅有6个教学难题有如此高的奖金。但是数学家会告诉你，使他们着迷的不仅仅是赢得巨额奖金，更重要的是为了挑战这个同行髙手认为“难于上青天”的难题。