假設(shè)一名旅行商打算拜訪一張城市列表中的所有城市，每座城市只去一次，最后回到出發(fā)地。要怎么走才能讓路線最短呢？這就是旅行商問題，乍一聽很簡單，在應(yīng)用數(shù)學(xué)界卻是一道研究極其熱烈的難題，時(shí)至今日仍無人能解。本書中，William J. Cook將帶領(lǐng)讀者踏上一場數(shù)學(xué)之旅，跟隨旅行商的腳步，從19世紀(jì)初愛爾蘭數(shù)學(xué)家W. R. Hamilton最初定義該問題開始，一路奔向當(dāng)今最前沿、最頂尖的解題嘗試。
作者追根溯源，回顧了旅行商問題的歷史，探索了它的種種重要應(yīng)用，比如基因組測序、設(shè)計(jì)計(jì)算機(jī)處理器、整理音樂乃至搜尋行星等。他分析了計(jì)算機(jī)如何抗衡規(guī)模宏大的旅行商問題，探討了人類如何在不借助計(jì)算機(jī)的情況下獨(dú)立破解難題。他一路穿越神經(jīng)科學(xué)、心理學(xué)與藝術(shù)的王國，向讀者下了戰(zhàn)書：試試解決這道難題吧！旅行商問題價(jià)值百萬美元——這是克雷數(shù)學(xué)研究所的懸賞金額，只要解出該題或證明該題不可解，就能得到這筆獎(jiǎng)金。
《迷茫的旅行商》介紹了人類對于復(fù)雜性本質(zhì)的理解與局限，將激勵(lì)讀者從此踏上求解這道迷人難題的漫漫征程。 作者簡介
William J. Cook
加拿大滑鐵盧大學(xué)教授，美國國家工程院院士，美國數(shù)學(xué)學(xué)會(huì)、美國工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)以及美國運(yùn)籌學(xué)和管理學(xué)研究協(xié)會(huì)會(huì)員。主要研究領(lǐng)域?yàn)檎麛?shù)規(guī)劃與組合優(yōu)化，曾出版多部研究旅行商問題的專著，其中與人合著的The Taveling Salesman Problem：A Computational Study獲2007年Lanchester獎(jiǎng)。
目錄：
目 錄
第 1 章 難題大挑戰(zhàn) 1
1.1 環(huán)游美國之旅 2
1.2 不可能的任務(wù)嗎 7
1.2.1 好算法，壞算法 8
1.2.2 復(fù)雜度類P與NP 10
1.2.3 終極問題 11
1.3 循序漸進(jìn)，各個(gè)擊破 12
1.3.1 從49到85 900 12
1.3.2 世界旅行商問題 15
1.3.3 《蒙娜麗莎》一筆畫 17
1.4 本書路線一覽 18
第 2 章 歷史淵源 21
2.1 數(shù)學(xué)家出場之前 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 數(shù)學(xué)譜系 39
2.3 維也納—哈佛—普林斯頓 40
2.4 蘭德公司 43
2.5 統(tǒng)計(jì)學(xué)觀點(diǎn) 45
2.5.1 孟加拉黃麻農(nóng)田 45
2.5.2 證實(shí)路線估計(jì)值 47
2.5.3 TSP常數(shù) 47
第 3 章 旅行商的用武之地 50
3.1 公路旅行 50
3.1.1 數(shù)字化時(shí)代的推銷員 50
3.1.2 取貨與送貨 51
3.1.3 送餐到家 52
3.1.4 農(nóng)場、油田、藍(lán)蟹 53
3.1.5 巡回售書 53
3.1.6 “多走一里路” 54
3.1.7 摩托車?yán)悺 ?4
3.1.8 飛行時(shí)間 55
3.2 繪制基因組圖譜 56
3.3 望遠(yuǎn)鏡、X射線、激光方向瞄準(zhǔn) 57
3.3.1 搜尋行星 58
3.3.2 X射線晶體學(xué) 59
3.3.3 激光雕刻水晶工藝品 60
3.4 操控工業(yè)機(jī)械 61
3.4.1 印制電路板鉆孔 61
3.4.2 印制電路板焊錫 62
3.4.3 黃銅雕刻 62
3.4.4 定制計(jì)算機(jī)芯片 62
3.4.5 清理硅晶片缺陷 63
3.5 組織數(shù)據(jù) 63
3.5.1 音樂之旅 64
3.5.2 電子游戲速度優(yōu)化 66
3.6 微處理器測試 67
3.7 安排生產(chǎn)作業(yè)任務(wù) 68
3.8 其他應(yīng)用 68
第 4 章 探尋路線 70
4.1 周游48州問題 70
4.2 擴(kuò)充構(gòu)造樹與路線 73
4.2.1 最近鄰算法 73
4.2.2 貪心算法 75
4.2.3 插入算法 77
4.2.4 數(shù)學(xué)概念：樹 79
4.2.5 Christofides算法 82
4.2.6 新思路 84
4.3 改進(jìn)路線？立等可��！ 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 鏈?zhǔn)骄植孔顑?yōu)化 97
4.4.4 遺傳算法 99
4.4.5 蟻群算法 101
4.4.6 其他 102
4.5 DIMACS挑戰(zhàn)賽 103
4.6 路線之王 104
第 5 章 線性規(guī)劃 106
5.1 通用模型 106
5.1.1 線性規(guī)劃 107
5.1.2 引入產(chǎn)品 109
5.1.3 線性的世界 110
5.1.4 應(yīng)用 111
5.2 單純形算法 112
5.2.1 主元法求解 113
5.2.2 多項(xiàng)式時(shí)間的選主元規(guī)則 116
5.2.3 百萬倍大提速 117
5.2.4 名字背后的故事 118
5.3 買一贈(zèng)一：線性規(guī)劃的對偶性 119
5.4 TSP對應(yīng)的度約束線性規(guī)劃的松弛 122
5.4.1 度約束條件 124
5.4.2 控制區(qū) 125
5.5 消去子回路 127
5.5.1 子回路不等式 129
5.5.2 “4/3猜想” 131
5.5.3 變量取值的上界 132
5.6 完美松弛 133
5.6.1 線性規(guī)劃的幾何本質(zhì) 133
5.6.2 閔可夫斯基定理 135
5.6.3 TSP多面體 137
5.7 整數(shù)規(guī)劃 137
5.7.1 TSP的整數(shù)規(guī)劃模型 139
5.7.2 整數(shù)規(guī)劃的求解程序 140
5.8 運(yùn)籌學(xué) 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 不自交的線性規(guī)劃解 159
6.4 Edmonds的“天堂之光” 161
6.5 整數(shù)規(guī)劃的割平面 163
第 7 章 分支 165
7.1 拆分 165
7.2 搜索隊(duì) 168
7.2.1 分支切割法 168
7.2.2 強(qiáng)分支 170
7.3 整數(shù)規(guī)劃的分支定界法 171
第 8 章 大計(jì)算 173
8.1 世界紀(jì)錄 173
8.1.1 隨機(jī)選取的64個(gè)地點(diǎn) 174
8.1.2 隨機(jī)選取的80個(gè)地點(diǎn) 175
8.1.3 德國的120座城市 177
8.1.4 電路板上的318個(gè)孔洞 178
8.1.5 全世界的666個(gè)地點(diǎn) 179
8.1.6 電路板上的2392個(gè)孔洞 180
8.1.7 電路板上的3038個(gè)孔洞 181
8.1.8 美國的13 509座城市 183
8.1.9 計(jì)算機(jī)芯片上的85 900個(gè)門電路 183
8.2 規(guī)模宏大的TSP 185
8.2.1 Bosch的藝術(shù)收藏品 186
8.2.2 世界 187
8.2.3 恒星 188
第 9 章 復(fù)雜性 190
9.1 計(jì)算模型 191
9.2 Jack Edmonds的奮戰(zhàn) 193
9.3 Cook定理和Karp問題列表 196
9.3.1 復(fù)雜性類 196
9.3.2 問題歸約 198
9.3.3 21個(gè)NP完全問題 199
9.3.4 百萬美金 200
9.4 TSP研究現(xiàn)狀 200
9.4.1 哈密頓回路 201
9.4.2 幾何問題 202
9.4.3 Held-Karp紀(jì)錄 203
9.4.4 割平面 205
9.4.5 近優(yōu)路線 206
9.4.6 Arora定理 207
9.5 非計(jì)算機(jī)不可嗎 208
9.5.1 DNA計(jì)算TSP 208
9.5.2 細(xì)菌 210
9.5.3 變形蟲計(jì)算 211
9.5.4 光學(xué) 212
9.5.5 量子計(jì)算機(jī) 213
9.5.6 閉合類時(shí)曲線 214
9.5.7 繩子和釘子 215
第 10 章 謀事在人 216
10.1 人機(jī)對戰(zhàn) 216
10.2 尋找路線的策略 217
10.2.1 路線之格式塔 218
10.2.2 兒童找到的路線 218
10.2.3 凸包假說 219
10.2.4 實(shí)地TSP題目 220
10.3 神經(jīng)科學(xué)中的TSP 221
10.4 動(dòng)物解題高手 223
第 11 章 錯(cuò)綜之美 225
11.1 Julian Lethbridge 225
11.2 若爾當(dāng)曲線 228
11.3 連續(xù)曲線一筆畫 231
11.4 藝術(shù)與數(shù)學(xué) 234
第 12 章 超越極限 238
參考文獻(xiàn) 240
|
