久久国产精品系列精品,乱淫av一区二区三区,在线观看你懂的小视频,日韩 激情 人妻 在线,国产精品视频第3页,亚洲,欧美,日韩,网站,五十路熟妇工口动画,中国人妻一区二区三区,日产国产一区二区不卡

1979年11月7日《紐約時報》出現一篇引人注目的文章，它的標題是：《蘇聯的發現震動數學界》（Soviet Discovery Rocks World of Mathematics），這文章介紹一個本是默默無聞的年青數學家卡倩（L．G．Khachian），他在線性規劃理論上的一個發現使到美國數學界為之轟動。由于記者在詢問一些著名數學家時對數學問題了解不深，文章報導是有一些失實，但由這文章引起的轟動及誤導是相當嚴重。我以后會討論這問題。該文中說：“俄國人的發現建議用電子計算機處理一類和‘旅行貨郎問題’（Travelling Salesman Problem）有關的數學上一個著名及難處理的問題。‘旅行貨朗問題’目的是決定一個貨郎（或推銷員或銷貨員）所要跑的最短路程──他要走遍市鎮，但是不能再回到走過的地方。表面上，這問題看來簡單，事實上為了要解決這問題的實際應用，人們需要電子計算機來解決。”

在這點上這記者是說對了。“旅行貨郎問題”目前是許多國家（如西德、日本、蘇聯、英國、美國、法國）的運籌學工作者研究的熱烈課題。為了要了解這問題，我們可要知道目前在圖論（Graph Theory）上許多人正在研究一種圖──哈密爾頓圖（Hemilton graphs）。

一、哈密爾頓圖的由來

在17—18世紀時，歐洲宮庭及一些貴族很喜歡玩西洋象棋，西洋象棋中的騎士（knight）是對應我們中國象棋的“馬”，而它通常是刻成一個馬頭，跑法也是和中國象棋的“馬”一樣，走“日”線──即從日的一角沿著對角線躍到另一角。

在1771年，就有一位名叫范德蒙（A．Vandermonde）的法國數學家，寫了一篇文章研究所謂“棋盤的騎士問題”。這問題是這樣：在8×8的棋盤格的隨意一個位置，我放一個騎士，然后我想法子使他跑遍棋盤的所有的格子，走過的不許再走，我能不能使騎士最后回到原來的位置？

這個問題并不簡單，許多象棋愛好者及數學家曾坐下來研究這個問題。我這里列出一個情形的解（見圖一），我將棋盤的左下角的格選為起始位置，把它定為1，讀者可以驗證根據圖一的跑法，騎士最后是能跑回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

圖一 “棋盤騎士問題”的一個解法

18世紀的大數學家歐拉（Euler），在1759年就系統地研究過這個問題，也得到了一些結果。以后德國數學家高斯也曾對這問題發生興趣，花過一些時間研究它及另外一個棋盤的“皇后問題”。

我們現在把棋盤上的格子對應在一個平面上的一個小圓點，這樣我們在平面上就有64個小圓點。從一個格子用騎士的走法我們可以抵達不同數目的格子：如果是處在棋盤的四個角，只能有兩種跑法；在其他邊緣的格子就有三種跑法；一般當中的格子，就有四種可能的跑法。我們把平面上的點用弧線連接，兩個點有一條弧線連起當且僅當（if and only if）我們可以從它們所對應的格子將騎士移動。我們得到了一個圖（ graph）。

在圖中取一個頂點v0，如果我們有一個弧線把它和另外一個點v1聯起來，我們就用（v0，v1）來表示這個弧線。假定我有一系列點v0，v1，v2，…，vn其中沒有兩個相同以及一序列的弧線存在（v0，v1），（v1，v2），…，（vn-1，vn），（vn，v0），使到我從v0出發可以經過v1，v2，…，vn最后由vn回到v0，我就說這些弧線組成一個回路（circuit），為了方便，我們用下面的記號表示這回路：（v0，v1，v2，…，vn，v0）。

如果我有一個圖G有n+1個頂點（vertices）{v0，v1，v2，…，vn}，而我能找到一個回路（v0，v1，v2，…，vn，v0），那么我就說這個圖是哈密爾頓圖（Hamilton graph），這個回路稱為哈密爾頓回路（Hamilton circuit）。

因此，“棋盤的騎士問題”實際上就是要判斷它所對應的圖是否是哈密爾頓圖的問題。

為什么叫哈密爾頓圖？哈密爾頓是誰呢？

哈密爾頓是愛爾蘭的一位數學家和天文學家。他的一生是多姿多彩的，我在《數學和數學家的故事》第一集里有詳細介紹他的工作和生平，讀者可以找來一讀。

