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$
7
  • $\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 '20 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 '20 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 '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 '20 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 '20 at 15:44
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$
3
  • $\begingroup$ But the OP seems to want an exact algorithm based on the comments. $\endgroup$
    – Juho
    Feb 21 '20 at 5:23
  • $\begingroup$ Good luck with that. Does he want it in polynomial time as well? $\endgroup$
    – gnasher729
    Jul 20 '20 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 at 11:22

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.