首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
admin
2019-07-20
42
问题
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
选项
答案
由边界条件可知:f
0
(2,[*])=d
12
=8,
0
(3,[*])=d
13
=5,f
0
(4,[*])=df
14
=6, 当k=1时,即从1城开始,中间经过一个城市到达i城的最短距离是: f
1
(2,{3})=f
0
(3,[*])+d
32
=5+9=14, f
1
(2,{4})=f
0
(4,[*])+d
42
=6+7=13, f
1
(3,{2})=8+8=16,f
1
(3,{4})=6+8=14, f
1
(4,{2})=8+5=16,f
1
(4,{3})=5+5=10, 当k=2时,即从1城开始,中间经过两个城市(它们的顺序随便)到达i城的最短距离是: f
2
(2,{3,4})=min[f
1
(3,{4})+d
32
,f
1
(4,{3})+d
42
]=min[14+9,10+7]=17, 所以p
2
(2,{3,4})=4, f
1
(3,{2,4})=min[13+8,13+8]=2l, 所以p
1
(3,{2,4})=2或4, f
2
(4,{2,3})=min[14+5,16+5]=19, 所以P
2
(4,{2,3})=2,故k=3时,即从1城开始,中间经过三个城市(顺序随便)回到1城的最短距离是: f
1
(1,{2,3,4})=min[f
2
(2,{3,4})+d
21
,f
2
(3,{2,4})+d
31
,f
2
(4,{2,3})+d
41
] =min[17+6,21+7,19+9]=23 所以p
3
(1,{2,3,4})=2. 由此可知,推销员的最短旅行路线是1—3—4—2—1,最短距离为23.
解析
转载请注明原文地址:https://kaotiyun.com/show/qvVx777K
本试题收录于:
物流数学题库理工类分类
0
物流数学
理工类
相关试题推荐
函数的返回值是通过函数体中的_______语句获得。
下面不属于软件设计原则的是【】
设系统的特征方程为s4+4s3+2s2+6s+2=0试用劳斯判据判断系统的稳定性。
RC电网络系统如图所示,画出此系统的框图,并求传递函数Uo(s)/Ui(s)。
NetWare网络操作系统大部分安装于服务器上,这部分称为_____,负责管理网络。
在SNMP报文数据部分中,【】用于指明一个或多个变量的名和对应的值。
假设网络中有n个用户,其中的任意两个人要进行加密通信,且加密密钥和解密密钥相同,则一共需要_______个密钥。
分析用户的业务处理后,以()形式表示数据的流向和对数据的加工。
P为任一概率矩阵,Q为一固定概率矩阵,则Pn()
随机试题
根据《巴黎公约》规定,外观设计的优先权的时间为()
军人叛逃罪
吗啡中毒后可有下述表现:
剧烈呕吐后出现呕血的情况提示()。
下列工期索赔的计算方法中,如果某干扰事件仅仅影响某单项工程、单位工程或分部分项工程的工期,要分析其对总工期的影响,可以采用()。
一般资料:求助者,男性,28岁,外企员工。案例介绍:求助者高大英俊,工作能力强,人际关系好,深受领导和同事的好评。求助者与女友是大学同学,大学毕业时确立恋爱关系,两人相恋5年,感情融洽,已谈及婚嫁,三个月前,求助者正准备为结婚购置婚房的时候,女友却突然提出
根据下表,完成126~130题。设2003年进出口总额最大的国家的进出口总额为A,2003年进出口总额最小的国家的进出口总额为B,则A约为B的()
86,41,27,18,13,6,5,()
动物的权利问题——1997年英译汉及详解Doanimalshaverights?Thisishowthequestionisusuallyput.Itsoundslikeauseful,ground-clearing
下面关于实时系统的论述中,正确的是()。
最新回复
(
0
)