首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
54
问题
设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
物流数学
理工类
相关试题推荐
下列算法的时间复杂度是【】for(inti=1；i
通过实验求得某最小相位系统对数幅频特性如图3所示，试估算其传递函数。
如图所示二阶系统框图，在单位阶跃输入信号作用下，当系统的阻尼比ζ满足什么条件时，二阶系统特征方程的根为两个不相等的负实根?
机械工程控制论的研究对象和任务是什么?
为进行网络中的数据通信而制定的规则、标准和约定称为________。
_______是指计算机网络是否具有抵御和防范各种风险和威胁的能力。
【】比较适用于单工数据通信系统或者对实时性要求比较高的数据通信系统(如多媒体实时通信系统)等。
下列软件中，不是基于P2P模式的是【】
IEEE802委员会为局域网制定了一系列标准，其中，【】是无线局域网介质访问控制方法及物理层技术规范。
某论坛发帖子系统有如下几个需求。(1)记录帖子内容：系统对访客的输入内容进行检查，无非法内容，则将内容存入发帖内容文件中，否则提示内容非法。(2)显示帖子内容：从发帖内容文件中读出帖子内容，按一定格式显示在屏幕上。请根据要求：①画出该子系统的数据流图
随机试题
对于肩手综合征的治疗不正确的是
治疗瘀血病证时常配以补气行血药物的理论依据是治疗血虚时常配以补气药物的理论依据是
基金托管人对基金管理人的估值结果即基金资产净值的复核，不包括对()的核对。[2014年6月证券真题]
下列各项中，不适合项目融资的是()。
自助游，是指自己设计路线，自己安排旅途中的一切，利用现代文明带来的便捷，却又不受束缚的旅行。根据上述定义，下列属于自助游的是：
试论新闻舆论的导向功能。(中国传媒大学，2011年)
ADSL下行数字信道速度可达()，上行数字信道可传送144Kbps或384Kbps中速数据。
李东阳是某高校的教授，最近，他撰写了一篇有关质量管理的论文，但受其自身计算机技术水平的限制，他需要找人帮忙完成编辑排版工作。请按照如下要求帮助李教授对论文进行编辑徘版：为文档添加文字水印“质量是企业的生命”，格式为宋体、字号80、斜式、黄色、半透明。
Comparisonsweredrawnbetweenthedevelopmentoftelevisioninthe20thcenturyandthediffusionofprintinginthe15thand1
A.smileB.teachC.busyD.waterE.friendlyF.shoutG.movegivelessonstosb.
最新回复
(
0
)
