How to turn TSP into minimum hamiltonian path?

问题:

I'm trying to solve this problem http://coj.uci.cu/24h/problem.xhtml?abb=1368.

After a lot of research, and spending a lot of time i was able to implement a Branch and Bound algorithm for TSP, which gets a path passing all points and returning to start.

I was thinking that removing the longest edge from that path i would get the answer, but just when i finished my algorithm, i discovered that this isn't true in all cases, reading this question: Minimal Distance Hamiltonian Path Javascript

I've found some answers saying that adding a dummy point with zero distance to every other point, and then removing it solves the problem, but i don't know the specifics of that. I've already added that dummy point, now instead of getting 26.01 now it's 16.23 as the answer. I haven't removed the dummy point yet, because i don't understand "the whole point of adding the dummy point".

Can you guide me for solving this? Or is it better to take another approach instead of the TSP?

回答1:

The dummy point allows you to have the connection between the two ends at an arbitrarily large distance. In the TSP the two ends would also have to lie very close to each other in order to minimize total distance. In your path problem this requirement does not exist and so a TSP optimum is subjective to a constraint not valid for your problem and thus may not be an optimum to your path problem.

If you introduce a dummy point (or think of it as a shortcut, a wormhole) your ends may lie far apart without affecting your distance.