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

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

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

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

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

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

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

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

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

　　解答與分析

　　李文黛的最短路徑是91 km，她的行程為：

　　艾克塞特→歐卡漢頓→克雷頓→提文頓→卡林頓→艾克塞特→艾克

　　23 16 11 8 13 10

　　茅茲→艾克塞特

　　10

　　如果把漢尼頓列入行程中，則最短行程為艾克塞特→歐卡漢頓→克雷頓→提文頓→卡林頓→漢尼頓→艾克茅茲→艾克塞特，總里程數為 100 km。

　　因為最短行程的各路線彼此不相交錯，故其行程為一簡單的封閉曲線，所以不論以哪一個小鎮(zhèn)為起點及終點，其里程數均相等。

　　但是如果起點和終點都不同，那么只要將整個行程顛倒過來(依原行程的反向而行)，以艾克塞特為起點，歐卡漢頓為終點，則可節(jié)省23 km的路程。