迷茫的旅行商[试读]
1.1 环游美国之旅
它产生于三个人求解一道经典数学问题的研究工作。这个历史悠久的问题叫做“旅行商问题”，无论靠人工计算还是借助最快的计算机都一直无法解决。——IBM 新闻稿，1964 年① 1962 年春天，宝洁公司发起了一场广告宣传活动，在应用数学家中引起了不小的反响。活动的重头戏是一项竞赛，奖金高达1 万美元，在当时足以买下一座房子。参赛规则如下：假设Toody 和Muldoon 打算开车环游美国，地图上用点标出的33 个地点都要游览，并且要走满足条件的路线中最短的一条。请你为他们规划一条旅行路线，以伊利诺伊州的芝加哥市为旅途的起点和终点，依次用线连接各地点，并使得总里程最短。 Toody 和Muldoo... 查看全部[ 1.1 环游美国之旅 ]
1.2 不可能的任务吗
兰德小组的研究工作解决了环游美国48 州的难题，却没有彻底解决TSP。他们取得了一次巨大的成功，并不意味着就能搞定规模更大的题目。事实上，如果拉斯维加斯赌场把TSP 的最终结果作为一项赌博项目，那么在数学家看来，把赌注押在“TSP 永远无法彻底解决”上会有更大的胜算。对此，必须明确一点：我们要找的所谓解法（solution），实际上是算法（algorithm），也就是要求对于任何一道实例，只要按照算法一步一步计算，一定能求出最优路线。单单找到周游美国或者周游其他某国的最优路线是不够的。 所以，为一般形式的TSP 找到通用解法的难度可想而知。CharlesStross 在科幻小说《抗体》（An... 查看全部[ 1.2 不可能的任务吗 ]
1.3 循序渐进，各个击破
将来或许会有人一举攻破终极的复杂性问题，给出惊天动地的答案。在那之前，我们能做什么？直面旅行商问题，目标非常明确：求解更大规模、更难解决的情形。 TSP 是算法工程（algorithm engineering）①的代表问题。这门研究学科重视实用性，以不达目的誓不罢休为理念。理论上，TSP 的规模一旦大到一定程度，求解某些实例的计算量就可能高得离谱。但这并不代表只要看到规模很大的具体问题，就只能退而求其次，选择粗略估计作为结果。研究人员正是在这种绝不妥协的态度的推动下，不断改进计算机代码和技术方法，如今已能解决复杂度惊人的大问题。 在TSP 研究领域，如果有人攻克了一道未解难题，消息会迅速流... 查看全部[ 1.3 循序渐进，各个击破 ]
1.4 本书路线一览
图1-11 的T 恤衫图案出自Jessie Brainerd 之手，她曾参加2007 年的布达佩斯数学项目。①在应用数学专业或者计算机科学专业，每一名毕业不久的合格本科生都能一眼看出这幅图的主题就是TSP。按照许多大学的课程设置，学习旅行商问题都是必经之路。最近，甚至连美国的中学课本里都有该问题的简单介绍。 图1-11 2007 年万圣节的TSP（照片由Jessie Brainerd提供） ① 照片上身着T 恤衫的男生是Bill Kay。他是Jessie Brainerd 的同学，当时他们在布达佩斯参加万圣节晚会。Jessie Brainerd 在博客上写了一篇日志，提到晚会上还有... 查看全部[ 1.4 本书路线一览 ]
书名： 迷茫的旅行商
作者： [美] William J·Cook
出版社： 人民邮电出版社
原作名： In pursuit of the traveling salesman:Mathematics at the limits of computation
副标题： 一个无处不在的计算机算法问题
译者： 隋春宁
出版年： 2013-10-1
页数： 256
定价： 49.00
装帧： 平装
丛书： 图灵新知
ISBN： 9787115327734