有些时候，我们必须去很多不同的地方办事，然后回到原出发点，所以我们通常想要找到最短的路径．这类问题被称为推销员的旅程问题，因为这是推销员在工作中最常遇到的问题．
然而，这也是许多人所要解决的问题，例如：
(1)油罐车的驾驶员必须将汽油运至各个加油站．
(2)运牛奶的卡车司机必须开车去分散在各地的农场．
(3)一位游客想要到剑桥、斯坦福、爱丁堡、朴利茅斯与巨石柱群等地旅游．
化妆品推销员李文黛小姐欲访问图1中的每个小镇，去推销新产品，她打算由艾克塞特出发．地图上所标示的数字为两小镇之间的距离，如果出发点与终点皆在艾克塞特的话，则最短的路径是怎样的？
解决此种问题较常用的方法为最近城市法．此方法是先前往距离起点艾克塞特最近的城镇克雷顿，然后再去最靠近克雷顿且尚未到过的城镇，依此类推．用这种方法可得出如图2所示的解．在此图中我们先走完一路径：艾克塞特→克雷顿→提文顿→卡林顿→艾克茅兹→艾克塞特，然后再走另一路径：艾克塞特→欧卡汉顿→艾克塞特．
175131_4ec0e4a3ddd6203.jpg
174750_4ec0e3c64a55403.jpg
此方法的总里程数为107英里(1英里=1.609千米)，但并不是最短行程．在现实生活中，我们可能会选择道路品质佳及路况良好的路径以节省时间，但在本题我们只要找出最短的路径即可．
175529_4ec0e5915444e03.jpg
你自己可能会发现如图3的解，此解的基本想法是将所有的城镇连成一个回路，所得出的答案为92英里．这个答案虽比前面的好得多了，但还不是最佳的解．最佳路径的里程只有91英里，你能找到吗？
假设现在李文黛又把汉尼顿列入她的行程之中(图4)，那么整个行程的最短路径为何(其出发点与终点仍为艾克塞特)？如果将出发点及终点皆改为卡林顿，会不会使整个行程变得较短呢？如果以不同的城镇为起点与终点，是否会影响总里程数呢？
175831_4ec0e647c553303.jpg
如果李文黛的起点及终点可以不同，那么她该选择哪两个城镇为起点及终点，以使整个行程为最短？
数学家们曾耗费许多心思以解决这类问题，但是到目前为止尚未成功．但他们知道在最短的路径中，各条路线彼此不可交错．然而当他们发现正确的解法时，若城镇的数目增加很多，又不适用了．他们甚至采用了先进的大型电脑作为辅助工具，利用系统的“试误法”．要找到“好”的解(可能并不是最好的)，方法很多，但如果有人能找到一个直接且快速的方法求得最佳路径，肯定会声名大噪！
英国每年都有成千上万的青少年会参加著名的“十岩探险”，整个探险路线包括要探访的所有著名的岩石地带(花岗岩通常露在山丘之顶)，如地图中所显示的地点(图5)．在正式探险之前
175952_4ec0e698df19703.jpg
几个月的周末，经常可以发现一些人在当地进行野外训练．某个周末，一支队伍先在地图上规划路线，他们打算由布雷克岩出发，然后经过图上标示的所有地方再回到出发点，他们希望尽可能找到最短的路径．
180345_4ec0e7816746003.jpg
解决此类问题的一个方法是先将地图描在纸上，并将纸固定在画板上．然后将钉子钉在每一个要探访的地方，再用不同长度、不同颜色的棉线来标出可能的路径，其中最短的线段当然就对应于最佳的路径(图6)．
你也可以利用地图来研究一下这类问题．
| 
发表于 2016-8-15 10:26:33