销售员的旅程问题

有时，我们不得不去很多地方做生意，然后回到原来的起点，所以我们通常先计划最短的路线。这些问题被称为销售人员的旅行问题，因为它们是销售人员工作中遇到的最常见的问题。

这种问题在很多场合都会遇到，例如:油罐车司机去各种加油站加油；一名游客想去剑桥、斯特拉特福德、爱丁堡、普利茅斯和其他地方旅游。

化妆品推销员李小姐想去图中的每个小镇推销新产品。她计划离开埃克塞特(见图1)。地图上的数字是两个小城镇之间的距离，单位是公里。如果起点和终点都是埃克塞特，最短的旅行次数是多少？

解决这些问题最常用的方法是最近城市法。这个方法是去克雷顿，离起点埃克塞特最近的城镇，然后去离克雷顿最近但还没去过的城镇，等等。该方法产生图2中的解决方案。在这张照片中，我们首先完成了一条路线:埃克塞特→克雷顿→蒂温顿→卡林顿→埃克塞特→埃克塞特；然后我们去了另一条路线:埃克塞特，奥卡汉顿，埃克塞特。

这种方法的总里程是107公里，但这不是最短的路程。在现实生活中，我们可能会选择道路质量好、路况好的路线来节省时间。但是在这个主题中，我们只需要最短的路径。你能找到它吗？

假设李·现在将汉尼拔包括在她的行程中(见图3)，那么整个行程中最短的路线是什么(起点和终点仍在前面)？如果起点和终点都改为卡灵顿，整个旅程会变得更短吗？

不同城镇的起点和终点会影响总里程吗？

如果李的起点和终点可以不同，她应该选择哪两个城镇作为起点和终点，使整个行程最短？

数学家们花了很多时间来解决这个问题，但是到目前为止他们还没有成功。现在可以肯定的是，在最短的路径中，每条路径不能相互交叉。然而，他们发现，如果城镇的数量增加很多，解决方案就不适用。