首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?
admin
2019-07-20
74
问题
求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从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)));在此函数调用语句中实参的个数是_______。
已知C语言函数fun()的定义形式为voidfun(charch,floatx){…)则正确调用函数fun()的语句是【】
若有定义语句intm[]={5,4,3,2,1},i=4;,则下面对数组m的数组元素的引用中错误的是【】
随时间推移,系统对干扰信号的响应不断扩大,控制系统一定是【】
利用奈奎斯特稳定性判据判断系统的稳定性时,z=p-N中的z表示意义为【】
相位滞后校正后可以提高稳态性能,但使系统带宽________,降低了时间响应速度。
DNS的域名服务器中,距离主机最近的是【】
用PV操作管理临界区时,把信号量的初值定义为1,现有n个进程在等待进入临界区,这时信号量的值为
某汽车运输公司有许多载重量为5吨的卡车,某天该公司接受了表7.5所示的9项运输业务。装卸点位置如图7.30所示的交通图(线上数字单位:km)。怎样安排卡车来完成这些运输业务才能够做到最节约?
随机试题
依据《金属非金属矿山禁止使用的设备及工艺目录》(第一批及第二批),金属非金属矿山可选用的设备或工艺为()。
火灾报警控制器能发出区别于环境声、光的火灾报警信号,警示人们迅速进行安全疏散和采取火灾扑救措施。()
促进振动病发生的重要外界条件是
红细胞内叶酸含量测定低于
任何金融工具都可能出现由资产价格或指数变动导致损失的可能性,这是()。
研究表明:如果人长期在95分贝的噪声环境里工作和生活,大约有29%的人会丧失听力;即使噪声只有85分贝,也有10%的人会发生耳聋;120~130分贝的噪声,能使人感到耳内疼痛;更强的噪声会使听觉器官受到损害。有检测表明:当人连续听摩托车声,8小时以后听力就
Alawyerneedsa(n)______secretary.
已知函数f(x)=x2ln(1-x),当n≥3时,f(n)(0)=().
学生的记录由学号和成绩组成,N名学生的数据已在主函数中放入结构体数组s中,请编写函数fun,它的功能是:把分数最低的学生数据放在b所指的数组中,注意:分数最低的学生可能不止一个,函数返回分数最低的学生的人数。注意:部分源程序在文件PROG1.C文
It’scommonsensethat____________________.(商务信函应以正式文体书写而不是以么人风格书写).
最新回复
(
0
)