首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
45
问题
设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的线性表A采用顺序存储结构，并且数据元素按值的大小非递减排列，写一算法，删除该线性表中值相同的多余元素(该算法完成后，线性表中数据元素严格按值递增排列)。
机械工程系统在外加作用激励下，其输出量随时间变化的函数关系称之为系统的________。
某仓库大门自动控制系统的原理如图所示，试说明自动控制大门开启和关闭的工作原理，并画出系统框图。
已知单位反馈系统的开环传递函数为G(s)=，试求参数K的取值范围以满足下面的指标：当输入r(t)=t时，系统的稳态误差ess≤0．02。
系统增益调整中，若减小开环增益，可使系统的稳定性________(填“提高"或“降低”)。
面向连接服务包括建立连接、传输数据和________三个阶段。
_____不仅可以检测出误码，还可以确定差错位置，并直接加以纠正。
IP地址中规定的全0是保留地址，表示______。
TCP／IP中规定了两种不同的传输层协议，其中无连接的用户数据报协议的简称是【】
对某公司进行调查分析，确定是否值得开发一个新系统的工作是属于()
随机试题
下列关于履带式装载机的说法中，错误的是()。
韩某和苏某共同殴打他人，致被害人李某死亡、吴某轻伤，韩某还抢走吴某的手机。后韩某被抓获，苏某在逃。关于本案的附带民事诉讼，下列哪一选项是正确的?()
甲状腺髓样癌是一种()(2001年)
A．辛味药B．酸味药C．甘味药D．苦味药E．咸味药有发汗、解热作用的药物多属于
对于水难溶性药物或注射后要求延长药效作用的药物，可制成()注射剂
继发性腹膜炎的细菌感染多是
“进口口岸”栏：()。“保费”栏：()。
根据以下资料，回答下列问题。2012年，Z省W市实现文化及相关产业增加值比上年增长9．6％。在文化产品制造业中，文化印刷、文化用品制造和工艺美术品制造三大主导行业，2012年分别实现增加值21．82亿元、11．57亿元和6．62亿元。201
党的十六大首次明确将“建设社会主义()”的思想写入党章。
The______ofthescientificattitudeisthatthehumanmindcansucceedinunderstandingtheuniverse.
最新回复
(
0
)
