迷茫的旅行商：一個(gè)無(wú)處不在的計(jì)算機(jī)算法問(wèn)題

目　錄

第1章　難題大挑戰(zhàn)　1
1.1　環(huán)游美國(guó)之旅　2
1.2　不可能的任務(wù)嗎　7
1.2.1　好算法，壞算法　8
1.2.2　復(fù)雜度類(lèi)P與NP　10
1.2.3　終極問(wèn)題　11
1.3　循序漸進(jìn)，各個(gè)擊破　12
1.3.1　從49到85 900　12
1.3.2　世界旅行商問(wèn)題　15
1.3.3　《蒙娜麗莎》一筆畫(huà)　17
1.4　本書(shū)路線一覽　18

第2章　歷史淵源　21
2.1　數(shù)學(xué)家出場(chǎng)之前　21
2.1.1　商人　21
2.1.2　律師　27
2.1.3　牧師　28
2.2　歐拉和哈密頓　30
2.2.1　圖論與哥尼斯堡七橋問(wèn)題　30
2.2.2　騎士周游問(wèn)題　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í)代的推銷(xiāo)員　50
3.1.2　取貨與送貨　51
3.1.3　送餐到家　52
3.1.4　農(nóng)場(chǎng)、油田、藍(lán)蟹　53
3.1.5　巡回售書(shū)　53
3.1.6　“多走一里路”　54
3.1.7　摩托車(chē)?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　音樂(lè)之旅　64
3.5.2　電子游戲速度優(yōu)化　66
3.6　微處理器測(cè)試　67
3.7　安排生產(chǎn)作業(yè)任務(wù)　68
3.8　其他應(yīng)用　68

第4章　探尋路線　70
4.1　周游48州問(wèn)題　70
4.2　擴(kuò)充構(gòu)造樹(shù)與路線　73
4.2.1　最近鄰算法　73
4.2.2　貪心算法　75
4.2.3　插入算法　77
4.2.4　數(shù)學(xué)概念：樹(shù)　79
4.2.5　Christofides算法　82
4.2.6　新思路　84
4.3　改進(jìn)路線？立等可?。　?5
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　百萬(wàn)倍大提速　117
5.2.4　名字背后的故事　118
5.3　買(mǎi)一贈(zèng)一：線性規(guī)劃的對(duì)偶性　119
5.4　TSP對(duì)應(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不等式的分離問(wèn)題　155
6.3.1　最大流與最小割　155
6.3.2　梳子分離問(wèn)題　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　德國(guó)的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　美國(guó)的13 509座城市　183
8.1.9　計(jì)算機(jī)芯片上的85 900個(gè)門(mén)電路　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問(wèn)題列表　196
9.3.1　復(fù)雜性類(lèi)　196
9.3.2　問(wèn)題歸約　198
9.3.3　21個(gè)NP完全問(wèn)題　199
9.3.4　百萬(wàn)美金　200
9.4　TSP研究現(xiàn)狀　200
9.4.1　哈密頓回路　201
9.4.2　幾何問(wèn)題　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　變形蟲(chóng)計(jì)算　211
9.5.4　光學(xué)　212
9.5.5　量子計(jì)算機(jī)　213
9.5.6　閉合類(lèi)時(shí)曲線　214
9.5.7　繩子和釘子　215

第10章　謀事在人　216
10.1　人機(jī)對(duì)戰(zhàn)　216
10.2　尋找路線的策略　217
10.2.1　路線之格式塔　218
10.2.2　兒童找到的路線　218
10.2.3　凸包假說(shuō)　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ù)曲線一筆畫(huà)　231
11.4　藝術(shù)與數(shù)學(xué)　234

第12章　超越極限　238

參考文獻(xiàn)　240