1979年11月7日《紐約時(shí)報(bào)》出現(xiàn)一篇引人注目的文章，它的標(biāo)題是：《蘇聯(lián)的發(fā)現(xiàn)震動(dòng)數(shù)學(xué)界》（Soviet Discovery Rocks World of Mathematics），這文章介紹一個(gè)本是默默無聞的年青數(shù)學(xué)家卡倩（L．G．Khachian），他在線性規(guī)劃理論上的一個(gè)發(fā)現(xiàn)使到美國數(shù)學(xué)界為之轟動(dòng)。由于記者在詢問一些著名數(shù)學(xué)家時(shí)對數(shù)學(xué)問題了解不深，文章報(bào)導(dǎo)是有一些失實(shí)，但由這文章引起的轟動(dòng)及誤導(dǎo)是相當(dāng)嚴(yán)重。我以后會討論這問題。該文中說：“俄國人的發(fā)現(xiàn)建議用電子計(jì)算機(jī)處理一類和‘旅行貨郎問題’（Travelling Salesman Problem）有關(guān)的數(shù)學(xué)上一個(gè)著名及難處理的問題。‘旅行貨朗問題’目的是決定一個(gè)貨郎（或推銷員或銷貨員）所要跑的最短路程──他要走遍市鎮(zhèn)，但是不能再回到走過的地方。表面上，這問題看來簡單，事實(shí)上為了要解決這問題的實(shí)際應(yīng)用，人們需要電子計(jì)算機(jī)來解決。”
在這點(diǎn)上這記者是說對了。“旅行貨郎問題”目前是許多國家（如西德、日本、蘇聯(lián)、英國、美國、法國）的運(yùn)籌學(xué)工作者研究的熱烈課題。為了要了解這問題，我們可要知道目前在圖論（Graph Theory）上許多人正在研究一種圖──哈密爾頓圖（Hemilton graphs）。
一、哈密爾頓圖的由來
在17—18世紀(jì)時(shí)，歐洲宮庭及一些貴族很喜歡玩西洋象棋，西洋象棋中的騎士（knight）是對應(yīng)我們中國象棋的“馬”，而它通常是刻成一個(gè)馬頭，跑法也是和中國象棋的“馬”一樣，走“日”線──即從日的一角沿著對角線躍到另一角。
在1771年，就有一位名叫范德蒙（A．Vandermonde）的法國數(shù)學(xué)家，寫了一篇文章研究所謂“棋盤的騎士問題”。這問題是這樣：在8×8的棋盤格的隨意一個(gè)位置，我放一個(gè)騎士，然后我想法子使他跑遍棋盤的所有的格子，走過的不許再走，我能不能使騎士最后回到原來的位置？
這個(gè)問題并不簡單，許多象棋愛好者及數(shù)學(xué)家曾坐下來研究這個(gè)問題。我這里列出一個(gè)情形的解（見圖一），我將棋盤的左下角的格選為起始位置，把它定為1，讀者可以驗(yàn)證根據(jù)圖一的跑法，騎士最后是能跑回1的。
56
41
58
35
50
39
60
33
47
44
55
40
59
34
51
38
42
57
46
49
36
53
32
61
45
48
43
54
31
62
37
52
20
5
30
63
22
11
16
13
29
64
21
4
17
14
25
10
6
19
2
27
8
23
12
15
1
28
7
18
3
26
9
24
圖一 “棋盤騎士問題”的一個(gè)解法
18世紀(jì)的大數(shù)學(xué)家歐拉（Euler），在1759年就系統(tǒng)地研究過這個(gè)問題，也得到了一些結(jié)果。以后德國數(shù)學(xué)家高斯也曾對這問題發(fā)生興趣，花過一些時(shí)間研究它及另外一個(gè)棋盤的“皇后問題”。
我們現(xiàn)在把棋盤上的格子對應(yīng)在一個(gè)平面上的一個(gè)小圓點(diǎn)，這樣我們在平面上就有64個(gè)小圓點(diǎn)。從一個(gè)格子用騎士的走法我們可以抵達(dá)不同數(shù)目的格子：如果是處在棋盤的四個(gè)角，只能有兩種跑法；在其他邊緣的格子就有三種跑法；一般當(dāng)中的格子，就有四種可能的跑法。我們把平面上的點(diǎn)用弧線連接，兩個(gè)點(diǎn)有一條弧線連起當(dāng)且僅當(dāng)（if and only if）我們可以從它們所對應(yīng)的格子將騎士移動(dòng)。我們得到了一個(gè)圖（ graph）。
在圖中取一個(gè)頂點(diǎn)v0，如果我們有一個(gè)弧線把它和另外一個(gè)點(diǎn)v1聯(lián)起來，我們就用（v0，v1）來表示這個(gè)弧線。假定我有一系列點(diǎn)v0，v1，v2，…，vn其中沒有兩個(gè)相同以及一序列的弧線存在（v0，v1），（v1，v2），…，（vn-1，vn），（vn，v0），使到我從v0出發(fā)可以經(jīng)過v1，v2，…，vn最后由vn回到v0，我就說這些弧線組成一個(gè)回路（circuit），為了方便，我們用下面的記號表示這回路：（v0，v1，v2，…，vn，v0）。
如果我有一個(gè)圖G有n+1個(gè)頂點(diǎn)（vertices）{v0，v1，v2，…，vn}，而我能找到一個(gè)回路（v0，v1，v2，…，vn，v0），那么我就說這個(gè)圖是哈密爾頓圖（Hamilton graph），這個(gè)回路稱為哈密爾頓回路（Hamilton circuit）。
因此，“棋盤的騎士問題”實(shí)際上就是要判斷它所對應(yīng)的圖是否是哈密爾頓圖的問題。
為什么叫哈密爾頓圖？哈密爾頓是誰呢？
哈密爾頓是愛爾蘭的一位數(shù)學(xué)家和天文學(xué)家。他的一生是多姿多彩的，我在《數(shù)學(xué)和數(shù)學(xué)家的故事》第一集里有詳細(xì)介紹他的工作和生平，讀者可以找來一讀。
自從哈密爾頓發(fā)現(xiàn)“四元數(shù)”之后，他又發(fā)現(xiàn)了另外一種他命名為“The Icosian Calculus”的代數(shù)系統(tǒng)，這系統(tǒng)有加和乘的運(yùn)算子（operators），可是乘法不滿足交換律（Commutative law即xy=yx這個(gè)規(guī)律）。
他發(fā)現(xiàn)這代數(shù)系統(tǒng)是和正則20面體（regularicosion polybedron）有關(guān)系。他想到一個(gè)游戲，怎樣跑遍正則多面體上的所有頂點(diǎn)，而最后又能回到起點(diǎn)的問題。在1857年他把這個(gè)游戲的想法以25英鎊的價(jià)錢賣給一位玩具和游戲制造商。這25英鎊在124年前是很好用，在今天拿去倫敦的“唐人區(qū)”買“牛腩面”吃可能連十碗都吃不到。
這玩具商把這游戲制造出來了（見圖二），在圓盤上有20個(gè)代表城市的圓孔，你必須把20個(gè)上面標(biāo)有1，2，3，…，20的木條順序插進(jìn)去，代表你經(jīng)過不同的城市，最后回到原出發(fā)點(diǎn)。這個(gè)游戲叫“環(huán)游世界”，很可惜玩具商人沒有從這游戲上賺到錢。
以后人們因這游戲就稱這類圖為哈密爾頓圖。
THE ICOSIAN GAME
二、怎么樣的圖是哈密爾頓圖
給你一個(gè)圖，你怎么知道它是否是哈密爾頓圖呢？當(dāng)然如果圖的頂點(diǎn)不多，你可以試試找哈密爾頓回路就可以解決和判斷。你用的是最古老的“嘗試和錯(cuò)誤”的方法，但是數(shù)學(xué)家并不滿意這樣的碰得焦頭爛額后才找到真理的方法。是否存在一組必要和充分的條件，使到我們能簡單輕易地判斷一個(gè)圖是否哈密爾頓圖？許多聰明人去試過了，很可惜到現(xiàn)在這問題還未解決，因此讀者可以試試自己來找尋一下。
英國數(shù)學(xué)家G．A．狄拉克（Dirac）在1952年給出一個(gè)充分條件使得一個(gè)圖會是哈密爾頓圖。他的定理是只要檢查每一個(gè)頂點(diǎn)x，看它的上面有多少個(gè)弧通過，把這個(gè)數(shù)目用d（x）來表示，只要每一個(gè)點(diǎn)的d（x）是相當(dāng)大的話，這圖就會是哈密爾頓圖。
狄拉克定理 給定一個(gè)圖G，如果其頂點(diǎn)集V的元素?cái)?shù)是n≥3，
由于我們可以看到以下的兩個(gè)圖G1，G2都是哈密爾頓圖（見圖三）。
到了1960年，美國著名的圖論專家奧斯坦·奧勒（ Oystein Ore）推廣狄拉克的工作，得到以下的結(jié)果。
奧勒定理 給定一個(gè)圖G，如果其頂點(diǎn)集V是有n≥3點(diǎn)，而對于任意兩點(diǎn)x，y我們有d（x）+d（y）≥n，那么G一定是哈密爾頓圖。
在1962年，匈牙利有一個(gè)少年發(fā)表了一篇只有一頁長的論文，他的結(jié)果卻是推廣了以上奧勒的定理，他的工作是這么重要引起許多人談?wù)�，并且在圖論的教科書上登他的證明。以后幾年來許多人想要改進(jìn)這工作，最后才由一個(gè)捷克青年數(shù)學(xué)家得到比他更好的結(jié)果。
這個(gè)少年名叫博薩（Posa），我在《數(shù)學(xué)和數(shù)學(xué)家的故事》第一集的一篇文章就有介紹他的事跡，讀者想要知道他的故事可以看看該文。
為了能更容易看清博薩的結(jié)果，我這里引進(jìn)幾個(gè)記號：對于每一個(gè)圖G，我們用d（G）來表示序列如（d（x1），d（x2），…，d（xn）），這里x1，…，xn是G的所有頂點(diǎn)，而序列的數(shù)是從小排到大去排列。比方說在圖三里我們有
d（G1）=（3，3，3，3）
d（G2）=（4，4，4，4，4，4）
假定我們有兩個(gè)序列具有相同個(gè)數(shù)的數(shù)字：
X=（x1，x2，x3，…xn）；
Y=（y1，y2，y3，…，yn）
我們用X≤Y表示當(dāng)且僅當(dāng)對于每個(gè)i=1，2，…，n，我們都有xi≤yi。
比方說，X=（1，2，3，4，5），Y=（2，3，5，7，9），Z=（4，2，1，3，5），我們就有X≤Y，而X≤Z是不對的。
現(xiàn)在對于每個(gè)n≥3的整數(shù)，我們定義這樣的整數(shù)序列P（n）
（1）如果n是偶數(shù)，我們有n個(gè)數(shù)照底下由小到大的排法：
（2）如果n是奇數(shù)，我們有n個(gè)數(shù)照底下的由小到大的排法：
根據(jù)定義我們有
P（3）=（1，2，2），
P（4）=（2，2，2，2），
P（5）=（2，2，3，3，3），
P（6）=（2，3，3，3，3，3）以及
P（7）=（2，3，3，4，4，4，4）
〔讀者請注意我們是怎樣定義這序列〕
現(xiàn)在我們可以敘述博薩的重要發(fā)現(xiàn)：
博薩定理 如果一個(gè)有n≥3個(gè)頂點(diǎn)的圖，它的d（G）滿足不等式d（G）≥P（n），那么G是哈密爾頓圖。
讓我們看以下的圖四（a）及（b），讀者很容易地看出
d（G5）=（2，2，3，3，4），
d（G4）=（3，3，3，3，3，3，3，3）。
它們都是哈密爾頓圖。G3不滿足奧勒的條件，因?yàn)閐（x）+d（y）=2+2=4 并不大過5。
可是我們卻看到d（G3）=（2，2，3，3，4）≥（2，2，3，3，3）=P（5）
因此由博薩定理知道它是哈密爾頓圖。由這個(gè)例子說明了博薩的結(jié)果是比奧勒的強(qiáng)。然而我們卻由G4看到它并不滿足博薩的不等式。因此人們嘗試想找比博薩更好的不等式以判別更多的哈密爾頓圖。
到目前來說，比較好的工作是捷克青年數(shù)學(xué)家薩瓦達(dá)（V. Chvátal）在1972年的發(fā)現(xiàn)，他的結(jié)果如下：
薩瓦達(dá)定理 如果圖G的頂點(diǎn)數(shù)n是大過2，而其d（G）=（a1，a2，…，an）滿足底下的條件：
ai≥i+1，an-i≥n-i最少有一個(gè)成立，那么G一定是哈密爾頓圖。
對數(shù)學(xué)有興趣的讀者可以試證明博薩的結(jié)果是包含在薩瓦達(dá)定理。我們的G4圖顯示它不滿足薩瓦達(dá)的條件，因此我們相信會存在比薩瓦達(dá)還要好的條件，這個(gè)問題就留給讀者自己去尋找。
三、旅行貨郎問題
如果我現(xiàn)在有一個(gè)圖G，而這圖的每一條弧上都算上一個(gè)數(shù)字，我要怎樣才能找到這圖的哈密頓回路具有所有的弧上數(shù)字的和是最小值的性質(zhì)，這個(gè)問題就是數(shù)學(xué)上大名鼎鼎的難題：“旅行貨郎問題”。
這問題在1932年由德國著名數(shù)學(xué)家K．Menger提出，這29年來是許多人廢寢忘食研究的對象。
我們在日常生活中就會遇到這問題，比方說：
（1）你是學(xué)校校車的司機(jī)，你從學(xué)校開車出來，到不同的街道去接孩子，你要怎樣安排使走的路程最短，可以接到所有的孩子回到學(xué)校去？
（2）春假到了，你想駕車在北美幾個(gè)城市旅行，可是現(xiàn)在汽油是這么昂貴，你想要盡量省用油，汽油的消耗是和路程成正比，因此你想法子找一個(gè)回路具有最短的路程。
（3）你為了商業(yè)業(yè)務(wù)，需要乘飛機(jī)飛幾個(gè)城市，不同的飛機(jī)公司提供不同的票價(jià)，你要怎樣安排行程，使到你能走遍你要去的城市，最后又回來原出發(fā)地，而又能省錢？
“旅行貨郎問題”是這么容易明白，可是要找出一個(gè)行之有效及能迅速提供解答的方法，目前并不存在。在28年前，美國的《管理科學(xué)》（Management Science 1963）一篇討論“旅行貨郎問題”的文章就說道：“人類由于他的運(yùn)算能力的限制在解決旅行貨郎問題上并不好。”人們現(xiàn)在對于這問題的實(shí)際情形都是借助高速的電子計(jì)算機(jī)來運(yùn)算。
我在以下會介紹一種直觀而又容易明白的樹的搜索法來尋找最優(yōu)解，目前解“旅行貨郎問題”有很多種方法，由于大部分要牽涉到較深的數(shù)學(xué)知識，因此我不在這里介紹。我最后會通過例子說明為什么這個(gè)看來小學(xué)生都能明白的問題卻是數(shù)學(xué)難題。
德國人很喜歡精確的數(shù)學(xué)，在1978年，波恩大學(xué)有一位數(shù)學(xué)家想要知道在西德的120個(gè)有鐵路穿過的城市要安排一個(gè)最短路程的回路，應(yīng)該怎么樣跑。他從鐵路局找到了準(zhǔn)確的城市間鐵路的長度，整個(gè)問題變成一個(gè)有7140個(gè)變數(shù)，120個(gè)方程及96個(gè)不等式的線性規(guī)劃問題，用電子計(jì)算機(jī)去算得到最短的回路是6942公里。（見圖五）。
四、樹的搜索法
我這里舉一個(gè)例子說明這個(gè)方法，假定我現(xiàn)在有四個(gè)城市A，B，C，D，它們之間的路程是由下面的表給出（見圖六）：
我要找從A出發(fā)回到A的最短回路。
我從A出發(fā)，我寫：（A）0。0是表示最初沒有出發(fā)路線長是0，然后我列下所有可能的下一個(gè)站：B，C，D，然后我得到三個(gè)節(jié)點(diǎn)（node）：（AB）1，（AC）3，（AD）2。
這時(shí)我就把（A）0劃掉，然后找節(jié)點(diǎn)具有最小的數(shù)值，這里是（AB）1。從B我可以走的站是C和D，我就劃掉（AB）1，用（ABC）1+4及（ABD）1+7來取代。為什么（ABC）旁的數(shù)字是1+4呢？因?yàn)樗牵ˋB）加上（BC）的長。（見圖七）。
我們把沒劃掉的節(jié)點(diǎn)中有最小長度的找出，這是（AD）2D的下一個(gè)可能的站是B和C，因此我們劃掉（AD）2補(bǔ)上兩個(gè)節(jié)點(diǎn)（ADB）2+7及（ADC）2+5。
我們繼續(xù)找具有最小長度的節(jié)點(diǎn)，這時(shí)看到是（AC）3從C出發(fā)可以到達(dá)B或D，于是我們劃掉（AC）3，補(bǔ)上（ACB）3+4，（ACD）3+5。（見圖七（e））
我們再搜索有最小長度的節(jié)點(diǎn)，看到是（ABC）5，于是劃掉它，補(bǔ)上（ABCD）5+5，得圖七（f）。
我們再搜索沒有被劃的節(jié)點(diǎn)，看到有最小長度的是（ACB）7及（ADC）7，我就先劃掉（ACB）7補(bǔ)上（ACBD）7+7，得圖七（g）。
然后我再劃掉（ADC）7補(bǔ)上（ADCB）7+4得圖七（h）。
這時(shí)候我看剩下沒劃線的最小長度的節(jié)點(diǎn)是：（ABD）8及（ACD）8，我劃掉了比方說（ABD）8，補(bǔ)上（ABDC）8+5。
我再尋找最小長度的節(jié)點(diǎn)得（ACB）8，劃掉之后補(bǔ)上了（ACDB）8+7，得圖七（j）。
現(xiàn)在變成（ADB）9是最小長度的節(jié)點(diǎn)，我們劃掉補(bǔ)上（ADBC）9+4，得圖七（k），我們劃去（k）的最小長度節(jié)點(diǎn)（ABCD）10，補(bǔ)上（ABCDA）10+2。我們已得到一個(gè)回路了，這時(shí)我們把（1）圖中所有長度大過12，節(jié)點(diǎn)全劃掉，因?yàn)檫@些節(jié)點(diǎn)所產(chǎn)生的回路肯定要大過12，我們可以不考慮，我們只剩下（ADCB）11，劃掉它之后補(bǔ)上（ADCBA）11+1，我們得（k）。
謝天謝地，到此時(shí)我們再沒有什么節(jié)點(diǎn)可以劃了，我們得到兩個(gè)回路（ABCDA）及（ADCBA），它們的長都是12。這種方法在數(shù)學(xué)上有一個(gè)名稱叫 uniformcost Search。為了說明整個(gè)搜索的程序，我畫了許多像樹枝分叉的圖，實(shí)際上讀者只需在一個(gè)圖上劃線及向下發(fā)展不必畫這么多樹。通常哈密爾頓回路找到之后，我們選取最少的長度，那就是我們所要的答案。
五、為什么數(shù)學(xué)家和電腦專家對貨郎問題發(fā)生興趣
我們前面介紹的方法在城市數(shù)目字比方說不超過十個(gè)還不顯得可怕。如果現(xiàn)在有21個(gè)城市用以上的方法去搜索最短的回路，我們最少要找超過九十萬個(gè)以上的路線，這是多么巨大的數(shù)字呀！
現(xiàn)在請想一想，如果我們要處理的是五百個(gè)城市，或者一千個(gè)城市，或者就拿像中國這么大的國家，這么多的縣城，要處理這問題，用目前最快速的電子計(jì)算機(jī)來協(xié)助，也會使電子計(jì)算機(jī)掛投降的白旗，宣稱：“我的記憶不夠處理這些問題產(chǎn)生出來的數(shù)值，對不起哥哥，我不能替你效勞�！�
我前面介紹的樹的搜索法是一個(gè)比較簡單但并不是太好的方法，這20年來，許多人想出一些方法想要改進(jìn)，希望能找到一個(gè)較理想的方法，可以快速的找到結(jié)果。目前來說這樣理想的方法還沒有找到。
什么樣的方法算是理想呢？我們這里給一個(gè)粗略的解釋：比方說我們要用電子計(jì)算機(jī)來幫我們工作，例如處理n個(gè)城市的旅行貨郎問題，當(dāng)我把n個(gè)城市的距離表喂給電子計(jì)算機(jī)之后，它就會一步一步的去找。如果它要得到答案，所要花費(fèi)的步驟數(shù)目是可以用n的函數(shù)f（n）來表示。我們說這方法是“理想”，當(dāng)f（n）是一個(gè)n的多項(xiàng)式。
目前我們的方法都不是理想的。如果你真能找到一個(gè)理想的方法，你的成果會轟動(dòng)全世界。你的方法可以轉(zhuǎn)化用來解決許多數(shù)學(xué)的難題及電子計(jì)算機(jī)理論的一些著名難題。
旅行貨郎問題是許多國家的運(yùn)籌學(xué)研究中心的工作者深入研究的問題。在美國的華籍?dāng)?shù)學(xué)工作者在這方面有很好的結(jié)果的有 Lin Shen及Hong Saman等人。在1977年Hong先生和Padberg 合作用電子計(jì)算機(jī)處理有318個(gè)城市的“旅行貨郎問題”，這個(gè)問題化成線性規(guī)劃問題就要處理有50403個(gè)變數(shù)（variables）的方程式，及不等式，如果不借助電子計(jì)算機(jī)的快速計(jì)算，我想就是請一位能筆算及心算很快的數(shù)學(xué)家，讓他窮十年的時(shí)間也是不能解決。以上的問題他們用IBM 370-168式的電子計(jì)算機(jī)，只花28.38分鐘就得到一個(gè)最優(yōu)解。
“玩物喪志”，這是以前老一輩的人罵兒童或少年不讀書只喜歡游戲所愛用的一句話。其實(shí)游戲和玩具可以引導(dǎo)大發(fā)現(xiàn)。如果有青少年肯對哈密爾頓圖及旅行貨郎問題下點(diǎn)苦功研究，我會說他們是“玩物立志”，很可能以后會出一些在這些問題上作出大貢獻(xiàn)的中國人。
六、動(dòng)腦筋想想看：
1．尋找下面幾個(gè)圖的哈密爾頓回路：
2．在下面的3×3方格里，如果我在最左上角放一只馬，然后讓馬依以下的數(shù)值跑（中國象棋的馬跑日的跑法）最后會有一個(gè)空位不能跑，但它能走回原來出發(fā)的位置。
試證明除了中間的方格不許放馬外，任何其它方格放馬出去它最后又能跑回原先出發(fā)的位置──我們要求跑過的位置不能再回去。
3．對于4×4及5×5的方格，你研究在什么樣的位置放馬可以無重復(fù)的跑遍全部的方格。研究在什么情況下有多過一組的解答。你可以把找到的解答寄來編輯部。
4．給出任何兩個(gè)正整數(shù)m、n，我們可以構(gòu)造一個(gè)特別的圖：
X=｛x1，x2，…，xm｝，
Y=｛y1，y2，…，yn｝，
任何在X里的x要和在Y里的每一個(gè)y用弧聯(lián)結(jié)；而任何在Y里的y也要和每一個(gè)在X里的x相連，X之間的點(diǎn)及Y之間的點(diǎn)不要連結(jié)。證明只有當(dāng)m=n時(shí)我們才能找到哈密爾頓回路。
5．下面的圖不可能存在哈密爾頓回路（見圖九）：
本文來自：逍遙右腦記憶 http://m.yy-art.cn/gaozhong/185681.html
相關(guān)閱讀：高一新生如何做好數(shù)學(xué)作業(yè)