找回密码
 欢迎注册
查看: 19124|回复: 9

[讨论] 加强旅行售货员问题

[复制链接]
发表于 2020-12-5 11:29:41 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
旅行售货员问题:

一个售货员从城市1出发,要到城市2,3 ,…,n 去推销产品 , 最后回到城市1.问应该怎样走,才能使所走的路程最短?

原来的是只考虑城市之间路程时间,不考虑在城市推销时间,
若考虑推销产品时间,那这个问题又该如何解决?

将以上问题改为:
一个售货员从城市1出发,要到城市2,3 ,…,n 去推销产品 ,在城市i的推销时间为ti,且不在同一个城市重复推销(即第二次经过某城市时,不需要再次计算推销时间),最后回到城市1.问应该怎样走,才能使所花费的时间最短?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-5 12:29:55 | 显示全部楼层
这个是弱化版……
可以直接规约成相同节点数的TSP
(而TSP不可以规约成相同节点数下的这个问题)
依旧是NPC问题(可以规约成哈密顿环)

你有兴趣可以自己玩
反正我是不会碰这玩意。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-5 13:13:15 | 显示全部楼层
.·.·. 发表于 2020-12-5 12:29
这个是弱化版……
可以直接规约成相同节点数的TSP
(而TSP不可以规约成相同节点数下的这个问题)

怎么直接归约成相同节点数的TSP?可以详细讲讲吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-5 13:32:03 | 显示全部楼层
熬出头8l 发表于 2020-12-5 13:13
怎么直接归约成相同节点数的TSP?可以详细讲讲吗?

先把时间减掉,“且不在同一个城市重复推销”可以直接用来计算任意两个城市之间的最短距离
于是我们得到一个带距离的完全图,从这个图里面跑一次TSP,得到的答案加上你的那一堆t,就是你这个问题的答案

感觉挺显然的
(别是我想错了吧……)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-5 21:25:32 | 显示全部楼层
抱歉,我没有讲得太清楚

TSP问题中:限制是每个城市只能拜访一次。

我将其改为:不在同一个城市重复推销(即第二次经过某城市时,不需要再次计算推销时间),即可以经过同一个城市两次。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-6 16:40:17 | 显示全部楼层
熬出头8l 发表于 2020-12-5 21:25
抱歉,我没有讲得太清楚

TSP问题中:限制是每个城市只能拜访一次。

??
我就是这个意思啊
新路线可以直接跟原路线一一对应。

你无非就是把原路线上任意两个城市增加了一条带长度(两城市之间最短路径)的路径。
把弱化问题里面第一次拜访城市的顺序排列一下,送回原问题(增加边之后的版本),你会发现弱化问题算得的总时间不小于原问题增加边之后的总时间

然而原问题(增加边之后)的每个解都是新问题的解

这就够了。

你说得很清楚。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-6 23:21:03 | 显示全部楼层
.·.·. 发表于 2020-12-6 16:40
??
我就是这个意思啊
新路线可以直接跟原路线一一对应。

举个简单例子,

在新问题中,最短路径很容易看出。
然而,也很容易证明,原问题(增加边之后)的时间一定大于新问题所得的时间,(因为TSP中每个节点只能经过一次)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-7 00:05:40 | 显示全部楼层
熬出头8l 发表于 2020-12-6 23:21
举个简单例子,、

在新问题中,最短路径很容易看出。

写出你找到的最短路径
找出第一次到达某个城市的顺序

把这个顺序送去增加边之后的TSP
你怎么得出这个序列满足“原问题(增加边之后)的时间一定大于新问题所得的时间”这一条件的??
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-7 07:53:53 | 显示全部楼层
我自己搞错了。。 。

我明白了,谢谢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-7 09:51:17 | 显示全部楼层
两个城市之间的行走时间不计算进去吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 22:44 , Processed in 0.067326 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表