Jump to content

New TSP Method (p=np)


TakenItSeriously

Recommended Posts

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

Link to comment
Share on other sites

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.

 

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.