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