首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
77
问题
设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://www.kaotiyun.com/show/LSVx777K
本试题收录于：
物流数学题库理工类分类
0
物流数学
理工类
相关试题推荐
下面不属于软件设计原则的是【】
在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后向前依次后移【】个元素。
系统的可变输出如果能按照要求由参考输入或控制输入进行调节的，则称为________。
HTTP规定的用户使用浏览器访问万维网的过程可以分为哪几个步骤?
______是由IBM公司所开发的网络管理综合平台，能够为用户提供强大的网络管理功能。
在人事管理信息系统的输入设计中，为了保证年龄数据的正确性，规定输入的年龄应在30～50之间，如果输入的数据超出此范围，则认为是错误的，这种数据校验方式属于()
分析题26图所示的时序逻辑电路。要求：(1)写出各触发器的驱动方程和状态方程；(2)画出状态转换图；(3)检查电路能否自启动。
一般说来，如果增大自然频率ωn的数值，则动态性能指标中的调整时间Ts【】
进度计划检查对比的方法主要有()
在施工进度检查过程中，对不符合要求的部分进行调整，下列方法不正确的是()
随机试题
男性，26岁。排柏油便2天，加重伴头晕、心慌半天急诊入院。既往无肝病史，近期无服药史。查体：BP70／40mmHg，心率120次／分，腹平软，无压痛，肝、脾肋下未触及，四肢末梢发凉。(2014年第100题)首选的处理是
当某一感官处于功能状态时，另一感官出现幻觉，此现象是
在评价未更正错报的影响时，下列说法中A注册会计师认为正确的有()。
某企业生产某种产品，品种单一，批量和生产相对稳定。利用抽样检验对产品进行验收。若根据检索要素确定的抽样方案抽取的样本中，发现不合格品数d大于接收数Re，则()。
下列关于乡村聚落和城市聚落的对比，错误的是()。
坚持社会主义初级阶段的基本经济制度，必须旗帜鲜明地反对()。
下列各项可使用通报来处理的是（）。
课程设计
以下叙述中正确的是
Withoursocietyprogressingsmoothlytowardthetwenty-lustcentury,itseemsthatthestablestructureoffamilyisalsochang
最新回复
(
0
)
