3

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...)

Map 1

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.

enter image description here

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

enter image description here enter image description here

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?

Improve this question
7
  • 1
    It sounds like a variant of convex hull.
    – Frank Hileman
    Commented Oct 14, 2016 at 18:59
  • 5
    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"
    – Richard Tingle
    Commented Oct 14, 2016 at 19:03
  • @RichardTingle Yup pretty much. :P
    – Ucenna
    Commented Oct 14, 2016 at 19:08
  • 1
    @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).
    – Frank Hileman
    Commented Oct 14, 2016 at 19:15
  • 1
    It is probably an heuristic approximation. TSP is known to be intractable
    – Basile Starynkevitch
    Commented Oct 15, 2016 at 6:23

1 Answer 1

Reset to default
2

What you're doing is making a convex hull. Your algorithm won't be a perfect solution, just an approximation. Consider the following grid:

enter image description here

Your algorithm would start by doing something like this:

enter image description here

Then things get more tricky, your algorithm would make one of the following choices depending on how it's coded:

enter image description here

enter image description here

enter image description here

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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.