1
$\begingroup$

I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first.

For example, should I start with one node; calculate the distance between this node and the other nodes; and sort the other nodes by this distance? Then, I will insert the closest node (to the first node) first. Will this be faster than randomly choosing nodes to insert?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I'm a little confused: sure, it can be faster if you insert a random node as the next node, but then you are not following the nearest insertion heuristic anymore. $\endgroup$ – Juho Dec 1 '18 at 19:57
  • $\begingroup$ @Juho Well, I didn't know a name for this "new technique" but it doesn't matter that I'm not following the insertion heuristic if this variation is faster, so do u know if it is? $\endgroup$ – Goldname Dec 1 '18 at 20:07
0
$\begingroup$

Inserting a random point instead of a nearest point can be faster, but then you are not following the nearest insertion heuristic anymore. The key is to realize that the point is not the runtime efficiency of the algorithm, but rather the quality of the solution obtained. Indeed, remember that we are dealing with an NP-hard problem.

The nearest neighbor heuristic should return considerably shorter tours than random insertion. In fact, we can prove that the ratio of the nearest insertion heuristic's solution to the minimum tour length is bounded by $O(\log n)$, where $n$ is the number of cities. No such guarantee exists for the random insertion that you propose, i.e., such a heuristic can return very long tours.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How about this instead: I insert the node closest to one particular node. I build the graph around one node? Is that a good solution? $\endgroup$ – Goldname Dec 1 '18 at 21:13
  • $\begingroup$ @Goldname What are you actually trying to achieve? Do you care about the length of the tour at all? How fast should the algorithm be? $\endgroup$ – Juho Dec 1 '18 at 21:30
  • $\begingroup$ I'm looking for an accurate and fast running estimation of the tour, but I want it to be easy to code as well. $\endgroup$ – Goldname Dec 1 '18 at 23:22
  • $\begingroup$ @Goldname OK. Google for 2-opt as well. $\endgroup$ – Juho Dec 1 '18 at 23:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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