《迷茫的旅行商》介紹了人類對於複雜性本質的理解與局限，將激勵讀者從此踏上求解這道迷人難題的漫漫征程。
基本介紹
- 作者：美 William J. Cook
- 出版社：人民郵電出版社
- 副標題：一個無處不在的計算機算法問題
- 原作名：In pursuit of the traveling salesmanMathematics at the limits of computation
- 譯者：隋春寧
- 出版時間：2013-9
- 頁數：256
- 定價：49.00
- 裝幀：平裝
- ISBN：9787115327734
內容介紹,作者介紹,作品目錄,
內容介紹
假設一名旅行商打算拜訪一張城市列表中的所有城市，每座城市只去一次，最後回到出發地。要怎么走才能讓路線最短呢？這就是旅行商問題，乍一聽很簡單，在套用數學界卻是一道研究極其熱烈的難題，時至今日仍無人能解。本書中，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
第 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
