首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
46
问题
设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
物流数学
理工类
相关试题推荐
只有先定义一个_______型变量，才能将另外一个变量的地址存放到该变量中。
系统增益调整中，若减小开环增益，可使系统的稳定性________(填“提高"或“降低”)。
为进行网络中的数据通信而制定的规则、标准和约定称为________。
【】比较适用于单工数据通信系统或者对实时性要求比较高的数据通信系统(如多媒体实时通信系统)等。
_____是TCP／IP网络中应用最为广泛的网络管理协议，最初是Internet工程任务组IETF为解决Internet上的路由器管理而提出的方案。
______是所有网络服务提供商ISP都要用到的重要功能模块，通过网络管理系统对用户使用网络资源的情况进行记录并核算费用。
下面几种不是数据库应用系统开发王具的是()
全面质量管理可以分为四个阶段，即计划、执行、检查和_______。
如图，求V1到V8的最短路线。
某论坛发帖子系统有如下几个需求。(1)记录帖子内容：系统对访客的输入内容进行检查，无非法内容，则将内容存入发帖内容文件中，否则提示内容非法。(2)显示帖子内容：从发帖内容文件中读出帖子内容，按一定格式显示在屏幕上。请根据要求：①画出该子系统的数据流图
随机试题
详述公文管理信息系统实现的方式中，单机方式与网络方式有何区别。
影响行为的因素主要包括（）
转录起始于DNA模板上的特定部位，该部位称为转录起始位点，能够被RNA聚合酶识别，从而调控转录的过程的一段特殊序列称为启动子，下列关于启动子的说法不正确的是
男，24岁，吸烟，近1年来右下肢行走后疼痛，休息后好转，出现间歇性跛行。近1个月来．，右脚趾变黑、皱缩、失去知觉，此种病变是
学校组织一次食品安全调查活动。由你来负责。你怎么组织?
下列行为中，应以非国家工作人员受贿罪定罪处罚的是()(2014年一专一第14题)
MFNS
形而上学否定观主张，否定是
已知函数f(x，y，z)＝x3y2z及方程x＋y＋z—3＋e—3＝e—(x＋y＋z)，(*)(I)如果x＝x(y，z)是由方程(*)确定的隐函数满足x(1，1)＝1，又u＝fx(y，z)，y，z)，求(Ⅱ)如果z＝z(x，y)是由方程(*)确定的隐函
Whohasgotapencil?
最新回复
(
0
)