自從哈密爾頓發現“四元數”之后，他又發現了另外一種他命名為“The Icosian Calculus”的代數系統，這系統有加和乘的運算子（operators），可是乘法不滿足交換律（Commutative law即xy=yx這個規律）。

他發現這代數系統是和正則20面體（regularicosion polybedron）有關系。他想到一個游戲，怎樣跑遍正則多面體上的所有頂點，而最后又能回到起點的問題。在1857年他把這個游戲的想法以25英鎊的價錢賣給一位玩具和游戲制造商。這25英鎊在124年前是很好用，在今天拿去倫敦的“唐人區”買“牛腩面”吃可能連十碗都吃不到。

這玩具商把這游戲制造出來了（見圖二），在圓盤上有20個代表城市的圓孔，你必須把20個上面標有1，2，3，…，20的木條順序插進去，代表你經過不同的城市，最后回到原出發點。這個游戲叫“環游世界”，很可惜玩具商人沒有從這游戲上賺到錢。

以后人們因這游戲就稱這類圖為哈密爾頓圖。

THE ICOSIAN GAME

二、怎么樣的圖是哈密爾頓圖

給你一個圖，你怎么知道它是否是哈密爾頓圖呢？當然如果圖的頂點不多，你可以試試找哈密爾頓回路就可以解決和判斷。你用的是最古老的“嘗試和錯誤”的方法，但是數學家并不滿意這樣的碰得焦頭爛額后才找到真理的方法。是否存在一組必要和充分的條件，使到我們能簡單輕易地判斷一個圖是否哈密爾頓圖？許多聰明人去試過了，很可惜到現在這問題還未解決，因此讀者可以試試自己來找尋一下。

英國數學家G．A．狄拉克（Dirac）在1952年給出一個充分條件使得一個圖會是哈密爾頓圖。他的定理是只要檢查每一個頂點x，看它的上面有多少個弧通過，把這個數目用d（x）來表示，只要每一個點的d（x）是相當大的話，這圖就會是哈密爾頓圖。

狄拉克定理 給定一個圖G，如果其頂點集V的元素數是n≥3，

由于我們可以看到以下的兩個圖G1，G2都是哈密爾頓圖（見圖三）。
　　

到了1960年，美國著名的圖論專家奧斯坦·奧勒（ Oystein Ore）推廣狄拉克的工作，得到以下的結果。

奧勒定理 給定一個圖G，如果其頂點集V是有n≥3點，而對于任意兩點x，y我們有d（x）+d（y）≥n，那么G一定是哈密爾頓圖。

在1962年，匈牙利有一個少年發表了一篇只有一頁長的論文，他的結果卻是推廣了以上奧勒的定理，他的工作是這么重要引起許多人談論，并且在圖論的教科書上登他的證明。以后幾年來許多人想要改進這工作，最后才由一個捷克青年數學家得到比他更好的結果。

這個少年名叫博薩（Posa），我在《數學和數學家的故事》第一集的一篇文章就有介紹他的事跡，讀者想要知道他的故事可以看看該文。

為了能更容易看清博薩的結果，我這里引進幾個記號：對于每一個圖G，我們用d（G）來表示序列如（d（x1），d（x2），…，d（xn）），這里x1，…，xn是G的所有頂點，而序列的數是從小排到大去排列。比方說在圖三里我們有

d（G1）=（3，3，3，3）

d（G2）=（4，4，4，4，4，4）

假定我們有兩個序列具有相同個數的數字：

X=（x1，x2，x3，…xn）；

Y=（y1，y2，y3，…，yn）

我們用X≤Y表示當且僅當對于每個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是不對的。

現在對于每個n≥3的整數，我們定義這樣的整數序列P（n）

（1）如果n是偶數，我們有n個數照底下由小到大的排法：

（2）如果n是奇數，我們有n個數照底下的由小到大的排法：

根據定義我們有

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）

〔讀者請注意我們是怎樣定義這序列〕

現在我們可以敘述博薩的重要發現：

博薩定理 如果一個有n≥3個頂點的圖，它的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不滿足奧勒的條件，因為d（x）+d（y）=2+2=4 并不大過5。

可是我們卻看到d（G3）=（2，2，3，3，4）≥（2，2，3，3，3）=P（5）

因此由博薩定理知道它是哈密爾頓圖。由這個例子說明了博薩的結果是比奧勒的強。然而我們卻由G4看到它并不滿足博薩的不等式。因此人們嘗試想找比博薩更好的不等式以判別更多的哈密爾頓圖。

