首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
80
问题
设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
物流数学
理工类
相关试题推荐
在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后向前依次后移【】个元素。
已知单位负反馈系统的开环传递函数为G(s)=，则其在单位阶跃输入下的稳态误差为________。
当输入与输出已知而系统尚未构建时，要求设计系统使系统在该输入条件下尽可能符合给定的最佳要求，此类问题即________。
已知系统开环频率特性的奈奎斯特图如图所示，则该系统的型次为【】
已知最小相位系统的对数幅频特性图如图所示，则系统包含【】个积分环节。
已知开环稳定的系统，其开环频率特性的奈奎斯特图如图所示，则该闭环系统________。
______是指网络中的数据终端可以与其他设备根据需要任意相连，两个网络结点之间可以直接通信，也可以通过其他结点进行转接。
下列软件中，不是基于P2P模式的是【】
数据库系统生存期中，下面不是需求分析阶段工作的是()
检查文件是否已关闭，若否，则请先调用“关闭”操作是以下哪一项操作的工作
随机试题
同时具有光学性能良好、保温隔热降低能耗、防结露、良好的隔声性能等功能的是()。
诱导和控制芽休眠的最重要的因素是（）。
Unix系统为用户建立了三个文件：标准输入文件、标准输出文件和（ ）。
∫sin2xcosxdx=_______．
女性，70岁。高血压20余年，冠心病史10余年，乙肝病史30年。半个月前着凉后出现胸闷，气短，偶有咳嗽，白痰，夜间明显，双下肢逐渐水肿，尿少，1周来偶有夜间憋醒，气短加重来诊。查体：BP170／80mmHg，P96bpm，唇微绀，颈静脉怒张，双肺底可闻
下面哪种情况是做烤瓷修复体的禁忌
既能凉血止血，又能散瘀消痈的药物是
学习动机程度与学习效率成正比，学习动机越强，效率越高。()
在我国，基层人民政府可以依法设立的派出机关是()。
A、Lateinthemorning.B、Earlyintheafternoon.C、Sometimebeforedawn.D、Shortlyaftersunrise.C推理判断题。男士在报道中提到反动武装有可能在破晓前占据首都
最新回复
(
0
)
