CONOSCERE CONOSCERSI
COMUNICARE
Problema del commesso viaggiatore
In inglese Traveling Salesman Problem T.S.P.
Come deve pianificare il suo itinerario un
commesso viaggiatore, un agente assicurativo,
un turista curioso,….. se vuole visitare un certo
numero di città percorrendo il minimo numero
di chilometri e non passando due volte per la
stessa città?
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
2
Hamilton?
• E’ ancora un problema di
ricerca del circuito di
Hamilton in un grafo connesso.
• Il problema del T.S.P. era
diventato piuttosto famoso
negli anni ’60, tanto che una
importante impresa americana aveva
proclamato una competizione offrendo 10 000 $ a chi
avesse trovato la soluzione per 33 città.
• http://www.tsp.gatech.edu/history/pictorial/car54.html
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
3
Bisogna accontentarsi!
Non esiste ancora un algoritmo efficiente per la
soluzione del problema in generale. Esistono alcuni
algoritmi, Christofides 1975, che assicurano una
soluzione, anche se non ottimale, che dista meno del
150% da quella del cammino minimo.
Esistono anche algoritmi per avere approssimazioni
migliori che usano cammini su poliedri, spesso
immersi in spazi a molte dimensioni.
Questi studi hanno dato vita ad una nuova branca della
matematica chiamata “ottimizzazione combinatoria”.
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
4
Breve storia del T.S.P.
Nel sito
http://www.tsp.gatech.edu/index.html
sono riportati i cammini trovati dal 1954 al
2004.
Trovare il sito aprire la pagina
History of TSP e poi
TSP in pictures
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
5
Evoluzione
anno
1954
1977
1987
1987
1987
Parte Settima
autore
vertici
Geroge Dantzig
49
Ray Fulkerson
Selmer Johnson
Martin Grötschel
120
Padberg, Rinaldi
532
Martin Grötschel
666
Olaf Holland
Padberg, Rinaldi
2392
Conoscere - Conoscersi - Comunicare
Sonia Fiori
USA
Germania Ovest
USA
World
fori
6
1991
1994
1995
1998
Parte Settima
David Applegate
Robert Bixby
Vasek Chvàtal
William Cook
Applegate Bixby
Chvàtal Cook
Applegate Bixby
Chvàtal Cook
Applegate Bixby
Chvàtal Cook
3038
7397
225
13509 USA
Conoscere - Conoscersi - Comunicare
Sonia Fiori
7
e infine
2001
Applegate Bixby
Chvàtal Cook
2003
2004
Parte Settima
15112 Germania
7516353739 world
Applegate Bixby,
Chvátal Cook e
Keld Helsgaun
24978 Svezia
Conoscere - Conoscersi - Comunicare
Sonia Fiori
8
Esempi
120 città
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
9
15112
(ottimale)
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
10
24978
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
11
Il giro del mondo
Sempre nello stesso sito alla pagina Test
Data, World TSP si trova il tour del mondo
alla pagina National TSPs si trovano i tuors
di molte nazioni tra cui quello dell’Italia.
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
12
World
7516353739
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
13
Le tre utenze
Tre edifici devono essere collegati alle utenze
del GAS, LUCE, ACQUA.
E’ possibile fare i collegamenti senza che le
linee si attraversino?
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
14
Grafo del problema 3UT
Il problema può essere rappresentato con un grafo, la
casa rosa e quella verde si collegano, la casa
marrone….
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
15
Dov’è la terza casa?
• ..si troverà in
una delle tre
zone in cui è
diviso il piano:
rosa, celeste o
bianco.
Parte Settima
rosa
GAS
LUCE
verde
marrone
Conoscere - Conoscersi - Comunicare
Sonia Fiori
ACQUA
16
Terra celeste
• Se è nella terra
celeste si può
collegare solo
all’acqua e alla
luce.
rosa
GAS
LUCE
verde
marrone
ACQUA
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
17
Terra rosa
• Se è nel rosa si
può collegare
solo all’acqua e
al gas.
marrone
rosa
GAS
LUCE
verde
ACQUA
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
18
Terra bianca
• Se è nel bianco
si può collegare
solo alla luce e
al gas.
rosa
GAS
LUCE
verde
ACQUA
marrone
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
19
Accoppiamenti
• Non è possibile collegare tre vertici con altri
tre vertici di un grafo senza che i lati si
incontrino.
• Un grafo in cui i lati non si intersecano si
dice grafo planare .
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
20
Carte geografiche
• colorare con solo 2 colori.
• colorare con solo 3 colori
• quanti colori occorrono in generale?
M.C.Escher
Circle limit III
Chi è l’autore?
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
21
Colorare con solo 2 colori
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
22
Colorare con solo 3 colori
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
23
Numero minimo di colori?
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
24
Soluzione 2
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
25
Soluzione 3
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
26
Soluzione
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
27
Mappe e Grafi
• Ogni mappa può essere rappresentata con
un grafo.
• Il problema si trasforma in :
colorare i vertici in modo che due vertici
che sono connessi non abbiano lo stesso
colore
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
28
Teorema dei quattro colori
E’ possibile colorare qualsiasi carta geografica,
connessa, con solo 4 colori.
Nel 1852 l’inglese Francis Guthrie aveva scoperto
questa proprietà ma solo nel 1977 i matematici
Kenneth Appel e Wolfgang Haken (Illinois) sono
riusciti a dimostrarla anche grazie all’aiuto di
potenti calcolatori.
Altre due dimostrazioni sono state fatte nel 1996 e
nel 1998, una terza di solo 12 pagine nel 2004 non
è stata ancora verificata.
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
29
Parole chiave
•
•
•
•
Problema T.S.P.
3 utenze
grafo planare
teorema 4 colori
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
30
Fine
settima parte
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
31
Altre mappe
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
32
Soluzioni
Parte Settima
Conoscere - Conoscersi - Comunicare
Sonia Fiori
33