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?
What is this Algorithm called? [Traveling Salesman Problem]
algorithms;problem solving
What you're doing is making a convex hull. Your algorithm won't be a perfect solution, just an approximation. Consider the following grid:Your algorithm would start by doing something like this:Then things get more tricky, your algorithm would make one of the following choices depending on how it's coded:Only one of these is correct. In theory your algorithm could work, but it would need more polish before then. You'd need some logic to help decide how the inner cities connect with the outer cities. There's a few methods, you could use the greedy algorithm, but that's inaccurate in most situations as it would be in this one. Alternatively, the brute force method is applicable. There's much less permutations to consider this time, as you aren't connecting every combination of cities. Keep in mind that you'd need to consider the distance of OuterCity->InnerCity->OuterCity and not just the distance between OuterCity->InnerCity.