首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1,u2u3,u4,u5各点之间的距离表如下: 求由某一点出发,遍历每个点各一次,最后又返回出发点的最短路径。
设u1,u2u3,u4,u5各点之间的距离表如下: 求由某一点出发,遍历每个点各一次,最后又返回出发点的最短路径。
admin
2015-01-12
61
问题
设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
物流数学
理工类
相关试题推荐
已知intb=4;,执行语句b+=b++;后,b的值是【】
已知C语言程序段如下:structsa{intnum;charname[10];floatf;}stu[3]={{5,"liming",85.0},{6,"liuliang",91.5},(7,"wa
C语言的基本数据类型是指【】
已知长度为n的线性表A采用顺序存储结构,并且数据元素按值的大小非递减排列,写一算法,删除该线性表中值相同的多余元素(该算法完成后,线性表中数据元素严格按值递增排列)。
最小相位系统对数幅频渐近特性如图所示,请确定系统的传递函数。
如图所示二阶系统框图,在单位阶跃输入信号作用下,当系统的阻尼比ζ满足什么条件时,二阶系统特征方程的根为两个不相等的负实根?
一般对机械工程控制系统有三方面的性能要求:稳定性、准确性和________。
下面关于系统稳态误差的说法中,正确的是【】
时分多路复用可分为同步时分多路复用和异步时分多路复用,若时隙与用户(或各路信号)之间没有固定的对应关系,必须在用户数据中加上用户的标识,以标记是哪个用户的数据,则称为______。
_____是指在商务活动中,将线下的商机与Internet相结合,让Internet成为线下交易的平台。商家同时开设网上商城和线下实体店,线上主要提供宣传推广、在线互动、在线购买和支付功能,在线下为用户提供具体的服务。
随机试题
设S1表示上半球面x2+y2+z2=R2,z≥0的上侧,设S2表示下半球面x2+y2+z2=R2,z≤0的下侧.若曲面积分I1=zdxdy,I2=zdxdy,则必有()
Hewasfound______onemonthafterhewasborn.
电讯检疫:国际航行船舶的电讯检疫一般是由船舶公司或船舶代理申请,同时符合下列条件:()
国外理财业务的形成与发展时期是()。
下列各项中,导致成本法核算的长期股权投资的账面价值发生增减变动的有()。
A公司(上市公司)是坐落于黑龙江省的国内大型现代化农业企业,公司采用现代农业生产方式,从事特色农产品种植、加工、保鲜、冷藏及销售。公司主要产品为:鲜食粘玉米、玉米果汁、玉米粒、青贮饲料、果肉型葡萄、葡萄酒。A公司资产总额近15亿元人民币,其中存货占公司资产
在选择性旅游中,不可选择部分包括()。
行政复议:指公民、法人或其他组织对行政机关的具体行政行为不服,依法向作出具体行政行为的行政机关的上级机关或法律规定的行政机关提出申诉,由其决定是否合法、适当,重新审议并作出裁决的行政程序制度。根据定义,下列情形属于行政复议的是()。
下面叙述正确的是()。
______hehaslimitedtechnicalknowledge,theoldworkerhasalotofexperience.
最新回复
(
0
)