Il problema
del
commesso
viaggiatore
Vediamo un esempio di
“informatica”
•
•
•
•
•
Modellazione astratta di un problema reale
Definizione di algoritmi che lo risolvano
Ricorsione
Confronto tra l’efficienza di diversi algoritmi
Esistenza di problemi difficili
Avete mai pianificato un viaggio
in più tappe?
Quale metodo avete usato per
minimizzare la distanza totale
percorsa?
Cartina alla mano non sembra così
difficile ... soprattutto per poche tappe
Pensate però per esempio di dover
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 cammino 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 è uno dei problemi più studiati in informatica
• Appartiene alla classe dei problemi difficili (NPhard), vedremo poi in che senso
• 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
È un caso molto particolare di TSP!
Forma generale TSP
• La formulazione generale considera forme
geometriche qualsiasi e distanze tra le città
• 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
cammino del trapano)
– protocolli di routing
– DNA sequencing
– ...
Modelliamo e studiamo
TSP
Quali informazioni ci servono?
Città = nodi
AOSTA
MILANO
TORINO
GENOVA
Distanze = archi pesati
AOSTA
186
115
142
TORINO
MILANO
246
140
169
GENOVA
Modello = Grafo (non orientato, pesato)
6
A
4
B
5
6
C 2
8
F
3
Archi=strade
4
D
7
E
9
6
Nodi=città
2
G
Pesi=distanze
Definizione di grafo
grafo (semplice) G = (V, E):
• insieme V di nodi o vertici
• insieme E di archi (o spigoli, ingl. edges)
• ogni arco è una coppia di nodi distinti, detti estremi
dell’arco
due tipi di grafi:
• non orientati (undirected): gli archi non hanno un verso,
cioè, formalmente, sono coppie non ordinate
• orientati (directed): gli archi hanno un verso, cioè sono
coppie ordinate
Altre definizioni
• cammino = sequenza di nodi v0 … vn con n  0, (vi, vi+1)
arco per ogni 0  i < n
• lunghezza di un cammino = numero archi = numero dei
nodi – 1
• ciclo = cammino (non nullo) in cui il primo nodo coincide
con l'ultimo
• ciclo hamiltoniano = ciclo in cui tutti i nodi sono distinti
tranne il primo e l’ultimo
• grafo pesato = grafo + funzione c che associa a ogni arco
un peso (costo)
• costo di un cammino = somma costi archi
cammino 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 = cammino con costo 4+2+4+2=14
Ciclo = cammino 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
È un ciclo che visita TUTTI i nodi UNA SOLA volta
Ciclo 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!
Ciclo 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 pesato G
calcolare un
ciclo hamiltoniano di costo minimo
In termini più informatici:
dare un algoritmo che dato un grafo pesato
G calcoli un ciclo hamiltoniano di costo
minimo
G
min, costomin
Min_ham
Algoritmo
• Algoritmo: sequenza di istruzioni eseguibile
“automaticamente”
• Esempi di istruzioni:
– variabile = valore
– SE (condizione) ALLORA azione
– SE (condizione) ALLORA azione ALTRIMENTI azione
- PER OGNI (valore in insieme) azione
- FINCHÈ (condizione) azione
Scritto in un linguaggio di programmazione può essere
eseguito da un calcolatore
Problema preliminare: quanti e quali cicli hamiltoniani (a partire
da A) contiene il seguente grafo?
A
2
B
1
5
6
E
3
1
C
3
D
Algoritmo richiesto
G, v1
hcicli
Ham
Versione testuale (ricorsiva) dell’algoritmo
Ham(G, v1 … vk, hcicli) =
SE (ci sono nodi non in v1 … vk) ALLORA
PER OGNI (arco (vk,v) con v non in v1 … vk)
Ham(G, v1 … vk v, hcicli)
ALTRIMENTI
SE (c’è arco(vk, v1)) ALLORA
hcicli = hcicli + v1 … vk v1
Chiamata iniziale
hcicli = insieme vuoto
Ham(G, v1, hcicli)
Modifichiamo in modo da trovare il cammino minimo
algoritmo richiesto:
G, v1
min, costomin
Min_ham
Modifichiamo in modo da trovare il cammino
minimo
Min_ham(G, v1 … vk, costo, min, costomin) =
SE (ci sono nodi in G non in v1 … vk) ALLORA
PER OGNI (arco (vk,v) con v non in v1 … vk)
Min_ham(G, v1 … vk v, costo+c(vk,v), min, costomin)
ALTRIMENTI
SE (c’è arco(vk, v1)) E costo+ c(vk, v1) < costomin
ALLORA
min = v1 … vk v1
costomin = costo+ c(vk, v1)
Chiamata iniziale:
costomin = +∞
Min_ham(G, v1, min, costomin)
Quanto “costa” questo algoritmo?
• Se il grafo è completo, ossia c’è un arco per
ogni coppia di nodi (come avviene nel TSP)
i cicli hamiltoniani sono tanti quante le
permutazioni dei nodi
Se il grafo è completo, equivalentemente:
Generate & Test
costomin = +∞
Min_ham(G, min, costomin)
PER OGNI (permutazione v1 … vn dei nodi di G)
costo = c(v1, v2)+....+ c(vn-1, vn)
SE costo < costomin ALLORA
min = v1 … vn
costomin = costo
È possibile evitare di generare TUTTE le permutazioni?
In qualche caso …
Min_ham(G, v1 … vk, costo, min, costomin) =
SE (ci sono nodi non in v1 … vk) ALLORA
PER OGNI (arco (vk,v) con v non in v1 … vk)
SE costo+costo(vk,v) < costomin ALLORA
Min_ham(G, v1 … vk v, costo+c(vk,v), min, costomin)
ALTRIMENTI
SE (arco(vk, v1)) E costo+ c(vk, v1) < costomin
ALLORA
min = v1 … vk v1
costomin = costo+ c(vk, v1)
Tuttavia, questo non migliora le prestazioni
dell’algoritmo “in generale” …
C’è sempre un caso peggiore
Problema
• Trovare una soluzione esatta del problema
TSP (cioè calcolare un tour minimo) è
difficile anche per un elaboratore
• La difficoltà è legata al numero di possibili
percorsi che occorre esplorare per calcolare
quello minimo
Per capire la difficoltà del problema
... facciamo due conti
• Negli USA ci sono 49 stati continentali + un
distretto
• Supponiamo che si programmi di fare un
solo comizio in ogni stato
Quanti percorsi devo considerare per
calcolare il migliore?
• Partendo da Washington, ci sono 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 più breve è
49! = 49 * 48 * ... * 3 * 2 * 1
... nell’ordine di 1062 cioè maggiore del
numero di atomi di cui è composta la Terra
Ricapitolando
• 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 può veramente risolvere?
Sì, è stato calcolato nel 1954!
È stato risolto per molte più città!
per esempio 13,509 città
Metodi di risoluzione per TSP
Algoritmi per TSP
Algoritmi esatti
Applicabili solo a problemi con un numero di città
relativamente basso
Algoritmi euristici
Producono soluzioni probabilmente buone, ma
non necessariamente ottimali
Problema
• Abbiamo visto che per TSP con molte città
il numero di possibili percorsi può 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 città più vicina non
ancora visitata
• L’algoritmo termina quando abbiamo visitato tutte
le città
Esempio Nearest Neighbour
A
5
C
B
2
4
4
2
3
D
...
Algoritmo Nearest Neighbour
NN(G, cammino) =
SE (ci sono nodi non in cammino) ALLORA
nodomin = nodo non in cammino più “vicino” a cammino.fine
cammino = cammino + nodomin
NN(G,cammino)
ALTRIMENTI
cammino = cammino + cammino.inizio
Chiamata iniziale:
cammino = v1
NN(G, cammino)
Algoritmo Nearest Neighbour
NN(G, cammino) =
SE (ci sono nodi non in cammino) ALLORA
costomin = +∞
PER OGNI (arco(cammino.fine,v) con v non in cammino)
SE c(cammino.fine,v) < costomin
ALLORA
nodomin = v;
costomin = c(cammino.fine,v)
cammino = cammino + nodomin
NN(G,cammino)
ALTRIMENTI
cammino = cammino + (cammino.fine,cammino.inizio)
Chiamata iniziale:
cammino = v1
NN(G, cammino)
Osservazioni su NN
• È un algoritmo intuitivo
• Non dà sempre la soluzione ottimale (cercare di
ottenere un vantaggio immediato non sempre è la
scelta migliore...)
• Tuttavia è una buona approssimazione
dell’algoritmo esatto
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
Esercizi
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