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

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

　　(1)油罐車的駕駛員必須將汽油運至各個加油站．

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

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

　　化妝品推銷員李文黛小姐欲訪問圖1中的每個小鎮(zhèn)，去推銷新產(chǎn)品，她打算由艾克塞特出發(fā)．地圖上所標示的數(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ù)學家們曾耗費許多心思以解決這類問題，但是到目前為止尚未成功．但他們知道在最短的路徑中，各條路線彼此不可交錯．然而當他們發(fā)現(xiàn)正確的解法時，若城鎮(zhèn)的數(shù)目增加很多，又不適用了．他們甚至采用了先進的大型電腦作為輔助工具，利用系統(tǒng)的“試誤法”．要找到“好”的解(可能并不是最好的)，方法很多，但如果有人能找到一個直接且快速的方法求得最佳路徑，肯定會聲名大噪！

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

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

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

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