alt Hacker NewsIf you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result?
The classic TSP approach is:
1. Hook up all the nodes in some arbitrary path.
2. Cut the path in two places to create three pieces.
3. Rearrange those three pieces in the six possible ways and keep the shortest.
4. Iterate steps 2-3 until no improvement has been observed for a while.
This is not guaranteed to be optimal, but for most real-world problems either finds the optimal result or is very close.
Replies
neves • 04/24/2025
https://www.youtube.com/watch?v=tChnXG6ulyE
Author's presentation about it
yobbo • 04/24/2025
Iirc the (probably simplified) LKH heuristic they used:
For each iteration:
apply some randomisation
starting at each place
cut the path in 2..n places
reconnect in the most optimal way
if the new tour is the new best, save
➕ show 1 reply
Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html), the achievement here and all the computation is to establish that this is the lower bound (assuming I understood correctly).
So, the heuristic solver worked pretty darn well :) Although, I’m not sure how close it would have been the heuristic algorithm you are describing (I suspect that it is considerably more advanced for good reasons, randomly picking will take too long to converge).