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 (NP-hard)

• 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

MILANO

TORINO

GENOVA

140

169

246

115 142

186

Modello = Grafo

Nodi=citta

Archi=strade

Pesi=distanze

F G

6

8

5

6

6

7

A B

C DE

92

3

2

4

4

Percorso in grafo

A,C,D,E,G,B = percorso con costo 4+2+2+2=12

F G

6

8

5

6

6

7

A B

C DE

92

3

2

4

4

Ciclo = Percorso chiuso

A,C,D,E,B,A = ciclo con costo 4+2+4+3+6

F G

6

8

5

6

6

7

A B

C DE

92

3

2

4

4

Ciclo hamiltoniano (Tour)

E’ un ciclo che visita TUTTI i nodi UNA SOLA volta

F G

6

8

5

6

6

7

A B

C DE

92

3

2

4

4

Percorso non hamiltoniano

F G

6

8

5

6

6

7

A B

C DE

92

3

2

4

4

Non visita tutti i nodi!

Percorso non hamiltoniano

F G

6

8

5

6

6

7

A B

C DE

92

3

2

4

4

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

A B

C D

2

5 2

3

44

...Grafo non diretto = costo A,B=costo B,A

I Cammino Hamiltoniano

A B

C D

2

5 2

3

44

A,C,D,B,A costo 5+3+2+2=12

II Cammino Hamiltoniano

A B

C D

2

5 2

3

44

A,B,C,D,A costo 2+4+3+4=13

III Cammino Hamiltoniano

A B

C D

2

5 2

3

44

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 & TestPer 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

2

5 2

3

4

A B

CD

4

...

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 attraverso24.978 citta’ in Svezia (72.500 km)

• Idea: si calcola una soluzione con unalgoritmo 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?

2

5 6

3

A B

CD

4

31

1

Applicate l’algoritmo Nearest Neighbour al seguente grafo a partire dal nodo A

F G

6

8

5

6

6

3

A B

C DE

92

3

2

4

1

4

3

5

8

Applicate l’algoritmo Nearest Neighbour al seguente grafo a partire dal nodo E

F G

6

8

5

6

6

3

A B

C DE

92

3

2

4

1

4

3

5

8

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