La complessità dell'algoritmo del Commesso Viaggiatore euristica V-opt

Question

Il paragrafo su algoritmi euristici TSP V-opt in questo sito menziona un molto efficace algoritmo a causa di Lin-Kernigham-Johnson. Quella pagina dice:

Per molti anni Lin-Kernighan-Johnson aveva identificato soluzioni ottimali per tutte FST dove una soluzione ottimale era noto e aveva identificato le migliori soluzioni note per tutti gli altri FST su cui era stato provato il metodo.

Impressionante, quindi qual è la complessità di questo algoritmo? Ha l'algoritmo spesso lavorare più velocemente di quanto previsto sulla base della complessità teorica (se sì, quanto)? È che l'algoritmo utilizzato più spesso in un software che risolve il TSP?

Answer 1

Secondo il originale 1973 di carta , il Lin- Kernighan algoritmo

... produce risultati ottimali con alta frequenza, in esecuzione volte che si sviluppi circa $ n ^ 2 $.

Il iterati Lin-Kernighan variante , proposto da Johnson nel 1990, offre una osservato miglioramento a $ O (n ^ {1.25}) $; un trattamento sperimentale di questo e molti altri euristiche di ottimizzazione TSP locali può essere trovato qui .