Problema del commesso viaggiatore
Il Traveling Salesman Problem (spesso chiamato TSP) è un classico problema algoritmico nel campo dell'informatica e della ricerca operativa. È focalizzato sull'ottimizzazione. In questo contesto, soluzione migliore significa spesso una soluzione più economica, più breve o più veloce. TSP è un problema matematico. Si esprime più facilmente come un grafico che descrive la posizione di un insieme di nodi.
Il problema dei venditori ambulanti fu definito nel 1800 dal matematico irlandese W. R. Hamilton e dal matematico britannico Thomas Kirkman. L'Icosian Game di Hamilton era un puzzle ricreativo basato sulla ricerca di un ciclo hamiltoniano. La forma generale del TSP sembra essere stata studiata per la prima volta dai matematici negli anni Trenta a Vienna e ad Harvard, in particolare da Karl Menger. Menger definisce il problema, considera l'ovvio algoritmo della forza bruta e osserva la non ottimalità del vicino euristico:
Si indica per problema di messaggero (poiché in pratica questa questione dovrebbe essere risolta da ogni postino, comunque anche da molti viaggiatori) il compito di trovare, per molti punti di cui si conoscono le distanze a coppie, il percorso più breve per collegare i punti. Naturalmente, questo problema è risolvibile con molte prove. Non sono note regole che spingano il numero di prove al di sotto del numero di permutazioni dei punti indicati. La regola secondo cui si deve andare prima dal punto di partenza al punto più vicino, poi al punto più vicino a questo, ecc. in generale non dà il percorso più breve.
Hassler Whitney alla Princeton University ha introdotto subito dopo il problema dei venditori ambulanti.
Un venditore vuole visitare tutte le città, A, B, C e D. Qual è il modo migliore per farlo (biglietti aerei più economici, e tempo di viaggio minimo)?
Percorso ottimale di un venditore che visita le 15 città più grandi della Germania. Il percorso indicato è il più breve tra i 43.589.145.600 possibili.
William Rowan Hamilton
Dichiarare il problema
Il Travelling Salesman Problem descrive un venditore che deve viaggiare tra N città. L'ordine in cui lo fa è qualcosa che non gli interessa, a patto che venga a trovarlo una volta durante il suo viaggio e finisca dove si trovava all'inizio. Ogni città è collegata ad altre vicine da città, o nodi, da aerei, o da strade o ferrovie. Ognuno di questi collegamenti tra le città ha uno o più pesi (o il costo). Il costo descrive quanto sia "difficile" attraversare questo bordo sul grafico, e può essere dato, ad esempio, dal costo di un biglietto aereo o di un biglietto ferroviario, o forse dalla lunghezza del bordo, o dal tempo necessario per completare l'attraversamento. Il venditore vuole mantenere il più basso possibile sia il costo del viaggio, sia la distanza percorsa.
Il Traveling Salesman Problem è tipico di una grande classe di problemi di ottimizzazione "difficili" che hanno incuriosito per anni matematici e informatici. La cosa più importante è che ha applicazioni nella scienza e nell'ingegneria. Ad esempio, nella produzione di un circuito stampato, è importante determinare l'ordine migliore in cui un laser eseguirà migliaia di fori. Una soluzione efficiente a questo problema riduce i costi di produzione per il produttore.
Difficoltà
In generale, il problema dei venditori ambulanti è difficile da risolvere. Se c'è un modo per suddividere questo problema in problemi di componenti più piccoli, i componenti saranno complessi almeno quanto quelli originali. Questo è ciò che gli informatici chiamano i problemi NP-hard.
Molte persone hanno studiato questo problema. La soluzione più semplice (e più costosa) è quella di provare semplicemente tutte le possibilità. Il problema è che per N città si hanno (N-1) possibilità fattoriali. Questo significa che per sole 10 città ci sono oltre 180 mila combinazioni da provare (poiché la città di partenza è definita, ci possono essere permutazioni sulle altre nove). Ne contiamo solo la metà, poiché ogni percorso ha un percorso uguale al contrario con la stessa lunghezza o lo stesso costo. 9! / 2 = 181 440
- Si possono trovare soluzioni esatte al problema, utilizzando algoritmi ramificati e legati. Questo è attualmente possibile per un massimo di 85.900 città.
- Gli approcci euristici utilizzano una serie di regole guida per la selezione del nodo successivo. Ma poiché l'euristica si traduce in approssimazioni, non sempre fornisce la soluzione ottimale, anche se l'euristica ammissibile di alta qualità può trovare una soluzione utile in una frazione del tempo necessario per una piena forza bruta del problema. Un esempio di euristica per un nodo sarebbe la somma di quanti nodi non visitati sono "vicini" ad un nodo connesso. Questo potrebbe incoraggiare il venditore a visitare un gruppo di nodi vicini raggruppati insieme prima di passare ad un altro cluster naturale nel grafico. Vedi algoritmi di Monte Carlo e algoritmi di Las Vegas
Domande e risposte
D: Che cos'è il Problema del commesso viaggiatore?
R: Il Traveling Salesman Problem (TSP) è un classico problema algoritmico nel campo dell'informatica e della ricerca operativa. Si concentra sull'ottimizzazione, con soluzioni migliori che spesso significano soluzioni più economiche, più brevi o più veloci.
D: Come si esprime il TSP?
R: Il TSP si esprime più facilmente come un grafico che descrive le posizioni di un insieme di nodi.
D: Chi ha definito per primo il TSP?
R: Il problema del commesso viaggiatore è stato definito nel 1800 dal matematico irlandese W. R. Hamilton e dal matematico britannico Thomas Kirkman.
D: Chi lo ha studiato ulteriormente negli anni '30?
R: Negli anni '30, i matematici Karl Menger a Vienna e Harvard lo studiarono ulteriormente.
D: Cosa introdusse Hassler Whitney poco dopo?
R: Hassler Whitney dell'Università di Princeton introdusse il nome di "problema del commesso viaggiatore" subito dopo la sua definizione.
D: Cosa significa "soluzione migliore" in questo contesto?
R: In questo contesto, una soluzione migliore spesso significa una soluzione più economica, più breve o più veloce.
D: Quale algoritmo era considerato ovvio da Menger quando studiava il TSP?
R:Menger considerò ovvio un algoritmo di forza bruta quando studiò il TSP e osservò che l'utilizzo dell'euristica del vicino più prossimo non sempre produce risultati ottimali.
