內容介紹
假設一名旅行商打算拜訪一張城市列表中的所有城市，每座城市只去一次，最後回到出發地。要怎么走才能讓路線最短呢？這就是旅行商問題，乍一聽很簡單，在套用數學界卻是一道研究極其熱烈的難題，時至今日仍無人能解。本書中，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
