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

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


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.


4

Algoritmo di Dijkstra

• Il grafo deve essere connesso

• i pesi devono essere positivi

vediamo come funziona


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


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


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


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


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


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


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


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


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


14

Conclusione• Su ogni nodo è scritta la distanza minima da

A• Partendo dal traguardo si risale al cammino

minimo• complessità O(n2)• Soluzione Rossa


15

Soluzione: peso 10B

G

AE F

C

H

D

2

6

2

1

4

2

7

3

2

3

2


16

Esercizi

• Trovare il cammino minimo dei grafi delle fotocopie


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?


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!


19

Costruiamo un’aiuola• fuochi = località

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


20

Facciamo buio

Forme generate da una torcia


21

ConicheSezioni di un cono

cerchio ellisse parabola iperbole


22

Parole chiave

• Algoritmo Dijkstra

• cammino minimo

• ellisse

• coniche


23

Fine terza parte


24

Soluzioni fotocopie

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

Documents

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