首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
31
问题
设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://jikaoti.com/ti/JCLaFFFM
本试题收录于：
物流数学题库理工类分类
0
物流数学
理工类
相关试题推荐
下列数据中，不合法的C语言实型数据是【】
设如图所示系统的固有开环传递函数为G1(s)=，其中T1=0．33s，T2=0．036s，K1=3．2，采用PI控制器(Kc=1．3，Tc=0．33s)，对系统进行串联校正，试比较系统校正前后的性能。
IP地址中规定的全0是保留地址，表示______。
______是由一些局域网网段构成的与物理位置无关的逻辑组，而这些网段具有某些共同的需求。
对某公司进行调查分析，确定是否值得开发一个新系统的工作是进行()
在对象联系图中，表示两个属性之间值的联系为逆联系的是()
在施工进度检查过程中，对不符合要求的部分进行调整，下列方法不正确的是()
设有某个运输问题的第二个运输方案如下表，试问此方案是否已是运输费用最低的方案?若不是，进行一次调整，建立第三个运输方案。
某汽车制造厂年产汽车12000辆，故年需用发动机12000台套。经过计算和修匀调整，应每月订货和进货发动机1000台套。设每台发动机的进厂价为20000元，试计算发动机的平均库存量和平均存货额。
随机试题
面神经受损
下列各项中符合风湿性二尖瓣关闭不全的体征有
以确保债权的履行为目的的限制物权，指的是()。
银行风险监管指标设计以资本盈利为核心，以法人机构为主体，兼顾分支机构，并形成分类、分级的监测体系。()
某农场通过大规模的并购话动，兼并多家同类型农场，农产品的种植规模和产量得到大幅度提高。高质量的产品和低廉的价格为该农场赢得了市场的肯定，成为国内多家知名食品生产企业的原料供应商。在充分分析行业竞争结构的基础上，该农场决定将业务范围扩大到农产品的深加工领域，
列宁称哪部书为一部“非常及时”的书?()
旅游团在用餐前()提出换餐要求，地陪要尽量与餐厅联系，按有关规定办理。
中国近代史是一部各种政治力量相互博弈的历史。下列历史事件出现的先后顺序依次是()。①武昌起义②护国战争③第一次护法运动④张勋复辟
教师分配学生座位时，最值得关注的是座位对人际关系的影响。()
Youshouldspendabout20minutesonQuestions1-13whicharebasedonReadingPassage1below.GoingNowhereFastTHISisludic
最新回复
(
0
)
