2. 自考
  3. A、B、C、D四城市间距离表如下 求从某一城市出发遍历各城市各一次的最短路径．

A、B、C、D四城市间距离表如下 求从某一城市出发遍历各城市各一次的最短路径．

admin2019-07-20  9
问题 A、B、C、D四城市间距离表如下   
  
求从某一城市出发遍历各城市各一次的最短路径．
选项
答案匈牙利算法思路 (1)距离矩阵的各行分别减去该行的最小数；各列也分别减去该列的最小数． (2)求最优路径： ①从第一行开始依次检查，找出只有一个0元素没有加标记的行．给这个0元素加标记“*”，与这个加标记的“0*”同列的0元素全划去，重复此过程，直到每一行没有未加标记的0元素或者至少有两个未加标记的0元素． ②从第一列开始依次检查各列，找出只有一个未加标记的0元素的列，将这个0元素加上标记“*”，并将与这个“0*”同行的0元素划去，重复此过程，直到每一列没有尚未加标记的0元素或者至少有两个未加标记的0元素． ③重复①，②两个步骤，直到表中没有未加标记的0元素为止． 用匈牙利算法求解 [*] D2中有四个“0*”，得路径A→C→D→B→A，最短路径总长为4+5+4+6=19·
解析
转载请注明原文地址:https://kaotiyun.com/show/tlVx777K
本试题收录于： 物流数学题库理工类分类
0

物流数学

理工类

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