Il Travelling Salesman Problem è un classico rompicapo
dell’informatica e della matematica: un viaggiatore deve visitare
tutte le città una sola volta e tornare al punto di partenza,
cercando il percorso più breve possibile.
Può sembrare semplice, ma diventa complicatissimo man mano che il numero
di città cresce. Infatti le possibili combinazioni crescono a dismisura
e nessun computer riesce a provarle tutte velocemente.
Per questo motivo si usano due approcci:
algoritmi esatti (che garantiscono la soluzione migliore,
ma richiedono molto tempo) e algoritmi approssimati o metaeuristici
(che trovano buone soluzioni in poco tempo, ma non sempre perfette).