首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
admin
2019-07-20
36
问题
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从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
物流数学
理工类
相关试题推荐
若有以下函数调用语句:func(a+b,(x,y),fun(n+k,d,(a,b)));在此函数调用语句中实参的个数是_______。
有一位置伺服系统,其框图如下图(a)所示。当系统输入单位阶跃函数时,要求Mp≤5%,试(1)校核该系统的各参数是否满足要求;(2)在原系统中增加一微分负反馈如下图(b)所示,求满足要求时的微分反馈时间常数τ。
某仓库大门自动控制系统的原理如图所示,试说明自动控制大门开启和关闭的工作原理,并画出系统框图。
单位阶跃响应与稳态值之差进入________范围所需的时间称为调整时间。
可以覆盖相距不远的几栋办公楼,也可以覆盖一个城市的网络是【】
______是指多个作业(进程)分享一台主机CPU的时间,即处理机的运行时间被分成很多的时间片,按时间片把处理机轮流分配给各联机作业使用。
如何判断两个关系代数表达式是等价的?
网络计划的优化包括工期优化、费用优化和02。
下列矩阵中,不是固定概率矩阵的是()
随机试题
依恋
某患者,右下第一磨牙缺失,双端固定桥修复。固定桥试戴时,用力戴入后,邻牙出现胀痛,最可能的原因是
正常妊娠于12周时,子宫底于
35周早产儿已住院2天,护士在对其晨间护理时室内温度应保持在
《中华人民共和国招标投标法》第3条规定,下列( )项目必须进行招标。
工资汇总表、耗用材料汇总表是汇总凭证,既可以提供经营管理所需的某项总量指标,又可以简化核算手续。()
计提基金管理费时,基金风险程度越,基金管理费率越低。()
【资料】某外籍人士杰瑞在境内一家外国企业中工作,2011年10月收入情况如下:(1)工资收入为20000元;(2)向某家公司转让专有技术一项,获得特许权使用费6000元;(3)利用业余时间为某家企业进行产品设计,取得报酬24000元;
周期波动规律是市场经济运行条件下的()经济规律。
Helloandwelcometothisweek’seditionofTellMeMore—theprogramwhereyouaskthequestionsandweprovidetheanswers.A
最新回复
(
0
)