1
$\begingroup$

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.

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

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.

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

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.

$\endgroup$
  • $\begingroup$ The answer is a too weak. It's as if the flaw of NN was a random starting point. $\endgroup$ – Karolis Juodelė Aug 15 '13 at 7:13
  • $\begingroup$ @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. $\endgroup$ – Pål GD Aug 15 '13 at 10:17

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.