销售员的旅程问题

小学教育网

          
          

       
  12
                               
        　　有些时候，我们必须去很多地方办事，再回到原出发点，所以我们通常会先规划出最顺路(最短)的路径。此类问题被称为销售员的旅程问题，因为这是销售员的工作中最常碰到的问题。
       
        　　在许多场合都会碰到此类问题，比如说：油罐车驾驶员到各个加油站巡回加油；一位观光客想到剑桥、史特佛、爱丁堡、浦利茅斯等处旅游。
       
        　　化妆品销售员李文黛小姐欲去图中的每个小镇推销新产品。她打算由艾克塞特出发(见图1)。地图中的数字为两小镇间的距离，单位是km。如果出发点及终点皆为艾克塞特的话，则最短的行程数是多少？
       
        　　解此类问题最常用的方法为最近城市法。此方法是先前往最靠近起点艾克塞特的城镇——克雷顿，然后再去最靠近克雷顿且尚未到过的城镇，依此类推。这种方法产生图2中的解。在此图中我们首先走完一路径：艾克塞特→克雷顿→提文顿→卡林顿→艾克茅兹→艾克塞特；然后再走到另一路径：艾克塞特→欧卡汉顿→艾克塞特。
       
        　　此方法的总里程数是107km，但这并不是最短的行程。在现实生活中我们可能会选择道路品质佳以及路况良好的路线以节省时间。但是在本题中我们只求最短的路径即可，你能找出来吗？
       
        　　假设现在李文黛又把汉尼顿列入她的行程之中(见图3)，那么整个行程的最短路径为多少km(出发点及终点仍然为艾克塞特)？如果将出发点及终点皆改为卡林顿，会不会使整个行程变得较短呢？
       
        　　若以不同的小镇为起点及终点会影响到总里程数吗？
       
        　　如果李文黛的起点及终点可以不同，那么她该选择哪两个小镇为起点和终点，以使整个行程为最短？
       
        　　数学家们在这个问题的解法上曾耗费许多心思，但到目前为止尚未成功。现在可确定的是在最短的路径中，各个路径彼此不可相交。然而他们发现若城镇的数目增加很多时，此解法又不适用了。