到目前來說，比較好的工作是捷克青年數學家薩瓦達（V. Chvátal）在1972年的發現，他的結果如下：

薩瓦達定理 如果圖G的頂點數n是大過2，而其d（G）=（a1，a2，…，an）滿足底下的條件：
ai≥i+1，an-i≥n-i最少有一個成立，那么G一定是哈密爾頓圖。

對數學有興趣的讀者可以試證明博薩的結果是包含在薩瓦達定理。我們的G4圖顯示它不滿足薩瓦達的條件，因此我們相信會存在比薩瓦達還要好的條件，這個問題就留給讀者自己去尋找。

三、旅行貨郎問題

如果我現在有一個圖G，而這圖的每一條弧上都算上一個數字，我要怎樣才能找到這圖的哈密頓回路具有所有的弧上數字的和是最小值的性質，這個問題就是數學上大名鼎鼎的難題：“旅行貨郎問題”。

這問題在1932年由德國著名數學家K．Menger提出，這29年來是許多人廢寢忘食研究的對象。

我們在日常生活中就會遇到這問題，比方說：

（1）你是學校校車的司機，你從學校開車出來，到不同的街道去接孩子，你要怎樣安排使走的路程最短，可以接到所有的孩子回到學校去？

（2）春假到了，你想駕車在北美幾個城市旅行，可是現在汽油是這么昂貴，你想要盡量省用油，汽油的消耗是和路程成正比，因此你想法子找一個回路具有最短的路程。

（3）你為了商業業務，需要乘飛機飛幾個城市，不同的飛機公司提供不同的票價，你要怎樣安排行程，使到你能走遍你要去的城市，最后又回來原出發地，而又能省錢？

“旅行貨郎問題”是這么容易明白，可是要找出一個行之有效及能迅速提供解答的方法，目前并不存在。在28年前，美國的《管理科學》（Management Science 1963）一篇討論“旅行貨郎問題”的文章就說道：“人類由于他的運算能力的限制在解決旅行貨郎問題上并不好。”人們現在對于這問題的實際情形都是借助高速的電子計算機來運算。

我在以下會介紹一種直觀而又容易明白的樹的搜索法來尋找最優解，目前解“旅行貨郎問題”有很多種方法，由于大部分要牽涉到較深的數學知識，因此我不在這里介紹。我最后會通過例子說明為什么這個看來小學生都能明白的問題卻是數學難題。

德國人很喜歡精確的數學，在1978年，波恩大學有一位數學家想要知道在西德的120個有鐵路穿過的城市要安排一個最短路程的回路，應該怎么樣跑。他從鐵路局找到了準確的城市間鐵路的長度，整個問題變成一個有7140個變數，120個方程及96個不等式的線性規劃問題，用電子計算機去算得到最短的回路是6942公里。（見圖五）。

四、樹的搜索法

我這里舉一個例子說明這個方法，假定我現在有四個城市A，B，C，D，它們之間的路程是由下面的表給出（見圖六）：

我要找從A出發回到A的最短回路。

我從A出發，我寫：（A）0。0是表示最初沒有出發路線長是0，然后我列下所有可能的下一個站：B，C，D，然后我得到三個節點（node）：（AB）1，（AC）3，（AD）2。

這時我就把（A）0劃掉，然后找節點具有最小的數值，這里是（AB）1。從B我可以走的站是C和D，我就劃掉（AB）1，用（ABC）1+4及（ABD）1+7來取代。為什么（ABC）旁的數字是1+4呢？因為它是（AB）加上（BC）的長。（見圖七）。

我們把沒劃掉的節點中有最小長度的找出，這是（AD）2D的下一個可能的站是B和C，因此我們劃掉（AD）2補上兩個節點（ADB）2+7及（ADC）2+5。

我們繼續找具有最小長度的節點，這時看到是（AC）3從C出發可以到達B或D，于是我們劃掉（AC）3，補上（ACB）3+4，（ACD）3+5。（見圖七（e））

我們再搜索有最小長度的節點，看到是（ABC）5，于是劃掉它，補上（ABCD）5+5，得圖七（f）。

我們再搜索沒有被劃的節點，看到有最小長度的是（ACB）7及（ADC）7，我就先劃掉（ACB）7補上（ACBD）7+7，得圖七（g）。

然后我再劃掉（ADC）7補上（ADCB）7+4得圖七（h）。

這時候我看剩下沒劃線的最小長度的節點是：（ABD）8及（ACD）8，我劃掉了比方說（ABD）8，補上（ABDC）8+5。

我再尋找最小長度的節點得（ACB）8，劃掉之后補上了（ACDB）8+7，得圖七（j）。

