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

Question

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.

Answer 1

Consider a ladder

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.

Answer 2

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.