traveling salesman without return and with given s

问题:

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!!!

回答1:

I doubt this has its own name, as it's trivially isomorphic to the normal TSP.

• From standard TSP to this: Given a directed weighted graph for TSP, with a start/end node, split the start/end node into a start node and an end node, with all the outgoing edges on the start node and all the incoming edges on the end node.
• From this to standard TSP: Remove all outgoing edges from the end node; add a single edge from the end node to the start node (which is now the start/end node).