0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Please name a few of those you found hard to understand, with a unique identification of the main resources you used to understand each. Do you insist on best solution or are you willing to settle for acceptable? $\endgroup$
    – greybeard
    Feb 19, 2020 at 20:01
  • $\begingroup$ For example Branch-and-Cut and Branch-and-Bound were hard andi would like to get a best solution. $\endgroup$
    – saltea
    Feb 19, 2020 at 20:10
  • $\begingroup$ If you want a "best solution" and an easy to understand one, you probably just want to consider all possible paths (all possible permutations of your n nodes). This probably won't solve instances over n=11 or 12 nodes, mind you. $\endgroup$
    – JimN
    Feb 20, 2020 at 8:17
  • 1
    $\begingroup$ oof, thats unlucky because i need an algorithm for 16 nodes ._. maybe do you know an easy acceptable solution algorithm expect the ones i mentioned? $\endgroup$
    – saltea
    Feb 20, 2020 at 12:10
  • 2
    $\begingroup$ The $O(2^n)$ dynamic programming is quite simple and probably fast enough for 16 nodes. It is documented in en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm $\endgroup$
    – Laakeri
    Feb 20, 2020 at 15:44

3 Answers 3

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ But the OP seems to want an exact algorithm based on the comments. $\endgroup$
    – Juho
    Feb 21, 2020 at 5:23
  • $\begingroup$ Good luck with that. Does he want it in polynomial time as well? $\endgroup$
    – gnasher729
    Jul 20, 2020 at 7:11
  • $\begingroup$ @gnasher729 Sorry I had missed your comment earlier. Notice that there's only at most 16 nodes. $\endgroup$
    – Juho
    Jul 15, 2021 at 11:22
  • $\begingroup$ Why do you say extremely hard ? The problem statement is easy, a brute force solution is easy. Even a solution by simulated annealing is easy. $\endgroup$
    – user16034
    Apr 12, 2022 at 12:31
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)
$\endgroup$
5
  • $\begingroup$ There are ways to consider permutations that differ in one swap of adjacent elements, only, e.g. (Steinhaus–)Johnson–Trotter(–Even): The cost for a tour head→a→b→tail can be updated to the next tour head→b→a→tail by subtracting the former arrows and adding the new - independent of tour length. $\endgroup$
    – greybeard
    Apr 12, 2022 at 12:51
  • $\begingroup$ @greybeard: right. I gave the most "obvious" approach. $\endgroup$
    – user16034
    Apr 12, 2022 at 12:56
  • $\begingroup$ To make this likely much faster, sort the cities so that city 2 is closest to city 1, c3 closest to c2 etc. And stop when a tour so far is longer than the shortest tour found. $\endgroup$
    – gnasher729
    Sep 10, 2022 at 11:54
  • $\begingroup$ @gnasher729: in the world of exponential algorithms, "much faster" means "that can handle marginally bigger problems". :-) $\endgroup$
    – user16034
    May 9 at 12:30
  • $\begingroup$ True. But if a van driver can go to at most 15 places in a day, “marginally bigger” may be all you need. $\endgroup$
    – gnasher729
    Sep 5 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.