Quando parte l'euristica vicino più prossimo di rifiuto per la Traveling venditore?

Question

Si può fornire un esempio di fallimento NN algoritmo di Euclide sul problema del commesso viaggiatore?

I stava cercando di costruire un esempio specifico di questo per i miei amici e stava venendo a mancare.

Answer 1

Si consideri una scala

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

lunghezza Say di a-b è di $ 2 $ e la lunghezza del a-d è $ 1 $. Il percorso ottimale è a-b-c-f-e-d-a, lungo $ 10 $ unità. A partire da a, NN produrrebbe a-d-e-b-c-f-a che è di $ 7 + \ sqrt {17}> di 11 $ unità.

V'è in realtà un esempio quattro nodi, un rombo

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

lunghezza Say di B-C è di $ 10 $, la lunghezza di A-D è di $ $ 24, e quindi la lunghezza di A-B è $ 13 $. Il percorso ottimale è A-B-D-C-A, lungo $ 52 $ unità. NN dovrebbe produrre il A-B-C-D-A percorso, lungo $ 60 $ unità.

Answer 2

La risposta seguente è quello di dare un'intuizione di come una situazione può guardare questo fallisce. La risposta di Karolis Juodele è molto meglio di questo, ma ho trovato il seguente esempio per dare una bella intuizione.

diciamo Let che cerchiamo percorso più breve TSP, e non ciclo, con vertice iniziale predefinito, si consideri il grafico sottostante con X essendo il vertice di partenza, un trattino mezzi distanza uno e due bordi mezzi distanza due:

O - X-O-O-O-O

andando a sinistra subito, e poi tutta la strada sulla destra dà un costo di 8, mentre andare NN, vale a dire, prima a destra, dà costi 9.