Heuristic for optimising the traveling salesman problem (tsp) in under O(n²)

Question

I have a large data set (more than 3 Million distinct data points that have 6 integer numbers). I want to compute the shortest route in terms of hamming distance. (amount of numbers that change between two data points, meaning that the distance between two points can either be 1, 2, 3, 4, 5 or 6).

Using even nearest neighbour is too slow because it is O(n²). And all the other algorithms I have seen so far ar also at least O(n²).

Are there faster heuristics for optimising the traveling salesman problem? (maybe O(n*log(n)) for example)

CLARIFICATION:

I know that I cannot compute the distance between every pair of points, which would be O(n²) already.

What I'm asking for is an algorithm that produces decent results but with a time complexity that is less than O(n²).

The algorithm should be an improvement over just randomly arranging all datapoints in a roundtrip.

One approach with O(1) although not that good would be:

1. Arrange the datapoints in a roundtrip somehow (use the way they are already arranged in memory (otherwise this would be O(n))
2. Take two random datapoints. Swap them and check if the sum of the distances to the adjacent data points has improved. If not, swap them back.
3. Repeat with 2 a constant amount of times.

This does reduce the total distance of the roundtrip and didn't calculate the distance for all pairs of data points.

There should be existing algorithms that do something like this, but with better gain per runtime.

Answer 1

When dealing with an O(n²) solution, it can be helpful to break down the problem into a smaller set. Unfortunately, I do not believe there is a way for you to approach this problem in a sub O(n²) way.

Your first step is to accept that your solution will not be 100% accurate, just acceptably accurate. This can be hard for programmers to accept. Sorry, this is just the way things are (unless you happen to have quantum computer handy).

Breaking down your problem into smaller problems does two things:

1. It reduces the exponential performance penalty

2. It allows your to make use of multiple processor cores

Your next step is to create a primary node selection algorithm. Use statistics, or some other criteria (you did not provide much detail in your question) in a node selection function selectSubset. This function should take as a parameter a set of arbitrary N and return a subset significantly less than N that is as evenly distributed as possible.

You then pass this subset to two functions... findDistances and recursively, selectSubset. If your functions are pure, you can use this as an a point to spawn more threads.

I hope that is clear that the functional paradigm is optimal for this problem.

Think of your first subset of nodes as the 7-lane super-highways, then the next subsets as your expressways, down to the lowest level which are your residential lanes.

You are constructing an hierarchical graph (not a tree since there is not one root).

P = point -, /, |, \ = distance between points (what you are calculating)

    P ---- P

   /|\    /|\

  P-P-P  P-P-P

 /|\

P-P-P
(Hard to show in ASCII art, but there can be connections between all the points in a group, so the one all the way to the right will connect to the one all the way to the left)

Next, when you need the distance, you sum your node connections.

I am sure there are many different data structures you could use generated by this approach, but it is hard to know what to recommend without more detail.