Nice visualization of an application of simulated annealing.
We should keep in mind that the OP is doing the traveling salesman problem (TSP) in the plane. So we should recall the nice Karp result in about 1972: With meager assumptions on the probability distribution of the cities, for any number x, no matter how small, as the number of cities n goes to infinity, there is a simple approach that will come within x% of optimality with probability 1 - x.
This simple approach? Start by connecting the cities with a minimum spanning tree. Then for the TSP tour, just traverse the spanning tree except going directly to the next city in the tree traversal not already visited. That is, when following the tree would cause visiting a city a second time, just go directly, not following an arc in the tree, to the next city in the tree traversal not yet visited.
So intuitively the value is, for large n, get about as close, about as often as wish, and for small n just enumerate!
Intuitively what is going on is that one of the main challenges is identifying the appropriate clusters of cities and, then, connecting the clusters, and the minimum spanning tree tends to find the right clusters.
Of course, there are at least two algorithms for finding minimum spanning trees, and as I recall both run in time proportional to n^2. So, we have a polynomial algorithm that is, for large n, for TSP in the plane, as close as we please.
For the "plane", I meant R^2, where R is the set of real numbers, that is, ordinary Euclidean 2-space. But Karp's approach also works the same in R^m for any positive integer m.
We should keep in mind that the OP is doing the traveling salesman problem (TSP) in the plane. So we should recall the nice Karp result in about 1972: With meager assumptions on the probability distribution of the cities, for any number x, no matter how small, as the number of cities n goes to infinity, there is a simple approach that will come within x% of optimality with probability 1 - x.
This simple approach? Start by connecting the cities with a minimum spanning tree. Then for the TSP tour, just traverse the spanning tree except going directly to the next city in the tree traversal not already visited. That is, when following the tree would cause visiting a city a second time, just go directly, not following an arc in the tree, to the next city in the tree traversal not yet visited.
So intuitively the value is, for large n, get about as close, about as often as wish, and for small n just enumerate!
Intuitively what is going on is that one of the main challenges is identifying the appropriate clusters of cities and, then, connecting the clusters, and the minimum spanning tree tends to find the right clusters.
Of course, there are at least two algorithms for finding minimum spanning trees, and as I recall both run in time proportional to n^2. So, we have a polynomial algorithm that is, for large n, for TSP in the plane, as close as we please.
For the "plane", I meant R^2, where R is the set of real numbers, that is, ordinary Euclidean 2-space. But Karp's approach also works the same in R^m for any positive integer m.