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

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.

• You are asking if you can compute the hamming distance matrix between each pair of points in less than `O(n^2)`. The matrix will `n` rows and `n` columns. You have to fill half the entries in the matrix. The best you can do is`n ^ 2 / 2 - n`, which is `O(n^2)`. Oct 12, 2017 at 13:29
• @BobDalgleish I know that I can not calculate the distance between every pair of points, because that would be O(n²). I'm asking for a heuristic that produces a lower distance for the entire roundtrip than just randomly choosing points, but with a time complexity of less than O(n²). Oct 12, 2017 at 14:43
• Preferably better than randomly choosing two points and swapping them if it improves the total distance. (which would be one approach that is O(1), but maybe not really desirable) Oct 12, 2017 at 14:45
• What algorithms have you found, especially in academic journals? Also you haven't defined "too slow", as big-O complexity and real world speed are unrelated when looking at a single dataset size. There are algorithms out there that can process datasets of several millions of points in "reasonable" timeframes, but you haven't defined what reasonable is. Oct 12, 2017 at 15:27
• @whatsisname: I understand that I was very vague. In the end all I can do is to try different ways to handle the data and analyze the result. But I can't do that if I don't find any way to finish the computation in let's say a few hours at max. Think of the dataset as arrays of 32bit integers on a regular x86_64 CPU (with 4-32 cores). Oct 12, 2017 at 16:45

When dealing with an O(n2) 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(n2) 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.

• Hm. Thanks. Dividing it into smaller sets and then using a more complex algorithm on them might be a good idea. Because the maximum distance between two data points is limited to 6, I can probably find a good way to divide the data set and stitch it back together in the end. Maybe I don't even need more than one hierarchy. Oct 12, 2017 at 16:41
• Not only is it "might be a good idea", I'd venture to say that is a prerequisite for any idea if you want to turn one of the n's in 'n * n' to 'n * log(n)'
– Dunk
Oct 12, 2017 at 18:12