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?

  • $\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 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 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 at 8:17
  • $\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 at 12:10
  • 1
    $\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 at 15:44

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.

| cite | improve this answer | |
  • $\begingroup$ But the OP seems to want an exact algorithm based on the comments. $\endgroup$ – Juho Feb 21 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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