Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm looking for a easier algorithm to implement to solve the travelling salesman problem (in javascript). Unluckily all of the ones i found are really hard to understand/ to implement.
The ones i already have are the nearest/farthest-neighbour-algorithms. Do you guys have any other suggestions?
It is an extremely hard problem to solve. But some reasonable heuristics are easy to explain/code.
One is to start at a random vertex, each step move to the vertex that hasn't been visited yet that is closest. Rinse and repeat.
Another is to start with a minimal spanning tree of the graph, pick any vertex as starting point (root), and visit the vertices in preorder. If you are asked to visit a vertex that you already visited, just skip it for the next one in preorder. Think about it as walking along the "outside" of the tree, taking shortcuts to the next when asked to visit a vertex again. This works rather well if the distances have the triangular property (i.e., $c(u v) \le c(u x) + c(x v)$ for all vertices).
See if you can come up with another idea.
There’s a trivial algorithm running in n! . That would be good enough for n=12. N=16 would talk about 43,000 times longer - probably just outside what you’d call a solution. Here’s a method that should save you just enough time to solve for n=16:
Take a sub tour abcd. If the distance abcd is longer than the distance acbd then abcd cannot be part of an optimal tour (since swapping b and c creates a shorter tour). If both sub tours have the same length we can arbitrarily exchange b and c if b is later in the alphabet than c. So we accept exactly half of the subsequences in an attempt to find an optimal tour.
Now we pick any fixed city b as the second city. We don’t need to try different cities as the second city because we can rotate the tour. We then pick any a and c as the first and third city, picking their order so that a comes before c in the alphabet. There are 15 x 14 / 2 = 105 choices for these three cities.
Then we choose the fourth city d. But instead of 13 choices, the requirement that abcd is not longer than acbd removes on average half the choices, so 6.5 on average. For cities 15 and 16 there is only one choice.
Total choices for the order of all cities is 15! / 2^13 ≈ 160,000,000. You’ll need to implement this in an efficient way. For general n, it is (n-1)! / 2^(n-3).
You could improve this by choosing which sequences abcde are possible. B, c and d can be visited in six different orders, and only one can be optimal.
Brute-force is not that difficult. All you need to do is to generate all permutations of a vector (0, 1, ... n-1) and compute the length of the corresponding cycle.
To generate the permutations, consider the input vector, extract one element at a time and recurse on the remaining elements.
E.g.
Permute(0, 1, 2, 3) ->
0 + Permute(1, 2, 3),
1 + Permute(0, 2, 3),
2 + Permute(0, 1, 3),
3 + Permute(0, 1, 2)