Il Problema
del
Commesso
Viaggiatore
Avete mai pianificato un viaggio
in piu’ tappe?
Quale metodo avete usato per
minimizzare la distanza totale
percorsa?
Cartina alla mano non sembra cosi’
difficile...soprattutto per poche tappe
Mettetevi pero’ nei panni dello staff di
Obama e provate a pianificare le tappe
della campagna elettorale negli USA...
?
Definiamo meglio il problema
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 del problema
• TSP e’ uno dei problemi matematici piu’ studiati
in Informatica
• Appartiene alla classe dei problemi difficili (NPhard)
• La prima formulazione risale al 1857 e all’icosian
game inventato dal matematico William Hamilton
Icosian Game (1857)
Scopo: trovare un tour lungo gli spigoli di un dodecaedro
Icosian Game: Scacchiera
Il tour deve passare una sola volta da ogni nodo
E’ un caso molto particolare di TSP!
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
Quali informazioni ci servono?
Citta’= nodi
AOSTA
MILANO
TORINO
GENOVA
Distanze = archi pesati
AOSTA
186
115
142
TORINO
MILANO
246
140
169
GENOVA
Modello = Grafo
6
A
4
B
5
6
C 2
8
F
3
Archi=strade
4
D
7
E
9
6
Nodi=citta
2
G
Pesi=distanze
Percorso in grafo
6
A
4
B
5
6
C 2
4
D
7
8
F
3
E
9
6
2
G
A,C,D,E,G,B = percorso con costo 4+2+2+2=12
Ciclo = Percorso chiuso
6
A
4
B
5
6
C 2
4
D
7
8
F
3
E
9
6
2
G
A,C,D,E,B,A = ciclo con costo 4+2+4+3+6
Ciclo hamiltoniano (Tour)
6
A
4
B
5
6
C 2
4
D
7
8
F
3
E
9
6
2
G
E’ un ciclo che visita TUTTI i nodi UNA SOLA volta
Percorso non hamiltoniano
6
A
4
B
5
6
C 2
4
D
7
8
F
3
E
9
6
2
G
Non visita tutti i nodi!
Percorso non hamiltoniano
6
A
4
B
5
6
C 2
4
D
7
8
F
3
E
9
6
2
G
A,C,F,D,E,G,E,...,G,E,B,A: G ed E visitati varie volte
TSP come problema sui grafi
Dato un grafo G con archi pesati
vogliamo calcolare un
Ciclo Hamiltoniano di Costo Minimo
Esempio di grafo pesato
2
A
B
4
4
5
C
2
3
D
Grafo non diretto = costo A,B=costo
B,A
...
I Cammino Hamiltoniano
2
A
4
4
5
C
B
2
3
D
A,C,D,B,A costo 5+3+2+2=12
II Cammino Hamiltoniano
2
A
4
4
5
C
B
2
D
3
A,B,C,D,A costo 2+4+3+4=13
III Cammino Hamiltoniano
2
A
4
4
5
C
B
2
D
3
A,C,B,D,A costo 5+4+2+4=16
Come si risolve TSP?
Soluzioni a TSP
• Trovare una soluzione esatta del problema
TSP (cioe’ calcolare un tour minimo) e’
difficile anche per un elaboratore
• 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
In generale
• Grafo completo = esiste un arco per ogni coppia di nodi
• Il numero di cicli hamiltoniani in un grafo completo con n
nodi è pari a (n-1)!
• Il numero di cicli hamiltoniani cresce esponenzialmente
col numero dei nodi
Si puo’ veramente risolvere?
Si, e’stato calcolato nel 1954!
Si puo’ fare anche per molte piu’ citta’!
Es. 13,509 citta’
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 il costo di C dei pesi sugli archi del
ciclo indotto da P
– se P 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 ponendo I=J
• 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 algoritmi
• 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)
• Idea: si calcola una soluzione con un
algoritmo euristico e poi si controlla
che sia ottimale
Uso del calcolo dei percorsi minimi
• Google map:
http://maps.google.it/
• Trenitalia:
http://trenitalia.it/
• AMT:
http://www.amt.genova.it/pianifica/calcola_percorso.asp
• ...
Prima della pratica ... un po’
di esercizi di riepilogo...
Quanti e quali cicli hamiltoniani contiene il
seguente grafo?
A
5
2
1
4
6
3
1
C
B
3
D
Applicate l’algoritmo Nearest Neighbour al
seguente grafo a partire dal nodo A
6
A
5
4
C 2
6
5
3
8
F
3
1
D
3
8
B
E
9
6
2
G
4
Applicate l’algoritmo Nearest Neighbour al
seguente grafo a partire dal nodo E
6
A
5
4
C 2
6
5
3
8
F
3
1
D
3
8
B
E
9
6
2
G
4
Aggiungete pesi (qualsiasi) sugli archi in modo
che la soluzione calcolata con l’algoritmo NN a
partire dal nodo A non sia quella ottimale
A
B
C
D
.
Disegnate un grafo nel piano Cartesiano
(nodi=punti, pesi sugli archi=distanze tra i
punti) per il quale NN non restituisce la
soluzione ottimale
Provate a risolvere l’icosian game...
Cioe’ a calcolare un tour nel seguente grafo