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

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

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

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

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

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

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

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

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

　　解答與分析

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

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

　　23 16 11 8 13 10

　　茅茲→艾克塞特

　　10

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

　　因?yàn)樽疃绦谐痰母髀肪�彼此不相交錯，故其行程為一簡單的封閉曲線，所以不論以哪一個小鎮(zhèn)為起點(diǎn)及終點(diǎn)，其里程數(shù)均相等。

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