有些時(shí)候，我們必須去很多不同的地方辦事，然后回到原出發(fā)點(diǎn)，所以我們通常想要找到最短的路徑．這類問題被稱為推銷員的旅程問題，因?yàn)檫@是推銷員在工作中最常遇到的問題．
然而，這也是許多人所要解決的問題，例如：
(1)油罐車的駕駛員必須將汽油運(yùn)至各個(gè)加油站．
(2)運(yùn)牛奶的卡車司機(jī)必須開車去分散在各地的農(nóng)場．
(3)一位游客想要到劍橋、斯坦福、愛丁堡、樸利茅斯與巨石柱群等地旅游．
化妝品推銷員李文黛小姐欲訪問圖1中的每個(gè)小鎮(zhèn)，去推銷新產(chǎn)品，她打算由艾克塞特出發(fā)．地圖上所標(biāo)示的數(shù)字為兩小鎮(zhèn)之間的距離，如果出發(fā)點(diǎn)與終點(diǎn)皆在艾克塞特的話，則最短的路徑是怎樣的？
解決此種問題較常用的方法為最近城市法．此方法是先前往距離起點(diǎn)艾克塞特最近的城鎮(zhèn)克雷頓，然后再去最靠近克雷頓且尚未到過的城鎮(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è)馁M(fèi)許多心思以解決這類問題，但是到目前為止尚未成功．但他們知道在最短的路徑中，各條路線彼此不可交錯(cuò)．然而當(dāng)他們發(fā)現(xiàn)正確的解法時(shí)，若城鎮(zhèn)的數(shù)目增加很多，又不適用了．他們甚至采用了先進(jìn)的大型電腦作為輔助工具，利用系統(tǒng)的“試誤法”．要找到“好”的解(可能并不是最好的)，方法很多，但如果有人能找到一個(gè)直接且快速的方法求得最佳路徑，肯定會(huì)聲名大噪！
英國每年都有成千上萬的青少年會(huì)參加著名的“十巖探險(xiǎn)”，整個(gè)探險(xiǎn)路線包括要探訪的所有著名的巖石地帶(花崗巖通常露在山丘之頂)，如地圖中所顯示的地點(diǎn)(圖5)．在正式探險(xiǎn)之前
幾個(gè)月的周末，經(jīng)常可以發(fā)現(xiàn)一些人在當(dāng)?shù)剡M(jìn)行野外訓(xùn)練．某個(gè)周末，一支隊(duì)伍先在地圖上規(guī)劃路線，他們打算由布雷克巖出發(fā)，然后經(jīng)過圖上標(biāo)示的所有地方再回到出發(fā)點(diǎn)，他們希望盡可能找到最短的路徑．
解決此類問題的一個(gè)方法是先將地圖描在紙上，并將紙固定在畫板上．然后將釘子釘在每一個(gè)要探訪的地方，再用不同長度、不同顏色的棉線來標(biāo)出可能的路徑，其中最短的線段當(dāng)然就對(duì)應(yīng)于最佳的路徑(圖6)．
你也可以利用地圖來研究一下這類問題．
