首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
28
问题
设u
1
，u
2
u
3
，u
4
，u
5
各点之间的距离表如下：
求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
选项
答案
(1)距离矩阵的各行分别减去该行的最小数，各列也分别减去该列的最小数得：[*] (2)求最优路径： (i)从第一行开始依次检查，找出只有一个0元素没有加标记的行，给这个0元素加标记“*”，与这个加标记“0”同列的0元素全划去。重复此过程，直到每一行没有未加标记的0元素或至少有两个未加标记的0。(ii)从第一列开始依次检查各列，找出只有一个未加标记的0元素的列，将这个0元素加上标记“*”，并将与这个“0”同行的0元素全划去。重复此过程，直到每一列没有尚未加标记的0或者至少有两个未加标记的0元素。(iii)重复(i)，(ii)，直到矩阵中没有未加标记的0元素为止。[*] 由上面的矩阵可以看出：v
1
→v
2
v
2
→v
4
，v
4
→v
1
，v
3
→v
5
，v
5
→v
3
总距离为：2+4+2+2+5=15 (3)打开节点个数少的环路，令d
35
=∞或d
53
=∞，调整过程如下：(i)令d
35
=∞，[*] 可得：v
1
→v
2
→v
5
→v
3
→v
4
→v
1
无环路，于是总距离为：2+5+3+2+5=17(ii)令d
53
=∞，得[*] 得路径v
1
→v
2
→v
1
，v
3
→v
5
→v
4
→v
3
总路径为：2+3+2+5+6=18若再打开节点最少得环路求解，其点距离必大于或等于18，故无需再计算了。所以最优路径为：v
1
→v
2
→v
5
→v
3
→v
4
→v
1
总距离为17。
解析
转载请注明原文地址:https://kaotiyun.com/show/LSVx777K
本试题收录于：
物流数学题库理工类分类
0
物流数学
理工类
相关试题推荐
运行下列程序后的输出结果是【】#includcinta=3，b=4；voidfun(intx1，intx2){printf("％d，％d＼n"，x1+x2，b)；}main(){inta
按照C语言规定的用户标识符命令规则，不能出现在变量名中的是【】
下面不属于软件设计原则的是【】
已知系统开环频率特性的奈奎斯特图如图所示，则该系统的型次为【】
系统如图所示，G(s)=，其中a=0．4，b=0．5，试求：(1)系统的开环零点及开环极点；(2)系统的闭环零点及闭环极点；(3)系统的阻尼比ζ和无阻尼自然频率ωn。
IP地址具有固定规范的格式，一个IPv4也址的二进制位数为【】
______是指网络中的数据终端可以与其他设备根据需要任意相连，两个网络结点之间可以直接通信，也可以通过其他结点进行转接。
______是指对于网络中两个相邻结点之间传输的数据进行加密保护。
下列关于进度计划检查的S型曲线比较法说法不正确的是()
甲、乙两军进行军事演习，甲军司令员想对乙军发动一次突然袭击，为了成功地进行这次袭击，他要求确保有足够数量的部队能调运到前沿阵地，他的参谋人员已经绘制了从甲军驻地到前沿阵地之间可通行路线的下列图解，下图中标出了每条路线按每小时可调运人数计算的通行能力。司令员
随机试题
关于水痘的叙述不正确的是()
A．补气B．养阴C．两者均可D．两者均不可西洋参功能()
以下哪个不正确
急性肾衰无尿或少尿期早期，发生水中毒的常见原因是
基础工程划分4个施工过程(挖基槽、做垫层、浇混凝土、回填土)。分3个施工段组织等节奏流水施工，流水节拍为5天。浇混凝土2天后才能进行回填土。该工程的流水施工工期为()天。
某商店商品销售额增长5%，平均销售价格增长2%，则商品销售量()。
白雾村曾是西汉时期西南夷道上的重要驿站，又是明清时期的万里京运第一站，但眼前的白雾村显得有些____________。狭长的白雾街还保留着当年的格局，两侧矗立着20多座明清风格古建筑，但歪歪扭扭的门梁、________的屋顶、面临倾覆的古会馆，令人对这个曾
Itisallverywelltoblametrafficjams,thecostofpetrolandthequickpaceofmodernlife,butmannersontheroadsarebe
Thedot-comcollapsemayhavebeenadisasterforWallStreet,buthereinSiliconValley,itwasablessing.Itwasthewelcome
Boilerroomsareoftendirtyandsteamy,butthisoneispristine(干净的)andcool.FoxPointisaspankingnew47-unit【C1】_______
最新回复
(
0
)
