-4
$\begingroup$

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.

GitHub

|cite|improve this question
$\endgroup$

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.

  • 5
    $\begingroup$ 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. $\endgroup$ – Juho Dec 9 '17 at 19:00
  • 6
    $\begingroup$ 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. $\endgroup$ – David Richerby Dec 10 '17 at 20:21
  • $\begingroup$ @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. $\endgroup$ – T145 Dec 10 '17 at 20:35
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Dec 10 '17 at 21:27
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Gilles♦ Dec 11 '17 at 17:07
11
$\begingroup$

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:

  1. Your program is correct
  2. Your program does indeed run in polynomial time.

I suspect the problem lies with (1), but you state your complexities for (2) without explaining any reasoning behind them, so there may be a problem there.

If you are serious about this, or about tackling large problems in CS theory in general, I would highly advise that you learn how to use and encode your algorithm in a proof assistant, such as Coq or Agda. Such systems will not allow you to make mistakes in your proof, so if you manage to prove your algorithm correct, then there will be a high degree of confidence in your result. And if your algorithm is incorrect, then the errors or pain points should reveal themselves quickly.

Finally, it's important to realize that P vs. NP is entirely about proofs: the question is, are these two mathematical sets equal? There are plenty of algorithms that approximate solutions to NP-hard problems, and many that are polynomial in common cases, but exponential in the worst case (like SAT solvers). So experimental results will not be enough here.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Firstly, dang. Secondly, as I mention in the comments, that's exactly my mindset. Everything I've done up to now just hasn't given an incorrect answer. Finally, why do I need a proof? Assuming I have the correct implementation, isn't the code all that matters? How would I go about "reverse-engineering" a formal proof from my code? $\endgroup$ – T145 Dec 9 '17 at 21:14
  • 6
    $\begingroup$ @T145 Otherwise, how do we know that your algorithm works for the first million graphs, but fails on one after that? Testing can never prove total correctness, and like I said, without total correctness, all you have is an approximation algorithm, or a solver for a limited subproblem, of which there are plenty. (That doesn't mean yours isn't interesting, or even worth a paper, but it certainly means it's not worth the million dollars). $\endgroup$ – jmite Dec 9 '17 at 21:38
  • $\begingroup$ How would I construct a proof from my code? Would doing so be violating the principle of doing so, as if it does fail on the millionth case then my proof would fail as well? $\endgroup$ – T145 Dec 9 '17 at 21:41
  • 2
    $\begingroup$ @T145 As for reverse-engineering a proof, there's no way to do that algorithmically. Use your intuition: how have you convinced yourself that this does indeed solve all cases? Can you make that argument formal? That is, assuming you have an arbitrary graph, showing that your algorithm computes exactly the shortest path? For your case, what you need is a proof that the shortest path in your geometric graph does in fact correspond to the one in the original graph. You will probably want to read up on induction and invariants, and how to prove algorithms correct in general. $\endgroup$ – jmite Dec 9 '17 at 21:41
  • 1
    $\begingroup$ @T145 If you want to use a proof-assistant, Volumes 1 and 3 of the free Software Foundations book will likely prove helpful. $\endgroup$ – jmite Dec 9 '17 at 21:43

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