現在變成（ADB）9是最小長度的節點，我們劃掉補上（ADBC）9+4，得圖七（k），我們劃去（k）的最小長度節點（ABCD）10，補上（ABCDA）10+2。我們已得到一個回路了，這時我們把（1）圖中所有長度大過12，節點全劃掉，因為這些節點所產生的回路肯定要大過12，我們可以不考慮，我們只剩下（ADCB）11，劃掉它之后補上（ADCBA）11+1，我們得（k）。

謝天謝地，到此時我們再沒有什么節點可以劃了，我們得到兩個回路（ABCDA）及（ADCBA），它們的長都是12。這種方法在數學上有一個名稱叫 uniformcost Search。為了說明整個搜索的程序，我畫了許多像樹枝分叉的圖，實際上讀者只需在一個圖上劃線及向下發展不必畫這么多樹。通常哈密爾頓回路找到之后，我們選取最少的長度，那就是我們所要的答案。

五、為什么數學家和電腦專家對貨郎問題發生興趣

我們前面介紹的方法在城市數目字比方說不超過十個還不顯得可怕。如果現在有21個城市用以上的方法去搜索最短的回路，我們最少要找超過九十萬個以上的路線，這是多么巨大的數字呀！

現在請想一想，如果我們要處理的是五百個城市，或者一千個城市，或者就拿像中國這么大的國家，這么多的縣城，要處理這問題，用目前最快速的電子計算機來協助，也會使電子計算機掛投降的白旗，宣稱：“我的記憶不夠處理這些問題產生出來的數值，對不起哥哥，我不能替你效勞。”

我前面介紹的樹的搜索法是一個比較簡單但并不是太好的方法，這20年來，許多人想出一些方法想要改進，希望能找到一個較理想的方法，可以快速的找到結果。目前來說這樣理想的方法還沒有找到。

什么樣的方法算是理想呢？我們這里給一個粗略的解釋：比方說我們要用電子計算機來幫我們工作，例如處理n個城市的旅行貨郎問題，當我把n個城市的距離表喂給電子計算機之后，它就會一步一步的去找。如果它要得到答案，所要花費的步驟數目是可以用n的函數f（n）來表示。我們說這方法是“理想”，當f（n）是一個n的多項式。

目前我們的方法都不是理想的。如果你真能找到一個理想的方法，你的成果會轟動全世界。你的方法可以轉化用來解決許多數學的難題及電子計算機理論的一些著名難題。

旅行貨郎問題是許多國家的運籌學研究中心的工作者深入研究的問題。在美國的華籍數學工作者在這方面有很好的結果的有 Lin Shen及Hong Saman等人。在1977年Hong先生和Padberg 合作用電子計算機處理有318個城市的“旅行貨郎問題”，這個問題化成線性規劃問題就要處理有50403個變數（variables）的方程式，及不等式，如果不借助電子計算機的快速計算，我想就是請一位能筆算及心算很快的數學家，讓他窮十年的時間也是不能解決。以上的問題他們用IBM 370-168式的電子計算機，只花28.38分鐘就得到一個最優解。

“玩物喪志”，這是以前老一輩的人罵兒童或少年不讀書只喜歡游戲所愛用的一句話。其實游戲和玩具可以引導大發現。如果有青少年肯對哈密爾頓圖及旅行貨郎問題下點苦功研究，我會說他們是“玩物立志”，很可能以后會出一些在這些問題上作出大貢獻的中國人。

六、動腦筋想想看：

1．尋找下面幾個圖的哈密爾頓回路：

2．在下面的3×3方格里，如果我在最左上角放一只馬，然后讓馬依以下的數值跑（中國象棋的馬跑日的跑法）最后會有一個空位不能跑，但它能走回原來出發的位置。

試證明除了中間的方格不許放馬外，任何其它方格放馬出去它最后又能跑回原先出發的位置──我們要求跑過的位置不能再回去。

3．對于4×4及5×5的方格，你研究在什么樣的位置放馬可以無重復的跑遍全部的方格。研究在什么情況下有多過一組的解答。你可以把找到的解答寄來編輯部。

4．給出任何兩個正整數m、n，我們可以構造一個特別的圖：

X=｛x1，x2，…，xm｝，

Y=｛y1，y2，…，yn｝，

任何在X里的x要和在Y里的每一個y用弧聯結；而任何在Y里的y也要和每一個在X里的x相連，X之間的點及Y之間的點不要連結。證明只有當m=n時我們才能找到哈密爾頓回路。

5．下面的圖不可能存在哈密爾頓回路（見圖九）：