首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
74
问题
设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
物流数学
理工类
相关试题推荐
下面程序段的时间复杂度是_________。i=s=0；while(s
编写一个算法，将一个顺序栈中的元素依次取出，并打印元素值。
已知长度为n的线性表A采用顺序存储结构，并且数据元素按值的大小非递减排列，写一算法，删除该线性表中值相同的多余元素(该算法完成后，线性表中数据元素严格按值递增排列)。
图3所示反馈控制系统中，求输入单位阶跃信号时系统的稳态误差。
RC电网络系统如图所示，画出此系统的框图，并求传递函数Uo(s)／Ui(s)。
【】比较适用于单工数据通信系统或者对实时性要求比较高的数据通信系统(如多媒体实时通信系统)等。
_____是TCP／IP网络中应用最为广泛的网络管理协议，最初是Internet工程任务组IETF为解决Internet上的路由器管理而提出的方案。
数据库设计步骤如下图所示，试填写其中的步骤，使设计过程完整。
关系数据库的数据与更新必须遵循三类完整性规则，下列不是其中一项的是()
数据库系统生存期中，下面不是需求分析阶段工作的是()
随机试题
青霉素的抗菌谱包括
冰雪道路对安全行车的主要影响是________。
东亚市场的文化共性包括()
患者，男，60岁。高血压病史20年，反复劳累时心前区压榨性疼痛1年，休息一段时间或舌下含服硝酸甘油数分钟后即可缓解，近5个月以来无发作。辅助检查：血TC5．0mmol／L，LDL-C2．9mmol／L，TG6．1mmol／L，HDL-C0．9
下列关于土石坝的稳定计算工况的说法错误的是()。
建设项目管理与企业管理同属于管理活动的范畴，但从建设项目管理的内涵可以看出，两者有着明显的区别，包括()。
道德与法律的联系不包括()。
秦王朝是中国历史第一个大一统的封建王朝。()
下列属于法律关系的是哪一项?()
西安事变的过程、结果、意义
最新回复
(
0
)
