旅行推销员，不返回，有给定的开始和结束城市

Question

我正在寻找以下问题的名称:旅行推销员问题(准确地访问每个城市一次)，但没有返回开始的城市和访问的城市在最后。换句话说，我想指定起始城市和结束城市，我不想回到起始城市。谢谢！

Answer 1

我怀疑这有它自己的名字，因为它与正常的TSP几乎是同构的。

• 从标准TSP到此:给定TSP的有向加权图，并有一个开始/结束节点，将开始/结束节点划分为一个开始节点和一个结束节点，其中开始节点上的所有传出边缘和结束节点上的所有传入边缘。
• 从这到标准的TSP:从结束节点中删除所有传出边缘；从结束节点添加一个单一边缘到开始节点(现在是开始/结束节点)。