加强旅行售货员问题
旅行售货员问题:一个售货员从城市１出发，要到城市２，３ ，…，ｎ 去推销产品 ， 最后回到城市１．问应该怎样走，才能使所走的路程最短？
原来的是只考虑城市之间路程时间，不考虑在城市推销时间，
若考虑推销产品时间，那这个问题又该如何解决？
将以上问题改为：
一个售货员从城市１出发，要到城市２，３ ，…，ｎ 去推销产品 ，在城市i的推销时间为ti，且不在同一个城市重复推销（即第二次经过某城市时，不需要再次计算推销时间），最后回到城市１．问应该怎样走，才能使所花费的时间最短？ 这个是弱化版……
可以直接规约成相同节点数的TSP
（而TSP不可以规约成相同节点数下的这个问题）
依旧是NPC问题（可以规约成哈密顿环）
你有兴趣可以自己玩
反正我是不会碰这玩意。 .·.·. 发表于 2020-12-5 12:29
这个是弱化版……
可以直接规约成相同节点数的TSP
（而TSP不可以规约成相同节点数下的这个问题）
怎么直接归约成相同节点数的TSP？可以详细讲讲吗？ 熬出头8l 发表于 2020-12-5 13:13
怎么直接归约成相同节点数的TSP？可以详细讲讲吗？
先把时间减掉，“且不在同一个城市重复推销”可以直接用来计算任意两个城市之间的最短距离
于是我们得到一个带距离的完全图，从这个图里面跑一次TSP，得到的答案加上你的那一堆t，就是你这个问题的答案
感觉挺显然的
（别是我想错了吧……） 抱歉，我没有讲得太清楚
TSP问题中：限制是每个城市只能拜访一次。
我将其改为：不在同一个城市重复推销（即第二次经过某城市时，不需要再次计算推销时间），即可以经过同一个城市两次。 熬出头8l 发表于 2020-12-5 21:25
抱歉，我没有讲得太清楚
TSP问题中：限制是每个城市只能拜访一次。
？？
我就是这个意思啊
新路线可以直接跟原路线一一对应。
你无非就是把原路线上任意两个城市增加了一条带长度(两城市之间最短路径)的路径。
把弱化问题里面第一次拜访城市的顺序排列一下，送回原问题（增加边之后的版本），你会发现弱化问题算得的总时间不小于原问题增加边之后的总时间
然而原问题（增加边之后）的每个解都是新问题的解
这就够了。
你说得很清楚。 .·.·. 发表于 2020-12-6 16:40
？？
我就是这个意思啊
新路线可以直接跟原路线一一对应。
举个简单例子，https://wx1.sinaimg.cn/mw1024/dfabac27gy1glej668i0qj21hc0u0mxd.jpg、
在新问题中，最短路径很容易看出。
然而，也很容易证明，原问题（增加边之后）的时间一定大于新问题所得的时间，（因为TSP中每个节点只能经过一次） 熬出头8l 发表于 2020-12-6 23:21
举个简单例子，、
在新问题中，最短路径很容易看出。
写出你找到的最短路径
找出第一次到达某个城市的顺序
把这个顺序送去增加边之后的TSP
你怎么得出这个序列满足“原问题（增加边之后）的时间一定大于新问题所得的时间”这一条件的？？ 我自己搞错了。。 。
我明白了，谢谢 两个城市之间的行走时间不计算进去吗？
页:
[1]