# 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? Feb 19 '20 at 20:01
• For example Branch-and-Cut and Branch-and-Bound were hard andi would like to get a best solution. Feb 19 '20 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 '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? Feb 20 '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 Feb 20 '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.

• But the OP seems to want an exact algorithm based on the comments.
– Juho
Feb 21 '20 at 5:23
• Good luck with that. Does he want it in polynomial time as well? Jul 20 '20 at 7:11
• @gnasher729 Sorry I had missed your comment earlier. Notice that there's only at most 16 nodes.
– Juho
Jul 15 at 11:22