小學數(shù)學游戲：旅程問題

　　【游戲題】

　　有些時候，我們必須去很多地方辦事，再回到原出發(fā)點，所以我們通常會先規(guī)劃出最順路(最短)的路徑。此類問題被稱為銷售員的旅程問題，因為這是銷售員的工作中最常碰到的問題。

　　在許多場合都會碰到此類問題，比如說：油罐車駕駛員到各個加油站巡回加油；一位觀光客想到劍橋、史特佛、愛丁堡、浦利茅斯等處旅游。

圖2

　　化妝品銷售員李文黛小姐欲去圖中的每個小鎮(zhèn)推銷新產(chǎn)品。她打算由艾克塞特出發(fā)(見圖1)。地圖中的數(shù)字為兩小鎮(zhèn)間的距離，單位是km。如果出發(fā)點及終點皆為艾克塞特的話，則最短的行程數(shù)是多少？

　　解此類問題最常用的方法為最近城市法。此方法是先前往最靠近起點艾克塞特的城鎮(zhèn)——克雷頓，然后再去最靠近克雷頓且尚未到過的城鎮(zhèn)，依此類推。這種方法產(chǎn)生圖2中的解。在此圖中我們首先走完一路徑：艾克塞特→克雷頓→提文頓→卡林頓→艾克茅茲→艾克塞特；然后再走到另一路徑：艾克塞特→歐卡漢頓→艾克塞特。

圖3

　　此方法的總里程數(shù)是107km，但這并不是最短的行程。在現(xiàn)實生活中我們可能會選擇道路品質(zhì)佳以及路況良好的路線以節(jié)省時間。但是在本題中我們只求最短的路徑即可，你能找出來嗎？

　　假設現(xiàn)在李文黛又把漢尼頓列入她的行程之中(見圖3)，那么整個行程的最短路徑為多少km(出發(fā)點及終點仍然為艾克塞特)？如果將出發(fā)點及終點皆改為卡林頓，會不會使整個行程變得較短呢？

　　若以不同的小鎮(zhèn)為起點及終點會影響到總里程數(shù)嗎？

　　如果李文黛的起點及終點可以不同，那么她該選擇哪兩個小鎮(zhèn)為起點和終點，以使整個行程為最短？

　　數(shù)學家們在這個問題的解法上曾耗費許多心思，但到目前為止尚未成功。現(xiàn)在可確定的是在最短的路徑中，各個路徑彼此不可相交。然而他們發(fā)現(xiàn)若城鎮(zhèn)的數(shù)目增加很多時，此解法又不適用了。

圖4

【答案請看下一頁】