Problema del commesso viaggiatore
Da Wikipedia, l'enciclopedia libera.
Il problema del commesso viaggiatore, o TSP (dall'inglese Traveling Salesman Problem) è un problema di teoria dei grafi, uno dei casi di studio tipici dell'informatica teorica e della teoria della complessità.
Indice |
[modifica] Formulazione del problema
Il nome nasce dalla sua più tipica rappresentazione: data una rete di città, connesse tramite delle strade, trovare il percorso di minore distanza che un commesso viaggiatore deve seguire per visitare tutte le città una e una sola volta.
Espresso nei termini della teoria dei grafi è così formulato: dato un grafo completo pesato, trovare il ciclo hamiltoniano con peso minore. La rete di città può essere rappresentata come un grafo in cui le città sono i nodi, le strade gli archi e le distanze i pesi sugli archi.
Può essere dimostrato che specificare o meno il ritorno alla città di partenza non cambia la complessità computazionale del problema.
Il problema è di considerevole importanza pratica, al di là delle ovvie applicazioni nella logistica e nei trasporti. Un esempio classico è la costruzione di circuiti stampati, nella pianificazione del percorso del trapano per creare i fori nella piastra. Nelle applicazioni di foratura o di rifinitura automatica eseguite da robot, le "città" sono pezzi da rifinire o fori (anche di varie dimensioni) da praticare, e il "costo di viaggio" include i tempi morti (ad esempio il tempo che il robot impiega, se necessario per cambiare la punta con cui lavora).
[modifica] Complessità computazionale
Non esistono algoritmi efficienti per la risoluzione del TSP, l'unico metodo di risoluzione è rappresentato dall'enumerazione totale, ovvero nell'elaborazione di tutti i possibili cammini sul grafo per la successiva scelta di quello migliore. Tuttavia, la complessità dell'operazione la rende impraticabile per grafi di dimensioni comuni nei problemi reali: in un grafo di n nodi, bisognerà calcolare, nel caso peggiore in cui ogni nodo è connesso con tutti gli altri, n! (n fattoriale) possibili cammini, il che implica una complessità esponenziale (in base all'approssimazione di Stirling).
Una rete di mille nodi, molto più comune di quanto si possa pensare, comincerebbe già a creare seri problemi computazionali.
[modifica] NP-completezza
È stato dimostrato che TSP è un problema NP-difficile (più precisamente, è NP-completo per la classe di complessità FPNP; v. problema di funzione), e la versione decisionale del problema ("dati i pesi e un numero x, decidere se ci sia una soluzione migliore di x") è NP-completa.
Il problema rimane NP-difficile anche in molte sue versioni ridotte, come nel caso in cui le città siano in un piano con distanze euclidee. Inoltre, omettere la condizione di visitare una città "una e una sola volta" non rimuove la NP-difficoltà, poiché si nota facilmente che nel caso piano un cammino ottimale visiterebbe comunque le città una volta sola.
Anche il problema del commesso viaggiatore per collo di bottiglia è NP-difficile.
[modifica] Algoritmi
Le strategie tradizionali di soluzione per i problemi NP-difficili sono:
- progettare algoritmi per trovare la soluzione esatta, ragionevolmente veloci solo per problemi con un numero di città relativamente basso
- progettare algoritmi euristici, cioè algoritmi che producono soluzioni probabilmente buone, ma impossibili da provare essere ottimali
- trovare un caso specifico del problema (sottoproblema) per il quale sia possibile o una soluzione esatta o un'euristica migliore.
Per condurre test sugli algoritmi TSP è stata sviluppata la libreria TSPLIB, che contiene istanze d'esempio del problema TSP e relative varianti (v. nella sezione voci correlate). Molti di questi esempi sono liste di città e schemi di circuiti stampati.
[modifica] Algoritmi esatti
- Algoritmi branch and bound che possono essere usati per problemi TSP con 50-60 città.
- Algoritmi che procedono per raffinamenti successivi usando tecniche derivate dalla programmazione lineare, adatti per problemi fino a 120-200 città.
- Implementazioni recenti di branch and bound e branch and cut basati sulla programmazione lineare, adatti per problemi contenenti fino a 5.000 città. Questo approccio è stato seguito anche per risolvere situazioni con 33.810 città.
Nel 2001 è stata trovata la soluzione esatta a un problema di 15.112 città contenuto in TSPLIB , usando il metodo cutting plane, basato sulla programmazione dinamica e originariamente proposto nel 1954 da George Dantzig, Ray Fulkerson e Selmer Johnson.
Il calcolo fu eseguito da una rete di 110 processori della Rice University e della Princeton University. Il tempo di elaborazione totale fu equivalente a 22,6 anni su un singolo processore Alpha a 500 MHz. Nel maggio 2004 fu risolto il TSP per tutte le 24.978 città della Svezia: risultò un percorso di circa 72.500 chilometri che fu provato essere ottimale.
Nel marzo 2005, il TSP riguardante la visita di tutti i 33.810 punti in una scheda di circuito fu risolto usando CONCORDE: fu trovato un percorso di 66.048.945 unità, e provato che non poteva esisterne uno migliore. L'esecuzione richiese approssimativamente 15,7 anni CPU.
[modifica] Euristiche
Ad oggi sono stati progettati vari algoritmi approssimati, che hanno un'"alta" probabilità di produrre una "buona" soluzione "velocemente". I metodi moderni possono trovare soluzioni in tempo ragionevolmente accettabile per problemi estremamente grandi (milioni di città), con un'alta probabilità che siano differenti del 2-3% dalla soluzione esatta.
Esistono vari tipologie d'euristiche.
[modifica] Euristiche costruttive
- L'algoritmo nearest neighbor, che normalmente è abbastanza vicino alla soluzione ottima, e non impiega troppo tempo. Sfortunatamente, è possibile provare la bontà della soluzione solo in casi particolari del TSP. Nel caso generale, esiste sempre un esempio in cui il nearest neighbor produce una soluzione pessima.
[modifica] Raffinamenti successivi
- Euristica Pairwise exchange, o euristica di Lin e Kernighan.
- Euristica k-opt
[modifica] Raffinamenti casuali
- Algoritmi ottimizzati e basati su processi markoviani, utilizzano sottoprocedure euristiche a ricerca locale e riescono a trovare una soluzione estremamente vicina a quella ottimale per problemi con 700-800 città.
TSP è un termine di paragone per molte euristiche generiche progettate per problemi di ottimizzazione combinatoria: algoritmi genetici, simulated annealing, tabu search, reti neurali, ant system.
[modifica] Casi speciali
[modifica] Locazioni particolari
- Una caso particolare di soluzione banale si ha quando le città sono disposte sul perimetro di un poligono convesso.
- Un buon esercizio sugli algoritmi combinatori riguarda la soluzione del TSP per un insieme di città situate lungo due cerchi concentrici.
[modifica] Disuguaglianza triangolare e algoritmo di Christofides
Una naturale restrizione del TSP è la disuguaglianza triangolare. Cioè, per tre città qualsiasi A, B e C, la distanza tra A e C deve essere al massimo la distanza da A a B più la distanza da B a C. Molti casi reali di problemi TSP soddisfano questo vincolo.
In questo caso, si ha un algoritmo di approssimazione con fattore di approssimazione costante (grazie a Christofides, 1975), che produce sempre un percorso lungo al massimo 1,5 volte il percorso ottimo. Nel prossimo paragrafo illustreremo un algoritmo semplificato che trova un percorso lungo al massimo il doppio della soluzione ottima.
La lunghezza dell'albero di copertura minimo della rete è un limite inferiore naturale per la lunghezza del percorso ottimale. Nel TSP con disuguaglianza triangolare è possibile determinare un limite superiore in termini dell'albero di copertura minimo, e progettare un algoritmo che abbia un limite superiore dimostrabile sulla lunghezza della soluzione.
Il primo e più semplice algoritmo è:
- costruire l'albero di copertura minimo
- duplicare tutti i suoi archi. Questo significa che, nel caso esista un arco dal vertice u al vertice v, si aggiunge un secondo arco da u a v. Questo produce un grafo euleriano.
- trovare al suo interno un circuito euleriano. Ovviamente, la sua lunghezza è il doppio della lunghezza dell'albero.
- convertire il circuito euleriano in un ciclo hamiltoniano nel seguente modo: percorrendo il ciclo euleriano, ogni volta che si sta per toccare un vertice già visitato, saltarlo e cercare di raggiungere il prossimo (sempre seguendo il cammino euleriano).
É facile dimostrare che l'ultimo passo funziona. Inoltre, grazie alla disuguaglianza triangolare, ogni volta che si salta un vertice al passo 4 si ha di fatto una scorciatoia, garantendo che la lunghezza del ciclo non aumenti. Questo ci permette di avere una soluzione che sicuramente non è più lunga del doppio di quella ottima.
L'algoritmo di Christofides segue un approccio simile, ma combina l'albero di copertura minimo con una soluzione di un altro problema, il minimum-weight perfect matching. Questo garantisce una soluzione che è al massimo 1,5 volte quella ottimale. È dal 1975 che il tentativo di ridurre la costante 1,5 è un problema aperto.
[modifica] TSP euclideo
TSP euclideo, o TSP planare, è il caso particolare in cui si usano le ordinarie distanze euclidee. Nonostante il problema rimanga NP-difficile, molte euristiche lavorano meglio.
Il TSP euclideo è un caso particolare del TSP con disuguaglianza triangolare, poiché le distanze nel piano obbediscono a tale vincolo; ciò nonostante sembra essere più semplice del caso generale con disuguaglianza triangolare. Per esempio, l'albero di copertura minimo del grafo associato a un caso di TSP euclideo è un albero di copertura minimo euclideo e come tale può essere calcolato in tempo O(nlogn) per n punti . Questo permette all'algoritmo illustrato in precedenza di computare più velocemente.
In generale, per ogni c > 0 esiste un algoritmo polinomiale che individua, su qualsiasi grafo, un percorso lungo al massimo (1 + c) volte quello ottimale (Arora, 1997); questo è detto schema d'apposimazione polinomiale. Questo algoritmo è però troppo lento nella pratica per poter essere utilizzato; al suo posto vengono usate euristiche che danno garanzie più deboli ma che lavorano meglio nei casi di TSP euclideo piuttosto che in casi generali.
[modifica] TSP asimmetrico
Il più delle volte si ha che la distanza tra due nodi della rete TSP è la stessa in entrambe le direzioni. Il caso particolare in cui la distanza da A a B non sia uguale alla distanza da B ad A è chiamato TSP asimmetrico. Un esempio pratico può essere la ricerca di un percorso nelle strade di una città, in cui sono presenti sensi unici.
[modifica] Voci correlate
[modifica] Collegamenti esterni
- (EN) TSPLIB
- (EN) Pagina dedicata al TSP
- Rete di Kohonen applicata al problema del commesso viaggiatore (in 3 dimensioni)
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
