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)

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.