CONOSCERE CONOSCERSI COMUNICARE
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
2
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
3
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
4
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
5
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
6
Evoluzioneanno autore vertici
1954 Geroge Dantzig
Ray Fulkerson
Selmer Johnson
49 USA
1977 Martin Grötschel 120 Germania Ovest
1987 Padberg, Rinaldi 532 USA
1987 Martin Grötschel
Olaf Holland
666 World
1987 Padberg, Rinaldi 2392 fori
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
7
1991 David Applegate
Robert Bixby
Vasek Chvàtal
William Cook
3038
1994 Applegate Bixby
Chvàtal Cook
7397
1995 Applegate Bixby
Chvàtal Cook
225
1998 Applegate Bixby
Chvàtal Cook
13509 USA
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
8
e infine
2001 Applegate Bixby
Chvàtal Cook
15112 Germania
2003 7516353739 world
2004 Applegate Bixby, Chvátal Cook eKeld Helsgaun
24978 Svezia
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
9
Esempi
120 città
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
10
15112(ottimale)
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
11
24978
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
12
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
13
World 7516353739
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
14
Le tre utenzeTre 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
15
Grafo del problema 3UTIl 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
16
Dov’è la terza casa?
• ..si troverà in una delle tre zone in cui è diviso il piano: rosa, celeste o bianco.
rosa
verde
marrone
GAS
ACQUA
LUCE
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
17
Terra celeste
• Se è nella terra celeste si può collegare solo all’acqua e alla luce.
rosa
verde
marrone
GAS
ACQUA
LUCE
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
18
Terra rosa
• Se è nel rosa si può collegare solo all’acqua e al gas.
rosa
verde
marrone
GAS
ACQUA
LUCE
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
19
Terra biancabianca
• Se è nel bianco bianco si può collegare solo alla luce e al gas.
rosa
verde
marrone
GAS
ACQUA
LUCE
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
20
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
21
Carte geografiche• colorare con solo 2 colori.• colorare con solo 3 colori• quanti colori occorrono in generale?
Chi è l’autore?
M.C.Escher
Circle limit III
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
22
Colorare con solo 2 colori
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
23
Colorare con solo 3 colori
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
24
Numero minimo di colori?
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
25
Soluzione 2
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
26
Soluzione 3
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
27
Soluzione
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
28
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
29
Teorema dei quattro coloriE’ 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
30
Parole chiave
• Problema T.S.P.
• 3 utenze
• grafo planare
• teorema 4 colori
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
31
Fine
settima parte
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
32
Altre mappe
Parte Settima Conoscere - Conoscersi - Comunicare Sonia Fiori
33
Soluzioni
Top Related