小學數學游戲：旅程問題

　　【游戲題】

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

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

圖2

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

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

圖3

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

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

　　若以不同的小鎮為起點及終點會影響到總里程數嗎？

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

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

圖4

【答案請看下一頁】