C'è una buona applicazione mobile che risolve il problema del commesso viaggiatore dato un elenco di città?

Computare il percorso più breve da un nodo di una rete ad un altro nodo di una rete è un problema relativamente semplice. Questo non è il problema del commesso viaggiatore.

Nel problema del commesso viaggiatore, devi disegnare un percorso che passa attraverso più nodi intermedi. Tuttavia, si può passare attraverso i nodi intermedi in qualsiasi ordine. Quale ordine fornisca il percorso più breve non è ovvio.

Considera un blocco di carta segnato in quadrati da 1/4″. Supponiamo che ogni quadrato sia di fatto un quadrato perfetto. Prendete tutte le intersezioni delle linee come vostri "nodi", e le linee tra di loro come vostri "collegamenti". Supponiamo di dover tracciare un percorso che attraversi ogni singolo nodo della pagina e torni al nodo di partenza. È ovvio che ci sono un numero enorme di modi per farlo, e che tutti i modi hanno esattamente la stessa lunghezza totale per il percorso fatto.

Supponiamo che si cambi il problema di una piccola quantità, in modo che alcuni dei link siano ancora lunghi 1/4″, e alcuni siano più lunghi dell'1%. Ora è chiaro che con un piccolo cambiamento al problema alcune soluzioni, in particolare le soluzioni che evitano i link leggermente più lunghi, sono migliori di altre soluzioni.

Fate un altro piccolissimo cambiamento al problema, in modo che i link che erano stati l'1% più lunghi siano ora l'1% più corti. Poiché avete cambiato il problema solo di una piccola quantità, il valore di qualsiasi soluzione non è molto diverso. Tuttavia, se aveste bisogno di trovare la soluzione migliore, è chiaro che la natura della soluzione ottimale potrebbe essere cambiata radicalmente, almeno nel senso che state prendendo un percorso completamente diverso attraverso la rete.

Una caratteristica dei problemi NP-hard è che un cambiamento molto piccolo nel problema può risultare in un cambiamento molto grande nella forma della soluzione ottimale. Un'altra caratteristica è che ci sono tipicamente diverse soluzioni che sono molto vicine in termini di quanto sono "ottimali", ma molto diverse in termini di forma della soluzione.