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

    然而，這也是許多人所要解決的問(wèn)題，例如：

    （1 ）油罐車的駕駛員必須將汽油運(yùn)至各個(gè)加油站。

    （2 ）運(yùn)牛奶的卡車司機(jī)必須開(kāi)車去分散在各地的農(nóng)場(chǎng)。

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

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

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

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

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

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

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

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

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

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

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

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

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

    你也可以利用地圖來(lái)研究一下這類問(wèn)題。