# Traveling Salesman Solution [closed]

This problem has been heavily studied, and at last may have a potential solution. The concept I have come up with was made entirely on my own, but is close to some other theories that will be referenced.

The intended purpose for posting here is to have more experienced software developers review my theory. Should it prove to hold up, my ultimate goal is to publish an academic paper covering it.

## The Theory

My first step was to think about the problem differently. The classic TSP (Traveling Salesman Problem) is stated along these lines:

A traveling salesman wants to sell his product in a set of given cities, and wants to travel along the shortest path between them all, returning to the city he started at. Each city is visited only one time. How is the length of this path found?

The problem is defined as the shortest route that starts and ends at the same point, which is essentially the shortest circuit for the whole graph, making the start aribtrary. In other words, no matter where you start on the graph, there will only be one "shortest path." The question then becomes:

What is the shortest circuit for the given graph, visiting each point only once?

To calculate this, I thought of how to make the graph more "understandable" for a computer, and the easiest way is just to make the whole graph into one line. Thinking abstractly, we take all of the points in the graph and arrange them into one straight line along the y-axis, creating a path with the shortest distance between each point. This produces the shortest line possible. To make a circuit, we just get the distance from the last point in the line to the first, and add it back onto the total distance of the line. None of the point values are actually changed, just rearranged using abstract thought. Now for constructing this line.

Working in the first quadrant, it turns out you can just iterate over the x and y axis adding the points closest to y=0 in order from the bottom, and you'll just get the right path. If you have negative y values, then the starting y becomes the most negative value. This process will build the shortest line. Again, since the start is aribtrary, the first point encountered can be the start. Due to the nature of this line, all of the points must be sorted by order of least to greatest x and y. This doesn't change their values; all points are put in an order that's easy to calculate. Because the distance formula is used, any calculations done in the third quadrant are brought up to the first, and any done in the fourth are brought up to the second (by order of magnitude), which is also conveniently friendly to a number line.

Now this works very well for any random scatter plot of data, but what happens if y-values between two or more points are shared? How is this calculated? We'll call these kinds of points "collisions," and calculating them is challenging. When a collision is encountered, we have to decide whether it goes before or after the first point that shared the same y-value but wasn't a collision, which we'll call a "source." We also have to choose whether it goes directly before or after the source, or somewhere farther down the path in either direction.

I've tried many variations on a solution, and how I solve it right now is as follows. If the graph contains any collisions, check to see if the collision matches a source. If the collision has a shorter distance (a.k.a the most optimal choice) compared to the source's neighbor (the next point in the graph disregarding collisions) then set the collision as the neighbor and remove it from a collision cache. After the shortest path is computed, if any collisions are leftover, find the best place to put them into the graph. My initial intuition was to throw all leftover collisions onto the end of the line, which is right a suprising amount of the time.

After some research, my solution most closely resembles the Nearest Neighbor Algorithm by Rosenkratz, Stearns and Lewis, detailed on page 242 of this paper. The fact that people have thought along these lines in the past gave me reassurance that I was on an accurate path.

A proof to reflect the algorithm is a work in progress.

## Results

Currently my implementation works for the following cases:

• a single point (length 0)
• simple to complex polygons
• lines (simple to complex functions implied)
• scatter plots (implied from polygons)

Every possible path would have to be either one or a mixture of these.

Here is the asymptotic analysis for the whole program.

The code has been posted to CodeReview for review.

## closed as unclear what you're asking by Gilles♦Dec 11 '17 at 17:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• We discourage questions that ask to verify a proposed solution. What's more, I guess you are claiming a polynomial-time algorithm for solving TSP, which is well-known to be NP-complete. This is an extraordinary claim requiring extraordinary proof. A quick way to see where your algorithm fails is to generate small instances of TSP, use a brute-force algorithm to generate the optimal solution, and checking what your algorithm outputs. – Juho Dec 9 '17 at 19:00
• I'm voting to close this question as off-topic because it seeks verification of what would be a major breakthrough in theoretical CS. We're a question and answer site, not a peer review service. – David Richerby Dec 10 '17 at 20:21
• @DavidRicherby I'll take jmite's advice and come back w/ a formal proof that people can actually verify, as there isn't much for people here to even review. I don't know why CR mods recommended posting here honestly, but I'm glad I did, otherwise I wouldn't have learned about the importance of backing my code up w/ a proof. – T145 Dec 10 '17 at 20:35
• @T145 It's great that you're going to try to come up with a proof, but checking whether you've correctly solved what is literally the biggest challenge in computer science is still off-topic here. – David Richerby Dec 10 '17 at 21:27
• Comments are not for extended discussion; this conversation has been moved to chat. – Gilles Dec 11 '17 at 17:07

First, it's important to recognize the gravity of what you are proposing. If correct, your algorithm is worth \$1 Million USD. Secondly, many many people have tried and failed to solve this problem. So it's important to approach this with the assumption that you are wrong, and to exhaustively try to disprove yourself.

The next step is to prove two things: