New TSP Method (p=np)

TakenItSeriously · October 19, 2017

From Wikipedia:

The travelling salesman problem (TSP) asks the following question:

"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

An Origional Solution:

copyright: October 19, 2017

Author: Paul Ikeda

Version: V3.0.0.0

Any thoughts or quesrions?

Edited October 20, 2017 by TakenItSeriously

thoughtfuhk · October 20, 2017

Don't things like Dwave quantum computing solve these hard problems?

TakenItSeriously · October 20, 2017

2 hours ago, thoughtfuhk said:

Don't things like Dwave quantum computing solve these hard problems?

Well, this problem hasn't been solved yet, at least not to the degree of making it an np solution since the $million is still up for grabs.

When I take on a new unsolved problem that has been considered to be this tough I make it a point to know as little as possible about the methods that were attempted before. It only biases how I look at a problem with how someone else looks at a problem. Not that I'm knocking any previous work, its just my way.

Besides for solutions I've discovered in the past, I've always found the keys to the solution in some unrelated field.

For example, To me this is just a problem of routing a circuit in series as efficiently as possible and that was my job for a very long time in high speed digital design. I Also took some hints based on the concept of the path of least inductance, even though that involves loops of least loop area instead of loops of shortest path. It still provided me with some abstract sense to approach it from the outside in, though I still don't know why yet. I'm sure it'll come to me eventually.

