具体描述
假设一名旅行商打算拜访一张城市列表中的所有城市，每座城市只去一次，最后回到出发地。要怎么走才能让路线最短呢？这就是旅行商问题，乍一听很简单，在应用数学界却是一道研究极其热烈的难题，时至今日仍无人能解。本书中，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与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在上世纪90年代曾参与过TSP求解器Concorde的开发。 2001年，Concorde因为高效地求解了CMG公司于1996年提出的15,112城市的车辆路径问题获得5000欧元奖励； 2005年，求解了电路板上的33,810城市的TSP； 2006年，作者和他的同事精确求解了在芯片布线中产生的8...
关于经典的TSP问题的一切... TSP问题看似简单，特别是在问题规模较小时，最优解似乎是不言自明的，但当问题规模不断扩大，即使是人脑这样的“超大规模并行”的wetware也会立刻感到无所适从、进而“迷茫”。 那最终使我们走出黑暗的、不服输的智慧火花又一次在热烈的燃烧中接力...
作者William J. Cook在上世纪90年代曾参与过TSP求解器Concorde的开发。 2001年，Concorde因为高效地求解了CMG公司于1996年提出的15,112城市的车辆路径问题获得5000欧元奖励； 2005年，求解了电路板上的33,810城市的TSP； 2006年，作者和他的同事精确求解了在芯片布线中产生的8...
关于经典的TSP问题的一切... TSP问题看似简单，特别是在问题规模较小时，最优解似乎是不言自明的，但当问题规模不断扩大，即使是人脑这样的“超大规模并行”的wetware也会立刻感到无所适从、进而“迷茫”。 那最终使我们走出黑暗的、不服输的智慧火花又一次在热烈的燃烧中接力...
作者William J. Cook在上世纪90年代曾参与过TSP求解器Concorde的开发。 2001年，Concorde因为高效地求解了CMG公司于1996年提出的15,112城市的车辆路径问题获得5000欧元奖励； 2005年，求解了电路板上的33,810城市的TSP； 2006年，作者和他的同事精确求解了在芯片布线中产生的8...
用户评价
初次翻开《迷茫的旅行商》，我其实并没有抱太大的期待，市面上的旅行文学太多了，要不就是走马观花式的风景罗列，要不就是强行灌输的人生哲理，总觉得少了点什么。然而，随着书页一点点被翻动，我渐渐被一种奇特的节奏所吸引。作者的文字并不像很多旅游博主那样，一上来就用华丽的辞藻描绘景色的瑰丽，反而有一种朴实得近乎唠叨的开始。他似乎在小心翼翼地整理着脑海中那些模糊的碎片，那些关于出发前的犹豫，关于行李打包的纠结，甚至关于旅途中某个微不足道的选择，都一丝不苟地被记录下来。这种刻意的“慢”和“细”，反而让我觉得无比真实。仿佛我不是在阅读一本别人的游记，而是我在某个咖啡馆里，与一个刚刚结束旅程的朋友，面对面地倾听他那些琐碎却又充满回味的讲述。他很少直接点明某个地方有多么震撼，而是通过描述他如何在一场突如其来的大雨中，狼狈地躲进一个破旧的小店，与店主用手语比划着点餐的经历，来展现那种文化碰撞的无措与有趣。这种沉浸式的细节描写，让我逐渐忘记了自己是在“读”书，而是身临其境地感受着每一次呼吸、每一次迷路、每一次与陌生人的短暂交集。
我喜欢《迷茫的旅行商》的这种“无目的性”。很多旅行书会有一个明确的主题，比如“寻找古迹”、“体验美食”，或者“探访特定人群”。但这本书似乎并没有一个清晰的“任务”。主角的旅程更像是一种漫无目的的漂泊，他没有固定的目的地，也没有明确的计划。他只是随着自己的心意，在陌生的城市里漫步，在无名的餐馆里用餐，与偶遇的人们短暂交流。这种“漂浮”的状态，反而让我感到一种久违的轻松。在现实生活中，我们总是被各种目标和时间表所裹挟，而这本书让我有机会暂时放下这些压力，去体验一种纯粹的、不受束缚的行走。它让我意识到，有时候，最美好的发现，并非来自于刻意的寻找，而是来自于一种开放的心态，一种允许自己随遇而安的自由。这种“不期而遇”的惊喜，在书中被描绘得淋漓尽致。他或许是在一家街角的小书店里，偶然翻到一本打动他的旧书；或许是在一次迷路中，意外发现了一处宁静优美的秘密花园。这些没有预设的精彩，让整本书充满了令人惊喜的张力，也让我对“旅行”这件事，有了全新的理解。
这本书最让我感到惊喜的是它对“孤独”的描绘。在很多人的想象中，旅行是逃离，是自由，是发现自我的过程。但《迷茫的旅行商》却捕捉到了旅行中那种无法避免的、细腻的孤独感。它不是那种撕心裂肺的痛苦，而是一种浸润在空气中的、无声的陪伴。主角一个人走在异国他乡的街头，看着当地人三五成群地谈笑，感受着自己仿佛是这个世界上的一个旁观者。他会在深夜里，一个人坐在酒店的窗前，看着城市的灯火阑珊，心中涌起一股淡淡的、挥之不去的孤寂。作者没有用煽情的笔触去刻意渲染这种孤独，而是通过一些极其生活化的场景，比如一个人吃饭时的沉默，一个人看电影时的不自觉的走神，来让读者体会到那种“身处人群，却又与世界隔了一层薄膜”的感觉。然而，这种孤独并非全然的负面。在作者的笔下，它也带来了一种更深的思考，一种与自己对话的空间。正是这种独自面对世界的时刻，才让他有机会去审视内心的波澜，去听清自己真实的呼吸。这是一种很高级的孤独，它没有摧毁人，反而让人在寂静中变得更加强大。
读《迷茫的旅行商》，我最大的感受是它对“迷失”二字的深刻诠释。很多旅行文学总是试图找到“意义”，寻找“答案”，仿佛旅行的目的就是为了解开某个终极谜题。但这本书却恰恰相反，它坦诚地展现了旅途中的不确定性，以及由此带来的种种困惑。主角并非那种胸有成竹、目标明确的探险家，他更像是一个被生活推着走，在陌生的土地上寻找一些模糊慰藉的普通人。他会因为错过一班火车而懊恼，会因为语言不通而在问路时碰壁，甚至会因为不熟悉当地的风俗而感到尴尬。但正是这些“不完美”，这些“迷茫”，构成了旅行最真实的底色。他并没有刻意去美化这些经历，而是如实地呈现出来，让我们看到，原来旅途中的“失败”和“挫折”，也可以是构成回忆的珍贵部分。这种坦率，让我感到一种莫名的释然，好像被允许放下对旅行的“高性能”期待，允许自己有权利在陌生的环境中感到不知所措，允许自己不必每次都抵达预设的“成功”终点。这本书让我意识到，有时候，最深刻的体验，恰恰就蕴藏在那些不期而遇的“迷茫”之中。
《迷茫的旅行商》给我最大的触动，是它对“看见”的重新定义。我们常常以为，旅行就是用眼睛去“看”风景，去记录那些视觉上的奇观。但这本书却引导我思考，什么是真正的“看见”。主角并非仅仅停留在对景色的描绘上，他更关注的是那些被隐藏在表象之下的东西。他会在一个看似普通的市集里，花费很长时间去观察摊贩们与顾客的互动，去揣摩他们脸上细微的表情，去感受他们生活的气息。他会因为一个陌生人的一个善意举动而反复回味，并从中解读出人与人之间共通的情感。他会深入到那些不被游客熟知的角落，去倾听当地人的故事，去感受他们平凡生活中的喜怒哀乐。这种“看见”，是一种同理心的延伸，是一种对生命细微之处的敏感捕捉。他让我明白，旅行不仅仅是用眼睛去丈量世界，更是用心灵去感受世界。那些在旅行中被忽略的、微不足道的瞬间，往往承载着最深刻的人性光辉，也最能触动我们内心深处的情感。这本书让我重新审视了自己过去的旅行方式，意识到我可能只是匆匆掠过，而错过了许多值得“看见”的宝藏。
e
多讲点算法的细节就好了
奇特的一本算法考古书，野史和干货穿插在一起，个别章节难度陡增。
科普大规模问题解法
奇特的一本算法考古书，野史和干货穿插在一起，个别章节难度陡增。
