# When does the nearest neighbor heuristic fail for the Traveling Salesperson?

Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem?

I was trying to construct a specific example of this for my friends and was failing.

• Please give (an outline of) the algorithm you are referring to. Also, please include your attempts. – Raphael Aug 15 '13 at 10:21

a----b----c
|    |    |
d----e----f


Say length of a-b is $2$ and length of a-d is $1$. The optimal route is a-b-c-f-e-d-a, $10$ units long. Starting at a, NN would produce a-d-e-b-c-f-a which is $7 + \sqrt{17} > 11$ units long.

There is actually a four node example, a rhombus

  A
/|\
B-+-C
\|/
D


Say length of B-C is $10$, length of A-D is $24$ and thus length of A-B is $13$. The optimal route is A-B-D-C-A, $52$ units long. NN would produce the path A-B-C-D-A, $60$ units long.

• Very interesting, do you think it's possible to generalize this down to less than 6 nodes? – dylan Aug 29 '13 at 19:20
• Apparently it is. I'm not sure whether this can be called generalizing though... – Karolis Juodelė Aug 30 '13 at 18:01

The following answer is to give an intuition of how a situation can look that fails. Karolis Juodelė's answer is much better than this, but I find the following example to give a nice intuition.

Let's say that we look for shortest TSP path, and not cycle, with predefined starting vertex, consider the graph below with X being the starting vertex, one dash means distance one, and two edges means distance two:

O--X-O-O-O-O

Going left immediately, and then all the way to the right gives a cost of 8, whereas going NN, i.e., right first, gives cost 9.

• The answer is a too weak. It's as if the flaw of NN was a random starting point. – Karolis Juodelė Aug 15 '13 at 7:13
• @KarolisJuodelė Yes, I know. I upvoted your answer, explained in the post that your answer is better, and also pointed out that this is for intuition purposes only. – Pål GD Aug 15 '13 at 10:17