(edit to add: it just came to me. It wasnt the path of least inductance, it was the trasformation from the path of least resistance i.e. shortest path, to the path of least inductance i.e smallest loop area, only in reverse. Part of the paradigm shift from DC to AC. It's actually kind of cool how that worked out..)

Other examples: I solved primeality following a proper analog of harmonic waves. For the origional Twin Paradoc solution, I used my experience with EM waves/fields in HSDD and in that field, time and space is always linked which solved the crux of the problem for me. My solution for the balance paradox came from Einstein's light clock derivation except it had an asymetry to it that was like the asymetry of the Twin Paradox.

I could go on, but suffice it to say, I can't think of a problem I've solved that hasn't had some basis in some unrelated field and searching for proper analogs to problems I recognize is just an automatic habit for me 24/7. It's like maintaining my own personal programmers toolbox for problem solving.

Edited October 20, 2017 by TakenItSeriously

thoughtfuhk · October 20, 2017

14 hours ago, TakenItSeriously said:

Well, this problem hasn't been solved yet, at least not to the degree of making it an np solution since the $million is still up for grabs.

When I take on a new unsolved problem that has been considered to be this tough I make it a point to know as little as possible about the methods that were attempted before. It only biases how I look at a problem with how someone else looks at a problem. Not that I'm knocking any previous work, its just my way.

Besides for solutions I've discovered in the past, I've always found the keys to the solution in some unrelated field.

For example, To me this is just a problem of routing a circuit in series as efficiently as possible and that was my job for a very long time in high speed digital design. I Also took some hints based on the concept of the path of least inductance, even though that involves loops of least loop area instead of loops of shortest path. It still provided me with some abstract sense to approach it from the outside in, though I still don't know why yet. I'm sure it'll come to me eventually.

(edit to add: it just came to me. It wasnt the path of least inductance, it was the trasformation from the path of least resistance i.e. shortest path, to the path of least inductance i.e smallest loop area, only in reverse. Part of the paradigm shift from DC to AC. It's actually kind of cool how that worked out..)

Other examples: I solved primeality following a proper analog of harmonic waves. For the origional Twin Paradoc solution, I used my experience with EM waves/fields in HSDD and in that field, time and space is always linked which solved the crux of the problem for me. My solution for the balance paradox came from Einstein's light clock derivation except it had an asymetry to it that was like the asymetry of the Twin Paradox.

I could go on, but suffice it to say, I can't think of a problem I've solved that hasn't had some basis in some unrelated field and searching for proper analogs to problems I recognize is just an automatic habit for me 24/7. It's like maintaining my own personal programmers toolbox for problem solving.

But, but by limiting your awareness of other attempted solutions, don't you run the risk of making some of those previous mistakes?

Wouldn't you avoid running the above risk, by simply being aware of those past mistakes?

Edited October 20, 2017 by thoughtfuhk

TakenItSeriously · October 22, 2017

It's highly unlikely. There are too many ways that people can make mistakes, when persuing origional work. It's not like making a comon mistake in a math.problem where rigor and methodology funnels peoples thinking into making common mistakes,.

There are far too many ways that people can make mistakes when origional thinking is required.

In fact it's quite the opposite, where I've often duplicated some past discovery that has already been accepted.. From my point of view, its a validation of my work because it was work I discovered independently which is fine as a reenforcing experience. I don't get any credit for that work of course, but geting credit has never been at the top of my goals.

Preventing others from stealing credit for themselves, however, is another matter.

On 10/20/2017 at 2:14 PM, thoughtfuhk said:

But, but by limiting your awareness of other attempted solutions, don't you run the risk of making some of those previous mistakes?

Wouldn't you avoid running the above risk, by simply being aware of those past mistakes?

It's highly unlikely. There are too many ways that people can make mistakes, when persuing origional work. It's not like making a comon mistake in a math.problem where rigor and methodology funnels peoples thinking into making common mistakes,.

There are far too many ways that people can make mistakes when origional thinking is required.

In fact it's quite the opposite, where I've often duplicated some past discovery that has already been accepted.. From my point of view, its a validation of my work because it was work I discovered independently which is fine as a reenforcing experience. I don't get any credit for that work of course, but geting credit has never been at the top of my goals.

Preventing others from stealing credit for themselves, however, is another matter.

Edit to add:

Strange, I forgot to include the quote, but when I teied to edit it in, It wouldn't allow the edit and, instead treated it like adding another post.

pzkpfw · October 22, 2017

Seems to me that step 8, in practice, means this can't be more efficient than any other given method.

Has this method ever been programmed, as opposed to implemented by a human who will tend to use heuristics? (Especially in step 8).

**Strange** · October 22, 2017

On 20/10/2017 at 0:53 AM, TakenItSeriously said:

Any thoughts or quesrions?

Doing a search for "convex hull" and travelling salesman" suggests that this is a very common approach. For example: http://ieeexplore.ieee.org/document/6429058/ (I can't read the full article but the abstract suggests it is similar).

Have you proved that (a) this generates the shortest path and (b) the run time (worst case) is not exponential?

On 20/10/2017 at 0:53 AM, TakenItSeriously said:

copyright: October 19, 2017

The only thing you have copyright on is the images and associated text. You cannot protect an algorithm.

On 20/10/2017 at 7:37 AM, TakenItSeriously said:

When I take on a new unsolved problem that has been considered to be this tough I make it a point to know as little as possible about the methods that were attempted before.

That may be sensible when you start. But after finding a solution, it would make sense to see if it is already known. (This one seems to be.)

TakenItSeriously · October 22, 2017

20 hours ago, pzkpfw said:

Seems to me that step 8, in practice, means this can't be more efficient than any other given method.

Has this method ever been programmed, as opposed to implemented by a human who will tend to use heuristics? (Especially in step 8).

I'm still working on the process for making it a fully automated solution. Step 8 is a problem that makes the process a nested iterative solution, or so I would imagine. However, I have a feeling that it may be connected to the three criteria for identifying the optimal triangle. i.e. if all three criteria of shortest distance, greatest angle and smallest area could not be satisfied simultaniously, then it may be an indication of a local minima, but I need to verify that in Excell where its still transparent.

(edit to add: I agree that it seems like local minimas seem to be an arbitrary condition as opposed to finding a direct connection, but there are examples of arbitrary being an illusion when loops are involved.)

I've automated the calculations for length, area and angles of the triangles, however, calculating the closest distance seems like a Heisenberg type issue, where, if you equated the grid dimensions to a Plank size it would create an ambigious distance between the vertex of the obtuse angle and the hypotenuse when the hypotenuse was not at an orthogonal angle.

Put another way, if you divided the grid to be smaller and smaller to it's infinitessimal limit, it would produce an irrational number for the distance. Though I'm hoping it would be a rational number. I need to think about that a little more.

I could use someones help, for a cut of the prize money, with programming the solution and submitting the paper for publication since the prize money is attached to a published solution, effectively qualifying only those with a PHD in math or computer science as far as I know. I've heard it said that anyone could be published, but I always equated that with saying anyone with the right skills could be in the NBA (but probably not if you never played on a scouted team).

Edited October 22, 2017 by TakenItSeriously

pzkpfw · October 22, 2017

44 minutes ago, TakenItSeriously said:

... Step 8 is a problem that makes the process a nested iterative solution, or so I would imagine. ...

And how do you relate that to the P=NP in your thread title?

TakenItSeriously · October 23, 2017

1 hour ago, pzkpfw said:

And how do you relate that to the P=NP in your thread title?

I'm not sure I understand your question.

This problem was given as the classic example for p=np by several sources, including the site that's awarding the prize. How it relates to polynomials, I assume has to do with the number of permutations for cities involved, but ask the site to get their official point of, view.

Edited October 23, 2017 by TakenItSeriously

Trurl · October 23, 2017

Polygons seem so complex. I like this idea, but circles are more closely related to navigation.

Here is my humble opinion (not understanding the complete traveling salesman problem):

Draw circles at a start point. It doesn’t matter which one. Continue to connect points with circles. Like at technical drawing or highway design where circles intersect is the path.

So you would 2 circles between 2 points. Then you would draw a circle from the 2^nd point to the third and where the intersection occurs is the shortest distance.

The trick is to program it on the computer, taking away circles that no longer give the shortest path.

I believe this is what you did with the polygon that encircles all points. However, I believe it is overly complicating your method.

Brilliant none the less. Will you post your computer program here to share? I’m not concerned it is similar to other approaches. It is your approach.

I suggest you get a technical drawing book and look at the geometric constructions. Circles not polygons, because you have your polygon acting as a circle. Circles are much more suited for the task.

**Strange** · October 23, 2017

15 hours ago, TakenItSeriously said:

This problem was given as the classic example for p=np by several sources, including the site that's awarding the prize. How it relates to polynomials, I assume has to do with the number of permutations for cities involved, but ask the site to get their official point of, view.

So you need to prove that your solution has polynomial run time.

4 minutes ago, Trurl said:

So you would 2 circles between 2 points. Then you would draw a circle from the 2^nd point to the third and where the intersection occurs is the shortest distance.

The challenge is extending that to N points. (I don't understand what you are describing, anyway, so I have no idea if it is a good approach or not.)

uncool · October 23, 2017

Taken: are you assuming that all distances are based on Euclidean distance in the plane? If not, how are you defining "perimeter"? A general graph with distances doesn't simply embed into the plane.

TakenItSeriously · October 24, 2017

7 hours ago, Strange said:

So you need to prove that your solution has polynomial run time.

Right, I agree, so if we start from a least efficient solution, it would be what we call a full game solution, in game theory or simply checking every possible permutation to find the shortest path which would be a factorial expansion or require

n! steps

Which is a very rapid expansion that exceeds polynomial time.

Alternatively, if we could literally move the cities with some mimum distance to each other in ofrder to design the shortest path it would always require the cities to be located on equidistant points of a circle to form a symetrical polygon:

e.g.

for n = 3 it would be a triangle as opposed to three cities in a line.

for n = 4 it would be a square as opposed to an hourglass path.

for n = 5 it would be a Pentagon and so on...

Next we define a perimeter path for the outermost cities that encompass all other cities to create a polygon, though it may be irregular, its still clearly the most efficient path for that particular subset of cities.

Next we add each unconnected city starting with those closest to the perimeter and it would be clear that when adding most cities, they would have one clearly optimal solution. Already reducing n! dramatically.

I will stop the proof short right here for now until I've worked it down to the most optimal method that I can prove for all cases of cities, before I formalize it.

To that end, I have discovered all the methods required for making the proper calculations of dimensions, distance, angles and areas which will be implemented to automatically so that I can study potential options with each change.

I'm hopeful that I will yield a single optimal option for every city which I believe would be called a non-deterministic solution in mathematical terminology.

2 hours ago, uncool said:

Taken: are you assuming that all distances are based on Euclidean distance in the plane? If not, how are you defining "perimeter"? A general graph with distances doesn't simply embed into the plane.

Yes, in a plane.

I think the perimiter path or perimeter cities could be uniquely defined as all cities that form a path such that all, as yet, unconnected cities are encompased and all perimeter cities form an angle pointing out from the center, (Sorry, I cant recall the name used to describe that condition.)

7 hours ago, Trurl said:

Polygons seem so complex. I like this idea, but circles are more closely related to navigation.

Here is my humble opinion (not understanding the complete traveling salesman problem):

Draw circles at a start point. It doesn’t matter which one. Continue to connect points with circles. Like at technical drawing or highway design where circles intersect is the path.

So you would 2 circles between 2 points. Then you would draw a circle from the 2^nd point to the third and where the intersection occurs is the shortest distance.

The trick is to program it on the computer, taking away circles that no longer give the shortest path.

I believe this is what you did with the polygon that encircles all points. However, I believe it is overly complicating your method.

Brilliant none the less. Will you post your computer program here to share? I’m not concerned it is similar to other approaches. It is your approach.

I suggest you get a technical drawing book and look at the geometric constructions. Circles not polygons, because you have your polygon acting as a circle. Circles are much more suited for the task.

Thank you, I really appreciate the kind words.

Due to the huge potential for commercial applications, and the fact that I need to monetize a project soon to continue to pay the rent, I'm afraid that I need to be a little more careful as to what I can show.

I will try to provide any previously known portions of the solutions as I find that they are not original, but as I said before, I like to finish a project to some degree, before doing a search for originality.

Thanks for your understanding.

uncool · October 24, 2017

Then you have not solved the general travelling salesman problem, as the general TSP does not assume the points are in a plane. The general TSP allows *any* distances.

TakenItSeriously · October 24, 2017

1 minute ago, uncool said:

Then you have not solved the general travelling salesman problem, as the general TSP does not assume the points are in a plane. The general TSP allows *any* distances.

How is that inconsistent?

A 2D plane can cover any distance.

uncool · October 24, 2017

10 minutes ago, TakenItSeriously said:

How is that inconsistent?

A 2D plane can cover any distance.

But not any sets of distances.

In the plane, there are no 4 points such that each of them is 1 apart.

Edited October 24, 2017 by uncool

TakenItSeriously · October 24, 2017

18 minutes ago, uncool said:

But not any sets of distances.

In the plane, there are no 4 points such that each of them is 1 apart.

This is a simple hypothetical problem intended to illustrate a certain concept for a group of problems that seem easy to solve or verify in one direction only. So finding a valid solution to the problem in the opposite direction should provide the answer.

This is not intended as some kind of trick question. What it says is all that we may assume to be true.

uncool · October 24, 2017

1 minute ago, TakenItSeriously said:

This is a simple hypothetical problem intended to illustrate a certain concept for a group of problems that seem easy to solve or verify in one direction only. So finding a valid solution to the problem in the opposite direction should provide the answer.

This is not intended as some kind of trick question. What it says is all that we may assume to be true.

I have no idea what you are trying to say here.

Your method doesn't explain how to solve the travelling salesman problem for the graph with 4 equidistant vertices. It only works on a subclass (graphs that can be embedded into the Euclidean plane), and not even then - it requires extra information in the form of an embedding in the plane. As such, it isn't a solution to the TSP.

fiveworlds · October 24, 2017

Quote

Alternatively, if we could literally move the cities with some mimum distance to each other in ofrder to design the shortest path it would always require the cities to be located on equidistant points of a circle to form a symetrical polygon:

Hmm I suppose that might work.

<script>
var cities = [[0,0],[30,40],[100,50]];
var distances = [];
var temp = [,];
var newTempCumulativeDistance;
var newTempCumulativeDistance2;
var tempCumulativeDistance;
var tempCumulativeDistance2;
function distanceFormula(x1,y1,x2,y2){
    return Math.sqrt((x2-x1)+(y2-y1))
}

for(var i = 0; i < cities.length - 1; i++){
    distances[i] = distanceFormula(cities[i][0],cities[i][1],cities[i+1][0],cities[i+1][1]);
}
distances[distances.length] = distanceFormula(cities[0][0],cities[0][1],cities[cities.length-1][0],cities[cities.length-1][1]);

tempCumulativeDistance = distances[0] + distances[distances.length - 1];
for(var t = 1; t < cities.length - 1; i++){
    newTempCumulativeDistance = distanceFormula(cities[t][0],cities[t][1],cities[cities.length-1][0],cities[cities.length-1][1]) + distanceFormula(cities[t][0],cities[t][1],cities[1][0],cities[1][1]);
    newTempCumulativeDistance2 = newTempCumulativeDistance + distanceFormula(cities[0][0],cities[0][1],cities[t-1][0],cities[t-1][1]) + distanceFormula(cities[0][0],cities[0][1],cities[t+1][0],cities[t+1][1]);
    tempCumulativeDistance2 = distances[t] + distances[t-1] + tempCumulativeDistance;
    if(newTempCumulativeDistance2 < tempCumulativeDistance2){
        temp[0] = cities[0][0];
        temp[1] = cities[0][1];
        cities[0][0] = cities[t][0];
        cities[0][1] = cities[t][1];
        cities[t][0] = temp[0];
        cities[t][1] = temp[1];
        temp[0] = distances[0];
        temp[1] = distances[distances.length - 1];
        distances[0] = newTempCumulativeDistance;
        distances[1] = newTempCumulativeDistance2;
        distances[t] = temp[0];
        distances[t+1] = temp[1];
        tempCumulativeDistance = distances[i] + distances[i - 1];
    }
}

for(var i = 1; i < cities.length - 1; i++){
    tempCumulativeDistance = distances[i] + distances[i - 1];
    for(var t = i; t < cities.length - 1; i++){
        newTempCumulativeDistance = distanceFormula(cities[t][0],cities[t][1], cities[i-1][0],cities[i-1][1]) + distanceFormula(cities[t][0],cities[t][1],cities[i+1][0],cities[i+1][1]);
        newTempCumulativeDistance2 = newTempCumulativeDistance + distanceFormula(cities[i][0],cities[i][1],cities[t-1][0],cities[t-1][1]) + distanceFormula(cities[i][0],cities[i][1],cities[t+1][0],cities[t+1][1]);
        tempCumulativeDistance2 = distances[t] + distances[t-1] + tempCumulativeDistance;
        if(newTempCumulativeDistance2 < tempCumulativeDistance2){
            temp[0] = cities[i][0];
            temp[1] = cities[i][1];
            cities[i][0] = cities[t][0];
            cities[i][1] = cities[t][1];
            cities[t][0] = temp[0];
            cities[t][1] = temp[1];
            temp[0] = distances[i];
            temp[1] = distances[i - 1];
            distances[0] = newTempCumulativeDistance;
            distances[1] = newTempCumulativeDistance2;
            distances[t] = temp[0];
            distances[t+1] = temp[1];
            tempCumulativeDistance = distances[i] + distances[i - 1];
        }
    }
}
console.log(distances.reduce(function(pv, cv) { return pv + cv; }, 0));
</script>

Trurl · October 24, 2017

Quote

The challenge is extending that to N points. (I don't understand what you are describing, anyway, so I have no idea if it is a good approach or not.)

I will stay out of the conversation after this post. I just wanted to clear up what I said. It may make more sense than you think. All I am saying is that geometric constructions may simplify the calculation. Let me know if this does or does not make sense.

I am saying take a compass and draw a circle that encompass 2 points. Then with 3 points draw another circle from the 2 points closest together. Keep drawing circles from all points. When there are several points, the circles should intersect somewhere along the circle. Connect those intersections with lines and you have a polygon or the shortest path.

Do you remember in high school when they taught us to find the center of a line by taking a radius more than half of the line and string 2 arcs from each side? The line between those arcs passes through the center of the original line.

I propose if you did the same constructors of circles on the unknown points, geometric constructions such as finding the tangent of a circle (or any of the dozens of circle constructions) you would simplify the computer process. I don’t know how to put a drawing compass into a computer program, but you could always use a CAD script. But then again, I don’t know the algorithm to such a thing, as I have only spent 2 minutes coming up with a hypothesis.

I would say that a radius of the circles, and arcs of those intersecting circles, would eliminate calculations that just can’t be done. I wouldn’t scrap the polygon idea. Instead, I’d use the polygon to form a path between the intersecting arcs.

Also by using circles you have the advantage of all the circular functions.

Do they still teach geometric constructions in geometry? Yes, I know the problem has N points, but this is a simple approach. As more and more points are formed you would have to erase (delete) some the circles no longer needed. And no, I don’t claim I can solve this problem. But I do like how the computer was run to solve this problem. Computers have already ruined chess and that game with squares. I’m glad there is much work to be done to solve this problem.

I hope this is clearer. All I am saying is use geometric circle constructions. After all, you can build almost any shape with them. Someone has probably tried it, but before modern programming, such an idea wasn’t possible. Because in CAD you could program it to draw hundreds of points.

TakenItSeriously · October 24, 2017

2 hours ago, Trurl said:

I will stay out of the conversation after this post. I just wanted to clear up what I said. It may make more sense than you think. All I am saying is that geometric constructions may simplify the calculation. Let me know if this does or does not make sense.

I am saying take a compass and draw a circle that encompass 2 points. Then with 3 points draw another circle from the 2 points closest together. Keep drawing circles from all points. When there are several points, the circles should intersect somewhere along the circle. Connect those intersections with lines and you have a polygon or the shortest path.

Do you remember in high school when they taught us to find the center of a line by taking a radius more than half of the line and string 2 arcs from each side? The line between those arcs passes through the center of the original line.

I propose if you did the same constructors of circles on the unknown points, geometric constructions such as finding the tangent of a circle (or any of the dozens of circle constructions) you would simplify the computer process. I don’t know how to put a drawing compass into a computer program, but you could always use a CAD script. But then again, I don’t know the algorithm to such a thing, as I have only spent 2 minutes coming up with a hypothesis.

I would say that a radius of the circles, and arcs of those intersecting circles, would eliminate calculations that just can’t be done. I wouldn’t scrap the polygon idea. Instead, I’d use the polygon to form a path between the intersecting arcs.

Also by using circles you have the advantage of all the circular functions.

Do they still teach geometric constructions in geometry? Yes, I know the problem has N points, but this is a simple approach. As more and more points are formed you would have to erase (delete) some the circles no longer needed. And no, I don’t claim I can solve this problem. But I do like how the computer was run to solve this problem. Computers have already ruined chess and that game with squares. I’m glad there is much work to be done to solve this problem.

I hope this is clearer. All I am saying is use geometric circle constructions. After all, you can build almost any shape with them. Someone has probably tried it, but before modern programming, such an idea wasn’t possible. Because in CAD you could program it to draw hundreds of points.

I see what your saying. You're essentially using geometric constructions for creating convex polygons as idealized cases for the arrangement of cities to create the shortest possible path.

However as the problem is presented, the cities are arranged arbitrarily without the user actually being allowed to effect their arrangement for the purpose of creating a favorable outcome.

The confusion may have come from my hypothetical description of idealized arrangements of cities always forming a regular complex polygon.

The point was to demonstrate the kind goals that are indicative of examples that are more or less optimal. Note that the main metric is non-intuitive. I accidentally neglected to include it in my last response.. So here it is now:

The loop that creates the shortest path between all cities is the loop that encompasses the greatest area.

While this sounds non-intuitive, you should be able to see that regular convex polygons such as an octagon, are indeed encompasing the greatest area.

Note that the perimeter path that encompases all cities is also a convex polygon, although probably irregular in shape. Never the less it is representative of the optimal path for that particular subset of cities connected by the path..

So if I add a city that is the nearest to the perimeter, it represents a newly created triangle that adds a concave (pointing in) angle to the polygon.

(see second example in the OP)

Of course adding cities to the path always makes the path longer, so we need to choose a triangle that adds the least amount of length to the path and it must be something that a computer can guage. That was the reason for giving the three metrics by which the optimal triangle option would be based. Its not always certain which metric will produce the optimal result, but it should be at least one of the three or possibly one of two cases. Those are the cases I need to study in detail perhaps finding the case where the optimal choice can always be found directly.

Note: just as you said, using circles adds utility for creating metrics to make judgements from but using triangles does the same thing, perhaps more efficiently.

It's similar to how a 2-D field solver works where shapes that need to be modeled are broken down into constituent triangles enableing calculations throughout the framework.

It's a lot to take in but I hope this helps.

4 hours ago, fiveworlds said:

Hmm I suppose that might work.


<script>
var cities = [[0,0],[30,40],[100,50]];
var distances = [];
var temp = [,];
var newTempCumulativeDistance;
var newTempCumulativeDistance2;
var tempCumulativeDistance;
var tempCumulativeDistance2;
function distanceFormula(x1,y1,x2,y2){
    return Math.sqrt((x2-x1)+(y2-y1))
}

for(var i = 0; i < cities.length - 1; i++){
    distances[i] = distanceFormula(cities[i][0],cities[i][1],cities[i+1][0],cities[i+1][1]);
}
distances[distances.length] = distanceFormula(cities[0][0],cities[0][1],cities[cities.length-1][0],cities[cities.length-1][1]);

tempCumulativeDistance = distances[0] + distances[distances.length - 1];
for(var t = 1; t < cities.length - 1; i++){
    newTempCumulativeDistance = distanceFormula(cities[t][0],cities[t][1],cities[cities.length-1][0],cities[cities.length-1][1]) + distanceFormula(cities[t][0],cities[t][1],cities[1][0],cities[1][1]);
    newTempCumulativeDistance2 = newTempCumulativeDistance + distanceFormula(cities[0][0],cities[0][1],cities[t-1][0],cities[t-1][1]) + distanceFormula(cities[0][0],cities[0][1],cities[t+1][0],cities[t+1][1]);
    tempCumulativeDistance2 = distances[t] + distances[t-1] + tempCumulativeDistance;
    if(newTempCumulativeDistance2 < tempCumulativeDistance2){
        temp[0] = cities[0][0];
        temp[1] = cities[0][1];
        cities[0][0] = cities[t][0];
        cities[0][1] = cities[t][1];
        cities[t][0] = temp[0];
        cities[t][1] = temp[1];
        temp[0] = distances[0];
        temp[1] = distances[distances.length - 1];
        distances[0] = newTempCumulativeDistance;
        distances[1] = newTempCumulativeDistance2;
        distances[t] = temp[0];
        distances[t+1] = temp[1];
        tempCumulativeDistance = distances[i] + distances[i - 1];
    }
}

for(var i = 1; i < cities.length - 1; i++){
    tempCumulativeDistance = distances[i] + distances[i - 1];
    for(var t = i; t < cities.length - 1; i++){
        newTempCumulativeDistance = distanceFormula(cities[t][0],cities[t][1], cities[i-1][0],cities[i-1][1]) + distanceFormula(cities[t][0],cities[t][1],cities[i+1][0],cities[i+1][1]);
        newTempCumulativeDistance2 = newTempCumulativeDistance + distanceFormula(cities[i][0],cities[i][1],cities[t-1][0],cities[t-1][1]) + distanceFormula(cities[i][0],cities[i][1],cities[t+1][0],cities[t+1][1]);
        tempCumulativeDistance2 = distances[t] + distances[t-1] + tempCumulativeDistance;
        if(newTempCumulativeDistance2 < tempCumulativeDistance2){
            temp[0] = cities[i][0];
            temp[1] = cities[i][1];
            cities[i][0] = cities[t][0];
            cities[i][1] = cities[t][1];
            cities[t][0] = temp[0];
            cities[t][1] = temp[1];
            temp[0] = distances[i];
            temp[1] = distances[i - 1];
            distances[0] = newTempCumulativeDistance;
            distances[1] = newTempCumulativeDistance2;
            distances[t] = temp[0];
            distances[t+1] = temp[1];
            tempCumulativeDistance = distances[i] + distances[i - 1];
        }
    }
}
console.log(distances.reduce(function(pv, cv) { return pv + cv; }, 0));
</script>

Thanks for providing the code. Unfortunately I don't know c as I'm not a professional programmer (EE Engineer). So I'm not sure what's going on with what appears to be arrays with some kind ov properties attached. Also I don't have easy acess to a PC to run it on (very long story).

Could you possibly include comment statements?

Edited October 24, 2017 by TakenItSeriously

fiveworlds · October 25, 2017

Quote

Could you possibly include comment statements?

I can. Since this is better explained in Java I wrote it in java. First we create the class to run the actual program. Here I generate a few cities and add them to the list of cities.

package mycode.tsp;
/////
//  Runs the program and generates the list of cities
/////
public class MyMain {
    public static double coordinates[] = {10,20,30};
    public static Cities cities;
    public static void main(String[] args) {
        City city = new City("Washington",coordinates);
        System.out.println(city.name + " --> " + city.coords[0] + "," + city.coords[1] + "," + city.coords[2]);
        cities = new Cities(10);
        cities.addCity(city);

        coordinates[0] = 30;
        coordinates[1] = 40;
        coordinates[2] = 50;
        city = new City("Paris",coordinates);
        cities.addCity(city);

        coordinates[0] = 60;
        coordinates[1] = 80;
        coordinates[2] = 30;
        city = new City("Berlin",coordinates);
        cities.addCity(city);

        coordinates[0] = 20;
        coordinates[1] = 100;
        coordinates[2] = 70;
        city = new City("New York",coordinates);
        cities.addCity(city);

        coordinates[0] = 30;
        coordinates[1] = 45;
        coordinates[2] = 50;
        city = new City("Hong Kong",coordinates);
        cities.addCity(city);

        for (int k = 0; k < cities.cities.size(); k++){
            System.out.println(cities.cities.get(k).name);
        }
    }
}

Next is the city Object which contains information about each city like name and position etc.

package mycode.tsp;

/////
//  The city object which contains the name and position of the city.
/////
public class City {
    public String name;
    public double coords[] = new double[3];
    public City(String name, double[] coordinates){
        this.name = name;
        this.coords = coordinates;
    }
}

Then there is the class that does all the actual calculation.

package mycode.tsp;

import java.util.ArrayList;

/////
//  The cities object which is the list containing all the cities
/////
public class Cities {
    public static ArrayList<City> cities;
    public static int size;
    public City temp;
    public static int index = -1;
    public boolean swapped;
    public int i;
    public static double
        coodinates[],
        coodinates2[],
        distance4, distance2;

    ///
    // Create the object
    ///

    public Cities(int size){
        cities = new ArrayList<City>();
        this.size = size;
    }

    public void addCity(City city){
        if(cities.size() > 1){

            swapped = true;
            while (swapped){

                distance4 = cumulativeDistance(
                    cities.get(cities.size()-1),
                    cities.get(0),
                    cities.get(1),
                    city
                );
                System.out.println("test " + city.name + " "+distance4);
                ///
                // The first Problem
                ///
                cities.add(city);

            }

        } else {
            cities.add(city);
        }
    }

    ///
    // Cumulative Distance Formula
    ///
    private double cumulativeDistance(City left,City middle,City right,City middle2){
        return  loopedDistance(left, middle,right) - loopedDistance(left, middle2, right);
    }

    ///
    // Looped Distance Formula
    ///
    private double loopedDistance(City left,City middle,City right){
        return distance(left.coords, middle.coords)+distance(right.coords, middle.coords);
    }

    ///
    // Euclidean Distance Formula
    ///
    private double distance(double coordinates[], double coordinates2[]){
        double distance3 = 0;
        int t = 0;
        while (t < 3){
            distance3 = distance3 + Math.pow((coordinates[t] - coordinates2[t]), 2);
            t++;
        }
        return Math.sqrt(distance3);
    }
}

The first problem is that when I try to get the cumulative distance then the result is.

Berlin Cumulative Distance --> 0.0
New York Cumulative Distance --> 0.0
Hong Kong Cumulative Distance --> 0.0

This is because the computer handles square roots badly. So then you would have to work out a way of finding the cumulative distance quickly (that is to say in polynomial time) since the rest is basically just bubble sort.

I would imagine the fastest way of solving the square root problem is to design a rom chip which maps integers to their square root then send data from java to the chip and get the result.

Edited October 25, 2017 by fiveworlds

TakenItSeriously · October 25, 2017

13 hours ago, fiveworlds said:

I can. Since this is better explained in Java I wrote it in java. First we create the class to run the actual program. Here I generate a few cities and add them to the list of cities.


package mycode.tsp;
/////
//  Runs the program and generates the list of cities
/////
public class MyMain {
    public static double coordinates[] = {10,20,30};
    public static Cities cities;
    public static void main(String[] args) {
        City city = new City("Washington",coordinates);
        System.out.println(city.name + " --> " + city.coords[0] + "," + city.coords[1] + "," + city.coords[2]);
        cities = new Cities(10);
        cities.addCity(city);

        coordinates[0] = 30;
        coordinates[1] = 40;
        coordinates[2] = 50;
        city = new City("Paris",coordinates);
        cities.addCity(city);

        coordinates[0] = 60;
        coordinates[1] = 80;
        coordinates[2] = 30;
        city = new City("Berlin",coordinates);
        cities.addCity(city);

        coordinates[0] = 20;
        coordinates[1] = 100;
        coordinates[2] = 70;
        city = new City("New York",coordinates);
        cities.addCity(city);

        coordinates[0] = 30;
        coordinates[1] = 45;
        coordinates[2] = 50;
        city = new City("Hong Kong",coordinates);
        cities.addCity(city);

        for (int k = 0; k < cities.cities.size(); k++){
            System.out.println(cities.cities.get(k).name);
        }
    }
}

Next is the city Object which contains information about each city like name and position etc.


package mycode.tsp;

/////
//  The city object which contains the name and position of the city.
/////
public class City {
    public String name;
    public double coords[] = new double[3];
    public City(String name, double[] coordinates){
        this.name = name;
        this.coords = coordinates;
    }
}

Then there is the class that does all the actual calculation.


package mycode.tsp;

import java.util.ArrayList;

/////
//  The cities object which is the list containing all the cities
/////
public class Cities {
    public static ArrayList<City> cities;
    public static int size;
    public City temp;
    public static int index = -1;
    public boolean swapped;
    public int i;
    public static double
        coodinates[],
        coodinates2[],
        distance4, distance2;

    ///
    // Create the object
    ///

    public Cities(int size){
        cities = new ArrayList<City>();
        this.size = size;
    }

    public void addCity(City city){
        if(cities.size() > 1){

            swapped = true;
            while (swapped){

                distance4 = cumulativeDistance(
                    cities.get(cities.size()-1),
                    cities.get(0),
                    cities.get(1),
                    city
                );
                System.out.println("test " + city.name + " "+distance4);
                ///
                // The first Problem
                ///
                cities.add(city);

            }

        } else {
            cities.add(city);
        }
    }

    ///
    // Cumulative Distance Formula
    ///
    private double cumulativeDistance(City left,City middle,City right,City middle2){
        return  loopedDistance(left, middle,right) - loopedDistance(left, middle2, right);
    }

    ///
    // Looped Distance Formula
    ///
    private double loopedDistance(City left,City middle,City right){
        return distance(left.coords, middle.coords)+distance(right.coords, middle.coords);
    }

    ///
    // Euclidean Distance Formula
    ///
    private double distance(double coordinates[], double coordinates2[]){
        double distance3 = 0;
        int t = 0;
        while (t < 3){
            distance3 = distance3 + Math.pow((coordinates[t] - coordinates2[t]), 2);
            t++;
        }
        return Math.sqrt(distance3);
    }
}

The first problem is that when I try to get the cumulative distance then the result is.

Berlin Cumulative Distance --> 0.0
New York Cumulative Distance --> 0.0
Hong Kong Cumulative Distance --> 0.0

This is because the computer handles square roots badly. So then you would have to work out a way of finding the cumulative distance quickly (that is to say in polynomial time) since the rest is basically just bubble sort.

I would imagine the fastest way of solving the square root problem is to design a rom chip which maps integers to their square root then send data from java to the chip and get the result.

Why does it look like each city has 3 coordinates? You only need two coordinates for a 2D plane.

Square roots shouldn’t be an issue for a problem that small. Excel handles calculations of distances in loops with 30 city’s, most involving irrational numbers, without any lag and Excel is not exactly known for it’s efficiency.

Perhaps your calculating relative distances which end up as 0 due to being in a loop? You may want to check to make sure negative distances aren’t being included.

fiveworlds · October 26, 2017

Quote

Square roots shouldn’t be an issue for a problem that small. Excel handles calculations of distances in loops with 30 city’s, most involving irrational numbers, without any lag and Excel is not exactly known for it’s efficiency.

There is workarounds like this example from jsfromhell.com but they tend to be slow.


BigNumber = function(n, p, r){
    var o = this, i;
    if(n instanceof BigNumber){
        for(i in {precision: 0, roundType: 0, _s: 0, _f: 0}) o[i] = n[i];
        o._d = n._d.slice();
        return;
    }
    o.precision = isNaN(p = Math.abs(p)) ? BigNumber.defaultPrecision : p;
    o.roundType = isNaN(r = Math.abs(r)) ? BigNumber.defaultRoundType : r;
    o._s = (n += "").charAt(0) == "-";
    o._f = ((n = n.replace(/[^\d.]/g, "").split(".", 2))[0] = n[0].replace(/^0+/, "") || "0").length;
    for(i = (n = o._d = (n.join("") || "0").split("")).length; i; n[--i] = +n[i]);
    o.round();
};
with({$: BigNumber, o: BigNumber.prototype}){
    $.ROUND_HALF_EVEN = ($.ROUND_HALF_DOWN = ($.ROUND_HALF_UP = ($.ROUND_FLOOR = ($.ROUND_CEIL = ($.ROUND_DOWN = ($.ROUND_UP = 0) + 1) + 1) + 1) + 1) + 1) + 1;
    $.defaultPrecision = 40;
    $.defaultRoundType = $.ROUND_HALF_UP;
    o.add = function(n){
        if(this._s != (n = new BigNumber(n))._s)
            return n._s ^= 1, this.subtract(n);
        var o = new BigNumber(this), a = o._d, b = n._d, la = o._f,
        lb = n._f, n = Math.max(la, lb), i, r;
        la != lb && ((lb = la - lb) > 0 ? o._zeroes(b, lb, 1) : o._zeroes(a, -lb, 1));
        i = (la = a.length) == (lb = b.length) ? a.length : ((lb = la - lb) > 0 ? o._zeroes(b, lb) : o._zeroes(a, -lb)).length;
        for(r = 0; i; r = (a[--i] = a[i] + b[i] + r) / 10 >>> 0, a[i] %= 10);
        return r && ++n && a.unshift(r), o._f = n, o.round();
    };
    o.subtract = function(n){
        if(this._s != (n = new BigNumber(n))._s)
            return n._s ^= 1, this.add(n);
        var o = new BigNumber(this), c = o.abs().compare(n.abs()) + 1, a = c ? o : n, b = c ? n : o, la = a._f, lb = b._f, d = la, i, j;
        a = a._d, b = b._d, la != lb && ((lb = la - lb) > 0 ? o._zeroes(b, lb, 1) : o._zeroes(a, -lb, 1));
        for(i = (la = a.length) == (lb = b.length) ? a.length : ((lb = la - lb) > 0 ? o._zeroes(b, lb) : o._zeroes(a, -lb)).length; i;){
            if(a[--i] < b[i]){
                for(j = i; j && !a[--j]; a[j] = 9);
                --a[j], a[i] += 10;
            }
            b[i] = a[i] - b[i];
        }
        return c || (o._s ^= 1), o._f = d, o._d = b, o.round();
    };
    o.multiply = function(n){
        var o = new BigNumber(this), r = o._d.length >= (n = new BigNumber(n))._d.length, a = (r ? o : n)._d,
        b = (r ? n : o)._d, la = a.length, lb = b.length, x = new BigNumber, i, j, s;
        for(i = lb; i; r && s.unshift(r), x.set(x.add(new BigNumber(s.join("")))))
            for(s = (new Array(lb - --i)).join("0").split(""), r = 0, j = la; j; r += a[--j] * b[i], s.unshift(r % 10), r = (r / 10) >>> 0);
        return o._s = o._s != n._s, o._f = ((r = la + lb - o._f - n._f) >= (j = (o._d = x._d).length) ? this._zeroes(o._d, r - j + 1, 1).length : j) - r, o.round();
    };
    o.divide = function(n){
        if((n = new BigNumber(n)) == "0")
            throw new Error("Division by 0");
        else if(this == "0")
            return new BigNumber;
        var o = new BigNumber(this), a = o._d, b = n._d, la = a.length - o._f,
        lb = b.length - n._f, r = new BigNumber, i = 0, j, s, l, f = 1, c = 0, e = 0;
        r._s = o._s != n._s, r.precision = Math.max(o.precision, n.precision),
        r._f = +r._d.pop(), la != lb && o._zeroes(la > lb ? b : a, Math.abs(la - lb));
        n._f = b.length, b = n, b._s = false, b = b.round();
        for(n = new BigNumber; a[0] == "0"; a.shift());
        out:
        do{
            for(l = c = 0, n == "0" && (n._d = [], n._f = 0); i < a.length && n.compare(b) == -1; ++i){
                (l = i + 1 == a.length, (!f && ++c > 1 || (e = l && n == "0" && a[i] == "0")))
                && (r._f == r._d.length && ++r._f, r._d.push(0));
                (a[i] == "0" && n == "0") || (n._d.push(a[i]), ++n._f);
                if(e)
                    break out;
                if((l && n.compare(b) == -1 && (r._f == r._d.length && ++r._f, 1)) || (l = 0))
                    while(r._d.push(0), n._d.push(0), ++n._f, n.compare(b) == -1);
            }
            if(f = 0, n.compare(b) == -1 && !(l = 0))
                while(l ? r._d.push(0) : l = 1, n._d.push(0), ++n._f, n.compare(b) == -1);
            for(s = new BigNumber, j = 0; n.compare(y = s.add(b)) + 1 && ++j; s.set(y));
            n.set(n.subtract(s)), !l && r._f == r._d.length && ++r._f, r._d.push(j);
        }
        while((i < a.length || n != "0") && (r._d.length - r._f) <= r.precision);
        return r.round();
    };
    o.mod = function(n){
        return this.subtract(this.divide(n).intPart().multiply(n));
    };
    o.pow = function(n){
        var o = new BigNumber(this), i;
        if((n = (new BigNumber(n)).intPart()) == 0) return o.set(1);
        for(i = Math.abs(n); --i; o.set(o.multiply(this)));
        return n < 0 ? o.set((new BigNumber(1)).divide(o)) : o;
    };
    o.set = function(n){
        return this.constructor(n), this;
    };
    o.compare = function(n){
        var a = this, la = this._f, b = new BigNumber(n), lb = b._f, r = [-1, 1], i, l;
        if(a._s != b._s)
            return a._s ? -1 : 1;
        if(la != lb)
            return r[(la > lb) ^ a._s];
        for(la = (a = a._d).length, lb = (b = b._d).length, i = -1, l = Math.min(la, lb); ++i < l;)
            if(a[i] != b[i])
                return r[(a[i] > b[i]) ^ a._s];
        return la != lb ? r[(la > lb) ^ a._s] : 0;
    };
    o.negate = function(){
        var n = new BigNumber(this); return n._s ^= 1, n;
    };
    o.abs = function(){
        var n = new BigNumber(this); return n._s = 0, n;
    };
    o.intPart = function(){
        return new BigNumber((this._s ? "-" : "") + (this._d.slice(0, this._f).join("") || "0"));
    };
    o.valueOf = o.toString = function(){
        var o = this;
        return (o._s ? "-" : "") + (o._d.slice(0, o._f).join("") || "0") + (o._f != o._d.length ? "." + o._d.slice(o._f).join("") : "");
    };
    o._zeroes = function(n, l, t){
        var s = ["push", "unshift"][t || 0];
        for(++l; --l;  n[s](0));
        return n;
    };
    o.round = function(){
        if("_rounding" in this) return this;
        var $ = BigNumber, r = this.roundType, b = this._d, d, p, n, x;
        for(this._rounding = true; this._f > 1 && !b[0]; --this._f, b.shift());
        for(d = this._f, p = this.precision + d, n = b[p]; b.length > d && !b[b.length -1]; b.pop());
        x = (this._s ? "-" : "") + (p - d ? "0." + this._zeroes([], p - d - 1).join("") : "") + 1;
        if(b.length > p){
            n && (r == $.DOWN ? false : r == $.UP ? true : r == $.CEIL ? !this._s
            : r == $.FLOOR ? this._s : r == $.HALF_UP ? n >= 5 : r == $.HALF_DOWN ? n > 5
            : r == $.HALF_EVEN ? n >= 5 && b[p - 1] & 1 : false) && this.add(x);
            b.splice(p, b.length - p);
        }
        return delete this._rounding, this;
    };
}

I wonder if you can get away with not using square roots at all. For comparing two distances by hand you can do.

root((x1-x2)^2 * (y1-y2)^2) = root((x3-x4)^2 * (y3-y4)^2)

then the roots cancel. So you get

(x1-x2)^2 + (y1-y2)^2 = (x3-x4)^2 + (y3-y4)^2

but here you have 4 distances so it is

root((x1-x2)^2 + (y1-y2)^2) + root((x1-x3)^2 + (y1-y3)^2) = root((x4-x5)^2 + (y4-y5)^2) + root((x4-x6)^2 + (y4-y6)^2)

which becomes

root((x1-x2)^2 + (y1-y2)^2) + root((x1-x3)^2 + (y1-y3)^2) / root((x4-x5)^2 + (y4-y5)^2) + root((x4-x6)^2 + (y4-y6)^2) = c

where we need to find if c is positive or negative.

maybe it is still possible to cancel the roots but it is a bit harder.

Sign In

New TSP Method (p=np)

Recommended Posts

TakenItSeriously

thoughtfuhk

TakenItSeriously

thoughtfuhk

TakenItSeriously

pzkpfw

Strange

TakenItSeriously

pzkpfw

TakenItSeriously

Trurl

Strange

uncool

TakenItSeriously

uncool

TakenItSeriously

uncool

TakenItSeriously

uncool

fiveworlds

Trurl

TakenItSeriously

fiveworlds

TakenItSeriously

fiveworlds

Create an account or sign in to comment

Create an account

Sign in

Browse

Activity

Important Information