本文介绍了旅行商没有回报,并与给定的起点和终点城市的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我要寻找以下问题的名称:旅行商问题(访问每个城市恰好一次),但没有返回到起点城市,并在最后参观一个给定的城市。换句话说,我想指定的起点和终点城市,我不想再回到起点城市。 谢谢!
I am looking for the name of the following problem: traveling salesman problem (visit each city exactly once) but without returning to the start city and with visiting a given city at the end. In other words, I would like to specify the start and end cities, and I don't want to go back to the start city. Thanks!!!
推荐答案我怀疑这有自己的名字,因为它是平凡的同构到正常的TSP。
I doubt this has its own name, as it's trivially isomorphic to the normal TSP.
- 从标准的TSP此:给定一个有向加权图的TSP,具有开始/结束节点,分裂的开始/结束节点到一个起始节点和一个结束节点,与所有的出边开始节点上和所有末端节点上的入边。
- 从这个标准TSP:拆下端节点的所有出边;从末端节点到开始节点添加单个边缘(即现在的开始/结束节点)。
更多推荐
旅行商没有回报,并与给定的起点和终点城市
发布评论