CONOSCERE CONOSCERSI COMUNICARE

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

2

ProblemaTrovare il cammino più corto da A a D del

seguente grafo B

G

AE F

C

H

D

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

3

Algoritmo cammini minimiEsiste una regola, algo-

ritmo, per trovare il cammino più breve che unisce due punti di un grafo?(navigatori!)

Un algoritmo efficiente per risolvere il problema si deve a Edsger Wybe Dijkstra (1930-2002), esperto informatico olandese, nel 1959.

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

4

Algoritmo di Dijkstra

• Il grafo deve essere connesso

• i pesi devono essere positivi

vediamo come funziona

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

5

Passo 1• Si attribuiscono a tutti i vertici distanza infinita

(+) da AB(+inf)

G(+inf)

AE(+inf) F(+inf)

C(+inf)

H(+inf)

D(+inf)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

6

Passo 2• Si esamina il nodo A e i suoi lati uscenti• Se il peso è < di quello già scritto si scrive il peso e da

quale nodo siamo giunti, si colora il nodo esaminato

B(2,A)

G(6,A)

AE(+inf) F(+inf)

C(+inf)

H(+inf)

D(+inf)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

7

Passo 3• Si esamina un nodo e i suoi lati uscenti• si scrive il peso (peso precedente +ultimo peso) e

il nodo di provenienza se il nuovo<vecchio• si colora il nodo esaminato

B(2,A)

G(6,A)

A

E(4,B) F(+inf)

C(9,B)

H(+inf)

D(+inf)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

8

Passo 4• Idem

B(2,A)

G(6,A)<(5,E)

A

E(4,B) F(6,E)

C(9,B)

H(+inf)

D(+inf)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

9

Passo 5• idem

B(2,A)

G(5,E)

A

E(4,B) F(6,E)

C(9,B)

H(9,G)

D(+inf)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

10

• idemPasso 6

B(2,A)

G(5,E)

A

E(4,B) F(6,E)

C(9,B)

H(9,G)<(8,F)

D(+inf)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

11

Passo 7

B(2,A)

G(5,E)

A

E(4,B) F(6,E)

C(9,B)

H(8,F)

D(11,C)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

12

Passo 8

B(2,A)

G(5,E)

A

E(4,B) F(6,E)

C(9,B)

H(8,F)

D(11,C)<(10,H)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

13

Passo 9 Fine!

B(2,A)

G(5,E)

A

E(4,B) F(6,E)

C(9,B)

H(8,F)

D(10,H)

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

14

Conclusione• Su ogni nodo è scritta la distanza minima da

A• Partendo dal traguardo si risale al cammino

minimo• complessità O(n2)• Soluzione Rossa

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

15

Soluzione: peso 10B

G

AE F

C

H

D

2

6

2

1

4

2

7

3

2

3

2

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

16

Esercizi

• Trovare il cammino minimo dei grafi delle fotocopie

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

17

Quale tram prendo?• Non esiste un metodo più semplice per

trovare la strada più corta?• Se devo andare da un punto ad un altro in

città con il tram quale collegamento scelgo guardando una cartina stradale?

• Considero anche collegamenti che mi porterebbero molto lontano?

• L’intuito ci può aiutare?

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

18

Il giardiniere ci può aiutare!Se il tragitto dipende solo dai chilometri percorsi si

può:• trovare un tragitto C abbastanza casualmente• stimare quanto C è lontano dal cammino ottimale

confrontandolo con la distanza minima tra i due punti cioè quella in linea d’aria

• costruire un’ellisse con il metodo del giardiniere• cercare il cammino ottimale all’interno dell’ellisse.• altrimenti? Dijkstra!

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

19

Costruiamo un’aiuola• fuochi = località

• lunghezza filo = lunghezza C• tendere il filo e tracciare la curva

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

20

Facciamo buio

Forme generate da una torcia

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

21

ConicheSezioni di un cono

cerchio ellisse parabola iperbole

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

22

Parole chiave

• Algoritmo Dijkstra

• cammino minimo

• ellisse

• coniche

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

23

Fine terza parte

Parte Terza Conoscere - Conoscersi - Comunicare Sonia Fiori

24

Soluzioni fotocopie