CONOSCERE CONOSCERSI COMUNICARE. Parte SettimaConoscere - Conoscersi - Comunicare Sonia Fiori 2...

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à?


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

http://www.tsp.gatech.edu/history/pictorial/car54.html

http://www.tsp.gatech.edu/history/pictorial/car54.html


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”.


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

http://www.tsp.gatech.edu/index.html


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


7

1991 David Applegate

Robert Bixby

Vasek Chvàtal

William Cook

3038

1994 Applegate Bixby

Chvàtal Cook

7397


Chvàtal Cook

225


Chvàtal Cook

13509 USA


8

e infine


Chvàtal Cook

15112 Germania

2003 7516353739 world

2004 Applegate Bixby, Chvátal Cook eKeld Helsgaun

24978 Svezia


9

Esempi

120 città


10

15112(ottimale)


11

24978


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.


13

World 7516353739


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?


15

Grafo del problema 3UTIl problema può essere rappresentato con un grafo, la

casa rosa e quella verde si collegano, la casa marrone….


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


17

Terra celeste

• Se è nella terra celeste si può collegare solo all’acqua e alla luce.

rosa

verde

marrone

GAS

ACQUA

LUCE


18

Terra rosa

• Se è nel rosa si può collegare solo all’acqua e al gas.

rosa

verde

marrone

GAS

ACQUA

LUCE


19

Terra biancabianca

• Se è nel bianco bianco si può collegare solo alla luce e al gas.

rosa

verde

marrone

GAS

ACQUA

LUCE


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 .


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


22

Colorare con solo 2 colori


23

Colorare con solo 3 colori


24

Numero minimo di colori?


25

Soluzione 2


26

Soluzione 3


27

Soluzione


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


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.


30

Parole chiave

• Problema T.S.P.

• 3 utenze

• grafo planare

• teorema 4 colori


31

Fine

settima parte


32

Altre mappe


33

Soluzioni

CONOSCERE CONOSCERSI COMUNICARE. Parte SettimaConoscere - Conoscersi - Comunicare Sonia Fiori 2...

Documents

Transcript of CONOSCERE CONOSCERSI COMUNICARE. Parte SettimaConoscere - Conoscersi - Comunicare Sonia Fiori 2...