2. 自考
  3. 求解四个城市旅行推销员问题，其距离矩阵如下表所示，当推销员从1城出发，经过每个城市仅一次，最后回到1城，问按怎样的路线走可使总行程最短?

求解四个城市旅行推销员问题，其距离矩阵如下表所示，当推销员从1城出发，经过每个城市仅一次，最后回到1城，问按怎样的路线走可使总行程最短?

admin2019-07-20  79
问题 求解四个城市旅行推销员问题，其距离矩阵如下表所示，当推销员从1城出发，经过每个城市仅一次，最后回到1城，问按怎样的路线走可使总行程最短?
选项
答案由边界条件可知：f0(2，[*])=d12=8，0(3，[*])=d13=5，f0(4，[*])=df14=6， 当k=1时，即从1城开始，中间经过一个城市到达i城的最短距离是： f1(2，{3})=f0(3，[*])+d32=5+9=14， f1(2，{4})=f0(4，[*])+d42=6+7=13， f1(3，{2})=8+8=16，f1(3，{4})=6+8=14， f1(4，{2})=8+5=16，f1(4，{3})=5+5=10， 当k=2时，即从1城开始，中间经过两个城市(它们的顺序随便)到达i城的最短距离是： f2(2，{3，4})=min[f1(3，{4})+d32，f1(4，{3})+d42]=min[14+9，10+7]=17， 所以p2(2，{3，4})=4， f1(3，{2，4})=min[13+8，13+8]=2l， 所以p1(3，{2，4})=2或4， f2(4，{2，3})=min[14+5，16+5]=19， 所以P2(4，{2，3})=2，故k=3时，即从1城开始，中间经过三个城市(顺序随便)回到1城的最短距离是： f1(1，{2，3，4})=min[f2(2，{3，4})+d21，f2(3，{2，4})+d31，f2(4，{2，3})+d41] =min[17+6，21+7，19+9]=23 所以p3(1，{2，3，4})=2． 由此可知，推销员的最短旅行路线是1—3—4—2—1，最短距离为23．
解析
转载请注明原文地址:https://kaotiyun.com/show/qvVx777K
本试题收录于： 物流数学题库理工类分类
0

物流数学

理工类

相关试题推荐
随机试题
最新回复(0)