千文網(wǎng)小編為你整理了多篇相關(guān)的《小學(xué)詩詞游戲活動方案》，但愿對你工作學(xué)習(xí)有幫助，當(dāng)然你在千文網(wǎng)還可以找到更多《小學(xué)詩詞游戲活動方案》。

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

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

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

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

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

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

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

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

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

解答與分析

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

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

23161181310

茅茲→艾克塞特

10

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

因為最短行程的各路線彼此不相交錯，故其行程為一簡單的封閉曲線，所以不論以哪一個小鎮(zhèn)為起點及終點，其里程數(shù)均相等。

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