# What is this Algorithm called? [Traveling Salesman Problem]

I've been thinking about the Traveling Salesman Problem. In examining it and grids of cities, I noticed that I could frequently pick out the shortest route just by staring at it. Granted, I couldn't necessarily get the solutions for the complex grids, but if I could get the simple ones there had to be a way to consistently solve them.

I realized that most(all the ones I've seen) take a circular route around the cities, follow a bit of an outer border. My idea was to start with an algorithm that marks the outermost points of a grid on as many sides as possible. Which is always at least 4(unless you have less than 4) one city for each cardinal direction. Something like this:

(Given, I'm only human so I mostly guessed which cities would be chosen. It's possible the initial algorithm would have chosen differently or chosen more than 4. For the purpose of examples though...)

Then the algorithm finds another set of the outermost points, not including points previously found. It matches these points with the closest red line, and inserts itself there.

it repeats this until all points have been selected and joined.

This seems to work pretty well for smaller simpler selections of cities. Whether or not it falls apart for larger more complex models is as of yet unknown. I suspect a city could be made that breaks this.

Anyways, I'm mostly curious what this sort of algorithm would be called. I find it fascinating, and I'd like to learn more about it.

Is this an actually solution to the problem, or just a close approximation?

• It sounds like a variant of convex hull. Oct 14, 2016 at 18:59
• By " I noticed that I could frequently pick out the shortest route just by staring at it" you actually mean "I set the most powerful parallel processor known to humankind on the problem" Oct 14, 2016 at 19:03
• @RichardTingle Yup pretty much. :P Oct 14, 2016 at 19:08
• @Ucenna You may be onto something. Suppose you have computed the convex hull, and now you want to add some of the "concave" points. Compute the center of gravity (or some time of center) of the hull, and sort the remaining points by their distance from the center. This may speed up the discovery of the closest of the concave points (farthest ones first). Oct 14, 2016 at 19:15
• It is probably an heuristic approximation. TSP is known to be intractable Oct 15, 2016 at 6:23