# Travelling Salesman Problem Easy Algorithms

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?

• 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? – greybeard Feb 19 at 20:01
• For example Branch-and-Cut and Branch-and-Bound were hard andi would like to get a best solution. – saltea Feb 19 at 20:10
• 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. – JimN Feb 20 at 8:17
• 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? – saltea Feb 20 at 12:10
• 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 – Laakeri Feb 20 at 15:44

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).