有些時候，我們必須去很多不同的地方辦事，然后回到原出發(fā)點，所以我們
通常想要找到最短的路徑。這類問題被稱為推銷員的旅程問題，因為這是推銷員
在工作中最常遇到的問題。

    然而，這也是許多人所要解決的問題，例如：

    （1 ）油罐車的駕駛員必須將汽油運至各個加油站。

    （2 ）運牛奶的卡車司機必須開車去分散在各地的農(nóng)場。

    （3 ）一位游客想要到劍橋、斯坦福、愛丁堡、樸利茅斯與巨石柱群等地旅
游。

    化妝品推銷員李文黛小姐欲訪問圖1 中的每個小鎮(zhèn)，去推銷新產(chǎn)品，她打算
由艾克塞特出發(fā)。地圖上所標(biāo)示的數(shù)字為兩小鎮(zhèn)之間的距離，如果出發(fā)點與終點
皆在艾克塞特的話，則最短的路徑是怎樣的？

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

    此方法的總里程數(shù)為107 英里（1 英里=1.609千米），但并不是最短行程。

    在現(xiàn)實生活中，我們可能會選擇道路品質(zhì)佳及路況良好的路徑以節(jié)省時間，
但在本題我們只要找出最短的路徑即可。

    你自己可能會發(fā)現(xiàn)如圖3 的解，此解的基本想法是將所有的城鎮(zhèn)連成一個回
路，所得出的答案為92英里。這個答案雖比前面的好得多了，但還不是最佳的解。

    最佳路徑的里程只有91英里，你能找到嗎？

    假設(shè)現(xiàn)在李文黛又把漢尼頓列入她的行程之中（圖4 ），那么整個行程的最
短路徑為何（其出發(fā)點與終點仍為艾克塞特）？如果將出發(fā)點及終點皆改為卡林
頓，會不會使整個行程變得較短呢？如果以不同的城鎮(zhèn)為起點與終點，是否會影
響總里程數(shù)呢？

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

    數(shù)學(xué)家們曾耗費許多心思以解決這類問題，但是到目前為止尚未成功。但他
們知道在最短的路徑中，各條路線彼此不可交錯。然而當(dāng)他們發(fā)現(xiàn)正確的解法時，
若城鎮(zhèn)的數(shù)目增加很多，又不適用了。他們甚至采用了先進的大型電腦作為輔助
工具，利用系統(tǒng)的“試誤法”。要找到“好”的解（可能并不是最好的），方法
很多，但如果有人能找到一個直接且快速的方法求得最佳路徑，肯定會聲名大噪！

    英國每年都有成千上萬的青少年會參加著名的“十巖探險”，整個探險路線
包括要探訪的所有著名的巖石地帶（花崗巖通常露在山丘之頂），如地圖中所顯
示的地點（圖5 ）。在正式探險之前

    幾個月的周末，經(jīng)�？梢园l(fā)現(xiàn)一些人在當(dāng)?shù)剡M行野外訓(xùn)練。某個周末，一支
隊伍先在地圖上規(guī)劃路線，他們打算由布雷克巖出發(fā)，然后經(jīng)過圖上標(biāo)示的所有
地方再回到出發(fā)點，他們希望盡可能找到最短的路徑。

    解決此類問題的一個方法是先將地圖描在紙上，并將紙固定在畫板上。然后
將釘子釘在每一個要探訪的地方，再用不同長度、不同顏色的棉線來標(biāo)出可能的
路徑，其中最短的線段當(dāng)然就對應(yīng)于最佳的路徑（圖6 ）。

    你也可以利用地圖來研究一下這類問題。