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

它產(chǎn)生于三個(gè)人求解一道經(jīng)典數(shù)學(xué)問(wèn)題的研究工作。這個(gè)歷史悠久的問(wèn)題叫做“旅行商問(wèn)題”，無(wú)論靠人工計(jì)算還是借助最快的計(jì)算機(jī)都一直無(wú)法解決。

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

1962年春天，寶潔公司發(fā)起了一場(chǎng)廣告宣傳活動(dòng)，在應(yīng)用數(shù)學(xué)家中引起了不小的反響?；顒?dòng)的重頭戲是一項(xiàng)競(jìng)賽，獎(jiǎng)金高達(dá)1萬(wàn)美元，在當(dāng)時(shí)足以買下一座房子。參賽規(guī)則如下：

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

圖1-1　“54號(hào)車”競(jìng)賽題（寶潔公司供圖）

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

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

求解一般形式的TSP，是容易，還是困難，抑或無(wú)法求解？對(duì)此，最簡(jiǎn)單的回答就是誰(shuí)也不知道。這道計(jì)算數(shù)學(xué)領(lǐng)域的知名難題之所以神秘莫測(cè)而又引人入 勝，正是因?yàn)檫@一點(diǎn)。為此陷入困境的也不只是一名糾結(jié)的旅行商而已，因?yàn)樵谟?jì)算復(fù)雜度的本質(zhì)與人類認(rèn)識(shí)的可能限度這一高深論題中，TSP正是討論的焦點(diǎn)。

若你已躍躍欲試，那么只需要一支削尖的鉛筆和一張干凈的草稿紙，就可以向旅行商伸出援手?；蛟S我們對(duì)于整個(gè)世界的認(rèn)識(shí)也會(huì)因?yàn)槟愣l(fā)生飛躍。

本書(shū)路線一覽

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

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

1 照片上身著T恤衫的男生是Bill Kay。他是Jessie Brainerd的同學(xué)，當(dāng)時(shí)他們?cè)诓歼_(dá)佩斯參加萬(wàn)圣節(jié)晚會(huì)。Jessie Brainerd在博客上寫了一篇日志，提到晚會(huì)上還有兩名學(xué)生化裝成P和NP，手持飛鏢槍玩具互相打斗。

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

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

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

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

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

補(bǔ)充一點(diǎn)小建議。

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

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

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

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