迷茫的旅行商
出版社:人民邮电出版社
出版日期:2013-10-1
ISBN:9787115327734
作者:[美] William J. Cook
页数:256页
内容概要
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与NP 10
1.2.3 终极问题 11
1.3 循序渐进，各个击破 12
1.3.1 从49到85 900 12
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 规模宏大的TSP 185
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计算TSP 208
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 神经科学中的TSP 221
10.4 动物解题高手 223
第 11 章 错综之美 225
11.1 Julian Lethbridge 225
11.2 若尔当曲线 228
11.3 连续曲线一笔画 231
11.4 艺术与数学 234
第 12 章 超越极限 238
参考文献 240
作者简介
假设一名旅行商打算拜访一张城市列表中的所有城市，每座城市只去一次，最后回到出发地。要怎么走才能让路线最短呢？这就是旅行商问题，乍一听很简单，在应用数学界却是一道研究极其热烈的难题，时至今日仍无人能解。本书中，William J. Cook将带领读者踏上一场数学之旅，跟随旅行商的脚步，从19世纪初爱尔兰数学家W. R. Hamilton最初定义该问题开始，一路奔向当今最前沿、最顶尖的解题尝试。
作者追根溯源，回顾了旅行商问题的历史，探索了它的种种重要应用，比如基因组测序、设计计算机处理器、整理音乐乃至搜寻行星等。他分析了计算机如何抗衡规模宏大的旅行商问题，探讨了人类如何在不借助计算机的情况下独立破解难题。他一路穿越神经科学、心理学与艺术的王国，向读者下了战书：试试解决这道难题吧！旅行商问题价值百万美元——这是克雷数学研究所的悬赏金额，只要解出该题或证明该题不可解，就能得到这笔奖金。
《迷茫的旅行商》介绍了人类对于复杂性本质的理解与局限，将激励读者从此踏上求解这道迷人难题的漫漫征程。
发布书评
精彩书评 (总计2条)
-
关于经典的TSP问题的一切...TSP问题看似简单，特别是在问题规模较小时，最优解似乎是不言自明的，但当问题规模不断扩大，即使是人脑这样的“超大规模并行”的wetware也会立刻感到无所适从、进而“迷茫”。那最终使我们走出黑暗的、不服输的智慧火花又一次在热烈的燃烧中接力，于是有了最近邻算法、有了贪心算法、有了插入算法、有了Christofides算法、有了LKH算法、有了线性规划算法...当问题解决方案带来的提升逐渐由量变转为质变，我们期待的或许已是另一场变革。 -
作者William J. Cook在上世纪90年代曾参与过TSP求解器Concorde的开发。2001年，Concorde因为高效地求解了CMG公司于1996年提出的15,112城市的车辆路径问题获得5000欧元奖励；2005年，求解了电路板上的33,810城市的TSP；2006年，作者和他的同事精确求解了在芯片布线中产生的85,900城市的TSP，创下了当时TSP求解规模的世界纪录；2007年, Hahsler & Hornik对当时TSP的所有主流启发式算法和精确算法进行了评估。给Concorde的评价是“当时最先进的实现”“世界上最好的精确求解器之一”。Concorde至今仍在被广泛地应用于各行各业。它应用过的场合有：基因图谱、蛋白质功能预测、车辆路径问题求解、图像处理、船舶调度，等等。参考文献：[1] https://en.wikipedia.org/wiki/Travelling_salesman_problem[2] https://en.wikipedia.org/wiki/Concorde_TSP_Solver
精彩短评 (总计50条)
-
多讲点算法的细节就好了 -
想到数学家被这道难题逼到想用时间机器来解决就想笑。业内专家写的科普，我是很多地方看不懂。 -
TSP:它的源流、应用、计算方法和影响。 -
The world is bulit by math. -
有点专业…… -
没完全看懂不会评价怎么破 -
小问题，大智慧 -
前面很好看，可是从线性规划那一章开始就感觉看的好辛苦，最后也就随便看看匆匆看完了_(:з)∠)_ -
作为科普来读还是很好的，可以相对直观的了解旅行商问题和相关算法的发展情况。同时也要做好为自己的智商捉急的心理准备。。。 -
科研之精神，循序渐进剖析TSP。 -
NP -
感觉亲眼历证了算法工程师们一代一代哪怕把TSP（以及其他）算法优化一点点儿都要付出千辛万苦...很有趣的一本结合了TSP的历史和各种优化、应用的书... -
很多地方讲得并不清楚、详细 -
旅行商问题是NP问题的典型代表，数学家们在其中付出的努力让人看到他们才是推动世界进步的动力。 -
前几章真精彩，干货十足！后面几章有些野路子乃至神棍！什么通过大猩猩拿香蕉来求解，真是2333！ -
牛逼 -
每次看到这种NP完全问题的时候，都会觉得人类实在是渺小，直觉上好像很简单的问题却被人们定义为无法解决；又觉得人类实在很伟大，在历史的长河中总能演化出无限逼近最正确的答案。 -
旅行商问题的历史娓娓道来，各种解决方法讲的通俗易懂，看完后获得很多启发 -
好玩。 -
科普大规模问题解法 -
很值得思考的一个问题 -
其实我努力试图在算法中读出人生哲理：贪心算法的局部最优解并不能代表全局最优解，就像我们生活中，眼前利益你都得到了，并不意味着这是使你人生利益最大化的选择，所以人生往往应该使用动态规划，年轻时多吃点苦、吃点亏，来寻找全局最优解。但贪心算法却具有时间优势，牺牲了精度换回了时间可行性，于是，我们可以选择这样一个短视的算法，暂时求解当下的人生。 -
跪着看完了 -
NP问题真是个天坑。。。 -
挺不错的，介绍了一些TSP的前沿，可惜前后有些脱节 -
经典的旅行商问题，关于P/NP问题方面的书不多，这本书读起来挺有趣的 -
TSP背后是P=NP问题。书中提到的算法都还蛮有趣的。线性规划+单纯形法已有很多行业实践。略知一二，不多做评论，有装逼嫌疑。 感兴趣的同学可以翻着看看。 -
超棒 -
能看懂的都感谢算法课 T T 把问题和方法名提一遍并不能让人懂，各种八卦也无非能成为一些谈资。还是静下心去看教材上的干货，去思考吧。突然觉得科普没啥意思，只是让人有错误的获得知识的错觉，其实很浅薄，根本用不起上。 -
由经典的TSP问题，层层深入，问题规模不断扩大，从周游几十个城市的最短路线到周游世界所有城市的最短路线，给出了关于解决TSP问题的许多先进算法，以及TSP问题在现实中的应用。
-
tsp问题 -
奇特的一本算法考古书，野史和干货穿插在一起，个别章节难度陡增。 -
恰到好处的算法入门. 以旅行商问题为背景, 作者深入浅出地介绍了算法在实际问题中的应用, 比只讲理论的课本丰富太多. -
各种涨姿势，学过算法，表示感觉很很有趣。 -
科普读物，不错。算法细节基本没有。以此为基础读paper可能会好点。翻译值得表扬，书价略贵。 -
看的时候才发现手上这本估计是印刷错误，少了147-162页，嘛，看目录也是好像看不懂的几节。如果能把蠹虫之惑做成电子游戏还挺好玩的吧，不过也只是想一下而已了。 -
很有意思的一本书，经典问题如果你不觉得经典，那么说明还没有到那个境界 -
只能看前五章 -
妞妞赠书2！很好的科普书咯，作为一个经典NPC问题，若能找到一个“好”的算法，“足以使整个互联网变成历史上微不足道的注脚”。 -
算法问题。 -
翻译真蛋疼 -
这本书很详实的解释了TSP的问题及其研究的历史，但是我读完觉得书中花了大量篇幅进行复杂的算法介绍但却没有解释算法涉及到的一些重要概念，这对于一本科普性质的书来说是严重的问题，而且脚注过于简单，没有提供更广的外延知识。 -
梳理历史多于数学干货。 -
中学生科普读物。但是对于中学生来说，这书定价高了。 -
学渣表示看着很有压力 -
很享受 -
总的来说还是挺不错的，数学总是能领先于这个时代~ -
我每次回家或者出行都要先计算好路线，找到接近最优的路线。 -
e -
其实就是数学书。。。