迷茫的旅行商:一个无处不在的计算机算法问题(全彩印刷) [平装]

《迷茫的旅行商：一个无处不在的计算机算法问题》概述了旅行商问题的起源和历史，并阐述了其许多重要的应用范围，如基因组测序、计算机处理器设计、音乐整理、行星寻找，等等。此外还探讨了人类如何在不借助计算机的情况下解决这个令人着迷的数学问题。 《迷茫的旅行商：一个无处不在的计算机算法问题》图文并茂，生动有趣，适合所有对旅行商和数学感兴趣的读者。《迷茫的旅行商:一个无处不在的计算机算法问题(全彩印刷)》图文并茂，生动有趣，适合所有对旅行商和数学感兴趣的读者。 “该书出自专业人士之手，围绕—个极其重要的算法问题，讲述了一段引人入胜的精彩故事。貌似简单的问题却能引发读者深亥JJA.3思考，相关研究成果亦能用来实现人类苦苦追求的目标：用最好的方式达成目的。《迷茫的旅行商》堪称现世经典之作！” ——Ian Stewart，英国华威大学数学教授《数学万花筒》及《数学万花筒2》作者 “在我看来，该书的精彩之处体现在多个方面：写作风格轻松而不失精确性，内容非常广泛，各种各样的论题彼此关联，对这段历史的讨论和评述也很丰富。读罢此书，我对旅行商问题的认识有了全面的提升。” ——Stan Wagon，Mathematica in Action作者美国麦卡莱斯特学院数学与计算机科学教授 “Cook充分证明了旅行商问题的重要意义。他在书中透露，虽然众多聪明人都研究过该问题，但是我们所有人其实都有机会提出新的重要见解。作为旅行商问题研究的领军人物，他拥有丰富的知识和经验，这在他的作品中体现得淋漓尽致，令人望尘莫及。在这方面，我认为这本书是独—无二的。” ——Mitchel T.Keller，英国伦敦政治经济学院 作者：（美国）库克（William J.Cook） 译者：隋春宁 第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到85900 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 美国的13509座城市 183 8.1.9 计算机芯片上的85900个门电路 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 JackEdmonds的奋战 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 JulianLethbridge 225 11.2 若尔当曲线 228 11.3 连续曲线一笔画 231 11.4 艺术与数学 234 第12章 超越极限 238 参考文献 240 版权页： 插图： 以上评论者是旅行商问题研究领域的三位大师。Merrill Flood在20世纪40年代呼吁人们支持研究TSP，并使它成为基础性研究课题，在这方面，他的贡献无人能及。1956年，他在讨论该问题的研究现状时，首次提出高效解法根本不存在的可能性。10年后，Jack Edmonds重申这一看法，当时他和别人为通用解法是否存在而打赌，而他认为不存在。谈起自己这样想的根据，他谦虚地说：“我对数学提出任何猜想，都是基于如下两条理由：第一，数学上有合理的可能性；第二，我并不确定。”不过，这只是他的玩笑话，因为对于20世纪的数学，他学识渊博，思考深邃，在世界上是数一数二的，所以他如此下注必然有他的道理。5年后，伟大的计算机科学家Richard Karp终于揭晓了这个赌的本质。他在一篇文章中把TSP和许多其他计算问题联系到了一起。具体理论细节留到第9章再讲，现在只稍做解释。相信这一节内容足以让读者理解，为何在小说《抗体》中，宣告发现TSP的高速算法会让每个人都不寒而栗。 1.2.1 好算法，坏算法 Edmonds在写下“好的算法”一词的时候，对于“好”的理解和我们一样：如果一个算法能够在我们满意的时问内解决问题，那么它就是好的。然而，他必须把“好”定义为正式的概念，才能让它有合理的数学意义。显然，我们不能指望TSP的每道题目都能在固定时间（比如一分钟）内通过人力或计算机解决，至少在城市数量增加时应该允许求解时间也相应增加。关键是要确定，时间按照什么速度增长才能得到我们的认可。