Il Problema
del
Commesso
Viaggiatore
Traveling Salesman’s Problem (TSP)
• Un commesso viaggiatore deve visitare un certo
numero di città
• Conosce la distanza da una città all’altra
• Vuole determinare il percorso più breve che gli
permetta di partire da casa sua e di farvi ritorno
dopo aver visitato ogni città una sola volta.
• Come può fare?
Caratteristiche
• TSP e’ uno dei problemi matematici piu’ studiati
in informatica
• Appartiene alla classe dei problemi difficili (NPhard)
• La prima formulazione risale al 1857 e al gioco
icosian inventato dal matematico William
Hamilton
Forma generale TSP
• La formulazione generale considera forme
geometrie qualsiasi e distanze tra le citta’
• Venne introdotta tra gli anni ‘40 e ’50
• Nel corso degli anni ha trovato numerose
istanziazioni interessanti:
– logistica e trasporti
– costruzione di circuiti stampati (pianificazione del
percorso del trapano)
– protocolli di routing
– DNA sequencing
– ...
Modelliamo e Studiamo
TSP
Le citta’... (nodi)
AOSTA
MILANO
TORINO
GENOVA
Le distanze... (archi pesati)
AOSTA
186
115
142
TORINO
MILANO
246
140
169
GENOVA
Modello
A
Nodi=citta
10
B
16
8
Archi=strade
5
7
C
GRAFO!
6
D
Pesi=distanze
Percorso in un grafo
A
10
B
16
8
5
7
C
6
D
A, D, B rappresenta un percorso da A a B con peso 16+5
TSP come problema sui grafi
Dato un grafo G con N nodi e archi pesati
trovare un percorso che sia:
– un ciclo hamiltoniano (tour)
• inizia e finisce nello stesso node
• passa da tutti i nodi una sola volta
– con peso totale (somma dei pesi) minimo
Esempio
A
5
C
B
2
4
4
2
3
D
...
Ciclo hamiltoniano
A
5
B
2
4
4
6
3
C
A,B,C,D,A: 2+4+3+2=11
Con questo percorso “visito” tutti i nodi!
D
Percorso non hamiltoniano
A
5
C
B
2
4
4
6
3
D
Percorso non hamiltoniano
A
5
C
B
2
4
4
6
3
D
Come si risolve TSP?
Soluzioni a TSP
• Trovare manualmente una soluzione esatta
del problema TSP (cioe’ calcolare un tour
minimo) e’ molto difficile
• La difficolta’ e’ legata al numero di possibili
percorsi che occorre esplorare per calcolare
quello minimo
Per capire la difficolta’ del problema
... facciamo due conti
• Negli USA ci sono 49 stati continentali + un
distretto
• Supponiamo che Obama programmi di fare
un solo comizio in ogni stato
Quanti percorsi devo considerare per
calcolare il migliore?
• Partendo da Washington, Obama ha 49
possibili scelte per la prima tappa
• Fissata la prima tappa, rimangono 48 scelte
per la seconda tappa
• Fissata la seconda tappa, rimangono 47
scelte per la terza tappa
• ...
Il numero di possibili percorsi tra i quali
trovare il piu’ breve e’
49! = 49 * 48 * ... * 3 * 2 * 1
... nell’ordine di 1062 cioe’ maggiore del
numero di atomi di cui è composta la Terra
Metodi di risoluzione per TSP
Come si puo’ fare?
• Per poter affrontare questo tipo di problemi
dobbiamo necessariamente programmare delle
soluzioni su uno o piu’ elaboratori
• Per calcolare le soluzioni usiamo quindi dei
programmi che rappresentano i passi che
l’elaboratore deve eseguire (algoritmo)
• Lo sviluppo di algoritmi per risolvere problemi
come TSP e’ uno degli obiettivi principali
dell’Informatica
Algoritmo
• Algoritmo: sequenza di istruzioni che deve
eseguire l’elaboratore
• Si scrivono usando i linguaggi di programmazione
• Esempi di istruzioni:
–
-
memorizza ... in ...
confronta ... con ...
per ogni valore in ... esegui....
ripeti ... fino a che ... diventa vera
Algoritmi per TSP
Algoritmi esatti
Applicabili solo a problemi con un numero di città
relativamente basso
Algoritmi euristici
Producono soluzioni probabilmente buone, ma
impossibili da provare essere ottimali
Un algoritmo esatto
Generate & Test
Per ogni permutazione P di [1...N]
– calcola la somma S dei pesi sugli archi del ciclo
indotto da P
– se S e’ minore dei precedenti calcolati
memorizza il cammino in Min
Alla fine Min contiene un ciclo “minimo”
Raffinamento
MinD=MAX_INT
MinP=nullo
Per ogni permutazione P=[i1,....,iN] di [1...N]
– S=dist(i1,i2)+....+dist(iN,i1)
– se S < MinD allora
MinP=P
MinD=S
Alla fine MinP contiene tour minimo
Problema
• Abbiamo visto che per TSP con molte citta’
il numero di possibili percorsi puo’ essere
astronomico!
• Provate a pensare e scrivere un algoritmo
euristico... quello che probabilmente usate
nei vostri viaggi...
Un Algoritmo Euristico
Nearest Neighbour (NN)
• Partendo da un nodo iniziale scelto a piacere, ci
muoviamo sempre verso la citta’ piu’ vicina non
ancora visitata
• L’algoritmo termina quando abbiamo visitato tutte
le citta’
Esempio Nearest Neighbour
A
5
C
B
2
4
4
2
3
D
...
Algoritmo Nearest Neighbour
• I = nodo iniziale
• Fino a che ho ancora nodi da visitare
– Sia J il nodo non ancora visitato piu’ vicino ad I
• marco J come visitato
– proseguo la ricerca
• La sequenza dei nodi marcati rappresenta il
ciclo hamiltoniano
Osservazioni su NN
• E’ un algoritmo “intuitivo”
• L’algoritmo Nearest Neighbour non da’ sempre la
soluzione ottimale (cercare di ottenere un
vantaggio immediato non sempre e’ la scelta
migliore...)
• Tuttavia e’ una buona approssimazione
dell’algoritmo ottimale
Esistono molti altri modi
• Algoritmi basati su programmazione intera
lineare (LIP)
– si codifica il problema come un insieme di
disequazioni ed una funzione costo
– si usano euristiche per problemi di LIP
• Algoritmi genetici
• ...
Sistemi per risolvere TSP
• Concorde: http://www.tsp.gatech.edu/
• Nel 2004 ha calcolato un tour minimo attraverso
24.978 citta’ in Svezia (72.500 km)
Prima della pratica ... un po’
di esercizi di riepilogo...
Quanti e quali cicli hamiltoniani contiene il
seguente grafo?
A
5
C
2
B
6
4
3
D
Applicate l’algoritmo Nearest Neighbour al
seguente grafo a partire dal nodo A
A
B
9
4
2
C
6
3
5
D
Applicate l’algoritmo Nearest Neighbour al
seguente grafo a partire dal nodo D
A
B
9
4
2
C
6
3
5
D
Aggiungete i pesi agli archi in modo che la
soluzione calcolata con l’algoritmo NN a partire
dal nodo A non sia quella ottimale
A
C
B
D
Provate a risolvere l’icosian game...
Il tour deve passare una sola volta da ogni nodo
E’ un caso molto particolare di TSP!