迷茫的旅行商

内容简介：

假设一名旅行商打算拜访一张城市列表中的所有城市，每座城市只去一次，最后回到出发地。要怎么走才能让路线最短呢？这就是旅行商问题，乍一听很简单，在应用数学界却是一道研究极其热烈的难题，时至今日仍无人能解。本书中，William J. Cook将带领读者踏上一场数学之旅，跟随旅行商的脚步，从19世纪初爱尔兰数学家W. R. Hamilton最初定义该问题开始，一路奔向当今最前沿、最顶尖的解题尝试。

作者追根溯源，回顾了旅行商问题的历史，探索了它的种种重要应用，比如基因组测序、设计计算机处理器、整理音乐乃至搜寻行星等。他分析了计算机如何抗衡规模宏大的旅行商问题，探讨了人类如何在不借助计算机的情况下独立破解难题。他一路穿越神经科学、心理学与艺术的王国，向读者下了战书：试试解决这道难题吧！旅行商问题价值百万美元——这是克雷数学研究所的悬赏金额，只要解出该题或证明该题不可解，就能得到这笔奖金。

《迷茫的旅行商》介绍了人类对于复杂性本质的理解与局限，将激励读者从此踏上求解这道迷人难题的漫漫征程。

作者简介：

William J. Cook

加拿大滑铁卢大学教授，美国国家工程院院士，美国数学学会、美国工业与应用数学学会以及美国运筹学和管理学研究协会会员。主要研究领域为整数规划与组合优化，曾出版多部研究旅行商问题的专著，其中与人合著的The Taveling Salesman Problem：A Computational Study获2007年Lanchester奖。

目录：

第 1 章　难题大挑战1

1.1 　环游美国之旅2

1.2 　不可能的任务吗7

1.2.1 　好算法，坏算法8

1.2.2 　复杂度类P与NP10

1.2.3 　终极问题11

1.3 　循序渐进，各个击破12

1.3.1 　从49到85 90012

1.3.2 　世界旅行商问题15

1.3.3 《蒙娜丽莎》一笔画17

1.4 　本书路线一览18

第 2 章　历史渊源21

2.1 　数学家出场之前21

2.1.1 　商人21

2.1.2 　律师27

2.1.3 　牧师28

2.2 　欧拉和哈密顿30

2.2.1 　图论与哥尼斯堡七桥问题30

2.2.2 　骑士周游问题33

2.2.3 　Icosian图34

2.2.4 　哈密顿回路37

2.2.5 　数学谱系39

2.3 　维也纳—哈佛—普林斯顿40

2.4 　兰德公司43

2.5 　统计学观点45

2.5.1 　孟加拉黄麻农田45

2.5.2 　证实路线估计值47

2.5.3 　TSP常数47

第 3 章　旅行商的用武之地50

3.1 　公路旅行50

3.1.1 　数字化时代的推销员50

3.1.2 　取货与送货51

3.1.3 　送餐到家52

3.1.4 　农场、油田、蓝蟹53

3.1.5 　巡回售书53

3.1.6 “多走一里路”54

3.1.7 　摩托车拉力赛54

3.1.8 　飞行时间55

3.2 　绘制基因组图谱56

3.3 　望远镜、X射线、激光方向瞄准57

3.3.1 　搜寻行星58

3.3.2 　X射线晶体学59

3.3.3 　激光雕刻水晶工艺品60

3.4 　操控工业机械61

3.4.1 　印制电路板钻孔61

3.4.2 　印制电路板焊锡62

3.4.3 　黄铜雕刻62

3.4.4 　定制计算机芯片62

3.4.5 　清理硅晶片缺陷63

3.5 　组织数据63

3.5.1 　音乐之旅64

3.5.2 　电子游戏速度优化66

3.6 　微处理器测试67

3.7 　安排生产作业任务68

3.8 　其他应用68

第 4 章　探寻路线70

4.1 　周游48州问题70

4.2 　扩充构造树与路线73

4.2.1 　最近邻算法73

4.2.2 　贪心算法75

4.2.3 　插入算法77

4.2.4 　数学概念：树79

4.2.5 　Christofides算法82

4.2.6 　新思路84

4.3 　改进路线？立等可取！85

4.3.1 　边交换算法86

4.3.2 　Lin-Kernighan算法89

4.3.3 　Lin-Kernighan-Helsgaun算法92

4.3.4 　翻煎饼、比尔·盖茨和大步搜索的LKH算法93

4.4 　借鉴物理和生物思想95

4.4.1 　局部搜索与爬山算法95

