首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
admin
2019-07-20
29
问题
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从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
物流数学
理工类
相关试题推荐
随时间推移,系统对干扰信号的响应不断扩大,控制系统一定是【】
系统传递函数G(s)=,则其幅频特性为【】
某一阶系统的传递函数G(s)=,则系统增益________,时间常数为________。
系统数学模型的建立可以采用哪些方法?
下面是某闭环系统的阶跃响应图,则根据此图可知该系统的特征方程的根【】
______是指对于网络中各种不安全因素,如攻击、窃取和篡改等行为,以及病毒、蠕虫、木马等恶意代码,及时准确地进行判断和识别,从而进行相应的防范、消除和修复。
传统的企业组织形式主要有直线制、______、直线一职能式、________、矩阵制等。
如果各并发进程对共享变量的访问是互斥的,那么就不会发生与_______有关的错误。
平均每6天有一艘货轮到达港口,装卸一艘货轮额平均时间为2天,求:货轮在等候装卸的平均时间Wq。
随机试题
A.血栓栓塞B.脂肪栓塞C.空气栓塞D.羊水栓塞E.肿瘤栓塞
《传染病防治法》规定,传染病暴发、流行时,当地政府应当
关于强直性脊柱炎.下列哪项是错误的
用于痧胀腹痛,吐泻,神昏用于闭证神昏,疮疡肿毒,胞衣不下
小儿营养不良是指体重低于正常均值的()
在病人常见的心理问题中,常表现为行为与年龄、社会角色不相符合,想回到婴儿时期,此病人的心理状态被称为()
在市场经济国家,公路、地铁、无线电视大都是由国家而不是由私人来投资的,其合理的经济学解释是,上述部门( )。
在社会工作的启动阶段,主要任务是()。
洋务学堂的创办类型中不包括()。
设A为3阶正交矩阵,它的第一行第一列位置的元素是1,又设β=(1,0,0)T,则方程组AX=β的解为_______.
最新回复
(
0
)