假設一名旅行商打算拜訪一張城市列表中的所有城市，每座城市只去一次，***回到出發(fā)地。要怎么走才能讓路線最短呢？這就是旅行商問題，乍一聽很簡 單，在應用數學界卻是一道研究極其熱烈的難題，時至今日仍無人能解。本書中，William J. Cook將帶領讀者踏上一場數學之旅，跟隨旅行商的腳步，從19世紀初愛爾蘭數學家W. R. Hamilton最初定義該問題開始，一路奔向當今最前沿、最***的解題嘗試。

它產生于三個人求解一道經典數學問題的研究工作。這個歷史悠久的問題叫做“旅行商問題”，無論靠人工計算還是借助最快的計算機都一直無法解決。

1. 摘自IBM公司發(fā)布于1964年1月2日的新聞稿。“它”表示一個新的計算機程序，能夠解決小規(guī)模的旅行商問題，由Michael Held、Richard Karp和Richard Shareshian三人編寫完成。

1962年春天，寶潔公司發(fā)起了一場廣告宣傳活動，在應用數學家中引起了不小的反響。活動的重頭戲是一項競賽，獎金高達1萬美元，在當時足以買下一座房子。參賽規(guī)則如下：

假設Toody和Muldoon打算開車環(huán)游美國，地圖上用點標出的33個地點都要游覽，并且要走滿足條件的路線中最短的一條。請你為他們規(guī)劃一條旅行路線，以伊利諾伊州的芝加哥市為旅途的起點和終點，依次用線連接各地點，并使得總里程最短。

圖1-1　“54號車”競賽題（寶潔公司供圖）

Toody和Muldoon是當時一部美國熱門電視劇²中的人物。他們是駕駛54號車的兩名警官。這項游遍33座城市的任務是旅行商問題（traveling salesman problem，簡稱TSP）的一個具體例子。TSP的一般形式為：給定一組城市及它們兩兩之間的距離，求經過每座城市并返回出發(fā)地的最短路線。

2. 即1961～1963年播出的美國電視喜劇Car 54, Where Are You。——譯者注

求解一般形式的TSP，是容易，還是困難，抑或無法求解？對此，最簡單的回答就是誰也不知道。這道計算數學領域的知名難題之所以神秘莫測而又引人入 勝，正是因為這一點。為此陷入困境的也不只是一名糾結的旅行商而已，因為在計算復雜度的本質與人類認識的可能限度這一高深論題中，TSP正是討論的焦點。

若你已躍躍欲試，那么只需要一支削尖的鉛筆和一張干凈的草稿紙，就可以向旅行商伸出援手。或許我們對于整個世界的認識也會因為你而發(fā)生飛躍。

本書路線一覽

圖1-11的T恤衫圖案出自Jessie Brainerd之手，她曾參加2007年的布達佩斯數學項目。¹在應用數學專業(yè)或者計算機科學專業(yè)，每一名畢業(yè)不久的合格本科生都能一眼看出這幅圖的主題就是TSP。按照許多大學的課程設置，學習旅行商問題都是必經之路。最近，甚至連美國的中學課本里都有該問題的簡單介紹。

圖1-11　2007年萬圣節(jié)的TSP（照片由Jessie Brainerd提供）

1 照片上身著T恤衫的男生是Bill Kay。他是Jessie Brainerd的同學，當時他們在布達佩斯參加萬圣節(jié)晚會。Jessie Brainerd在博客上寫了一篇日志，提到晚會上還有兩名學生化裝成P和NP，手持飛鏢槍玩具互相打斗。

對TSP的介紹既然已經如此普及，我寫作本書的目的何在？很簡單，我希望能讓本書讀者對它更加了解，不止步于最簡單的認識，而是遠遠深入問題，接觸 最近的理論進展與***進的解法。我的***目標是鼓勵你們，希望你們也能踏上對旅行商的追蹤之路。也許就在某個未知的拐角處，你們將邁出最終一步，迎來徹底 的成功。

本書第2章將從數學和應用兩方面追溯旅行商問題的由來，在回顧歷史的過程中介紹TSP的基本研究題目，進一步討論將留到后面各章進行。第3章繼續(xù)介紹TSP的豐富應用，包括旅行規(guī)劃、基因組測序、行星搜尋、樂曲編排等方面的內容。

第4章到第7章闡述求解TSP的技術方法，為核心內容。接下來在第8章討論計算機代碼如何解決大規(guī)模的TSP題目。

第9章將探討一般形式的TSP是否存在多項式時間解法。這一理論問題價值百萬美金，你若愛錢，這章內容正合你意。然而，即使你錢庫空空，亟待現金入 賬，我也不建議你跳過前面的章節(jié)。因為在計算領域大顯身手的方法里，很可能孕育著成功解決理論問題的種子。而你若打算證明不存在通用解法，也必須解釋清楚 為何前人的解法能實際應用卻不合要求。

數學知識就介紹到這里。第10章將轉向心理學和神經學的研究范疇，論述人類如何在不借助計算機的情況下求解TSP。第11章將帶領讀者欣賞藝術作品 中的TSP路線，比如Julian Lethbridge筆下美妙的抽象畫和Robert Bosch設計的簡單曲線圖案。***，第12章將再次號召本書讀者接受TSP的挑戰(zhàn)，并以此結束全書。

補充一點小建議。

如果面前有無數艱難險阻橫空而降，愛爾蘭作家J. P. Donleavy筆下的人物Rashers Ronald會發(fā)誓“不屈不撓，前進到底”。¹Applegate等人在研究TSP計算時便將這句話作為戰(zhàn)斗口號。我建議深入該問題的讀者也能堅持這種態(tài)度。本書會介紹許多專家，他們的研究取得了重大進展，但仍然沒有從根本上解決TSP。要想扭轉局勢，搞定旅行商，也許我們需要的恰恰只是一個新的思考角度。

1 Rashers Ronald出現在J. P. Donleavy的作品The Destinies of Darcy Dancer, Gentleman中，該書由Atlantic Monthly Press于1994年出版。

圖1-12　左圖：1987年，W. Cook（本書作者，左一）和V. Chvátal（右一）向作家J. P. Donleavy贈送夜壺，由Adrian Bondy拍攝，照片所有權利保留；右圖：1987年，J. P. Donleavy寫給本書作者的明信片

原文鏈接:http://www.ituring.com.cn/article/56991