迷茫的旅行商：一个无处不在的计算机算法问题

迷茫的旅行商：一个无处不在的计算机算法问题
作者：（美）William J.Cook 著，隋春宁 译
出版时间：2013-10-01

【图书简介】

《迷茫的旅行商：一个无处不在的计算机算法问题》概述了旅行商问题的起源和历史，并阐述了其许多重要的应用范围，如基因组测序、计算机处理器设计、音乐整理、行星寻找，等等。此外还探讨了人类如何在不借助计算机的情况下解决这个令人着迷的数学问题。《迷茫的旅行商：一个无处不在的计算机算法问题》图文并茂，生动有趣，适合所有对旅行商和数学感兴趣的读者。


【作者简介】

William J. Cook加拿大滑铁卢大学教授，美国国家工程院院士，美国数学学会、美国工业与应用数学学会以及美国运筹学和管理学研究协会会员。主要研究领域为整数规划与组合优化，曾出版多部研究旅行商问题的专著，其中与人合著的TheTaveling Salesman Problem：A ComputationalStudy获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