New TSP Method (p=np)

[Strange]

On 25/10/2017 at 1:40 AM, fiveworlds said:

This is because the computer handles square roots badly.

What does that mean? The worst case error is only going to be in the least significant digit of the result.

On 25/10/2017 at 1:40 AM, fiveworlds said:

since the rest is basically just bubble sort

Why on earth would you use a bubble sort? This is a pathologically bad sorting algorithm. I thought the intention here was to produce an efficient algorithm.

On 25/10/2017 at 1:40 AM, fiveworlds said:

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. 

This is irrelevant if you are trying to produce an algorithm that runs in polynomial time instead of exponential time.

1 hour ago, fiveworlds said:

root((x1-x2)^2 * (y1-y2)^2)

The Java Math.hypot(x,y) function will calculate this without overflow. (Again, not relevant to performance.)

[fiveworlds]

Quote

The Java Math.hypot(x,y) function will calculate this without overflow. (Again, not relevant to performance.)

So you can get it running then? Cool.

1. So take a list of cities and then create a new list.
2. Add 3 cities to the new list because the first 3 cities can be put anywhere
3. Then for each city in the list of cities find the position in the new list which results in the lowest change in distance using the cumulative distance formula

This should run in O(n) since for each new city you only need n checks to find the position it fits best.

 

[Strange]

43 minutes ago, fiveworlds said:

So you can get it running then? Cool.

1. So take a list of cities and then create a new list.
2. Add 3 cities to the new list because the first 3 cities can be put anywhere
3. Then for each city in the list of cities find the position in the new list which results in the lowest change in distance using the cumulative distance formula

This should run in O(n) since for each new city you only need n checks to find the position it fits best.

This (like most of your posts) appears to have nothing to do with either the OP's algorithm nor the travelling salesman problem.