旅行商没有回报，并与给定的起点和终点城市 [英] traveling salesman without return and with given start and end cities

问题描述

我要寻找以下问题的名称：旅行商问题（访问每个城市恰好一次），但没有返回到起点城市，并在最后参观一个给定的城市。换句话说，我想指定的起点和终点城市，我不想再回到起点城市。 谢谢！

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：拆下端节点的所有出边;从末端节点到开始节点添加单个边缘（即现在的开始/结束节点）。

这篇关于旅行商没有回报，并与给定的起点和终点城市的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！