4.4.2 　模拟退火算法97

4.4.3 　链式局部最优化97

4.4.4 　遗传算法99

4.4.5 　蚁群算法101

4.4.6 　其他102

4.5 　DIMACS挑战赛103

4.6 　路线之王104

第 5 章　线性规划106

5.1 　通用模型106

5.1.1 　线性规划107

5.1.2 　引入产品109

5.1.3 　线性的世界110

5.1.4 　应用111

5.2 　单纯形算法112

5.2.1 　主元法求解113

5.2.2 　多项式时间的选主元规则116

5.2.3 　百万倍大提速117

5.2.4 　名字背后的故事118

5.3 　买一赠一：线性规划的对偶性119

5.4 　TSP对应的度约束线性规划的松弛122

5.4.1 　度约束条件124

5.4.2 　控制区125

5.5 　消去子回路127

5.5.1 　子回路不等式129

5.5.2 　“4/3猜想”131

5.5.3 　变量取值的上界132

5.6 　完美松弛133

5.6.1 　线性规划的几何本质133

5.6.2 　闵可夫斯基定理135

5.6.3 　TSP多面体137

5.7 　整数规划137

5.7.1 　TSP的整数规划模型139

5.7.2 　整数规划的求解程序140

5.8 　运筹学140

第 6 章　割平面法143

6.1 　割平面法143

6.2 　TSP不等式一览148

6.2.1 　梳子不等式149

6.2.2 　TSP多面体的小平面定义不等式152

6.3 　TSP不等式的分离问题155

6.3.1 　最大流与最小割155

6.3.2 　梳子分离问题157

6.3.3 　不自交的线性规划解159

6.4 　Edmonds的“天堂之光”161

6.5 　整数规划的割平面163

第 7 章　分支165

7.1 　拆分165

7.2 　搜索队168

7.2.1 　分支切割法168

7.2.2 　强分支170

7.3 　整数规划的分支定界法171

第 8 章　大计算173

8.1 　世界纪录173

8.1.1 　随机选取的64个地点174

8.1.2 　随机选取的80个地点175

8.1.3 　德国的120座城市177

8.1.4 　电路板上的318个孔洞178

8.1.5 　全世界的666个地点179

8.1.6 　电路板上的2392个孔洞180

8.1.7 　电路板上的3038个孔洞181

8.1.8 　美国的13 509座城市183

8.1.9 　计算机芯片上的85 900个门电路183

8.2 　规模宏大的TSP185

8.2.1 　Bosch的艺术收藏品186

8.2.2 　世界187

8.2.3 　恒星188

第 9 章　复杂性190

9.1 　计算模型191

9.2 　Jack Edmonds的奋战193

9.3 　Cook定理和Karp问题列表196

9.3.1 　复杂性类196

9.3.2 　问题归约198

9.3.3 　21个NP完全问题199

9.3.4 　百万美金200

9.4 　TSP研究现状200

9.4.1 　哈密顿回路201

9.4.2 　几何问题202

9.4.3 　Held-Karp纪录203

9.4.4 　割平面205

9.4.5 　近优路线206

9.4.6 　Arora定理207

9.5 　非计算机不可吗208

9.5.1 　DNA计算TSP208

9.5.2 　细菌210

9.5.3 　变形虫计算211

9.5.4 　光学212

9.5.5 　量子计算机213

9.5.6 　闭合类时曲线214

9.5.7 　绳子和钉子215

第 10 章　谋事在人216

10.1 　人机对战216

10.2 　寻找路线的策略217

10.2.1 　路线之格式塔218

10.2.2 　儿童找到的路线218

10.2.3 　凸包假说219

10.2.4 　实地TSP题目220

10.3 　神经科学中的TSP221

10.4 　动物解题高手223

第 11 章　错综之美225

11.1 　Julian Lethbridge225

11.2 　若尔当曲线228

11.3 　连续曲线一笔画231

11.4 　艺术与数学234

第 12 章　超越极限238

参考文献240

文章试读：兰德小组的研究工作解决了环游美国48 州的难题，却没有彻底解决TSP。他们取得了一次巨大的成功，并不意味着就能搞定规模更大的题目。事实上，如果拉斯维加斯赌场把TSP 的最终结果作为一项赌博项目，那么在数学家看来，把赌注押在“TSP 永远无法彻底解决”上会有更大的胜算。对此，必须明确一点：我们要找的所谓解法（solution），实际上是算法（algorithm），也就是要求对于任何一道实例，只要按照...

(查看全部试读)