CONOSCERE CONOSCERSI
COMUNICARE
Problema
Trovare il cammino più corto da A a D del
seguente grafo
C
B
7
2
3
2
E
F
3
A
D
2
6
2
1
2
G
Parte Terza
4
H
Conoscere - Conoscersi - Comunicare
Sonia Fiori
2
Algoritmo cammini minimi
Esiste una regola, algoritmo, 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
3
Algoritmo di Dijkstra
• Il grafo deve essere connesso
• i pesi devono essere positivi
vediamo come funziona
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
4
Passo 1
• Si attribuiscono a tutti i vertici distanza infinita
(+) da A
C(+inf)
B(+inf)
7
2
3
2
E(+inf)
F(+inf)
A
3
D(+inf)
2
6
2
1
2
G(+inf)
Parte Terza
4
H(+inf)
Conoscere - Conoscersi - Comunicare
Sonia Fiori
5
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
esaminatoB(2,A)
C(+inf)
7
2
3
2
E(+inf)
F(+inf)
A
3
D(+inf)
2
6
2
1
2
G(6,A)
Parte Terza
4
H(+inf)
Conoscere - Conoscersi - Comunicare
Sonia Fiori
6
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
C(9,B)
B(2,A)
7
2
3
2
E(4,B)
F(+inf)
A
3
D(+inf)
2
6
2
1
2
Parte Terza
G(6,A)
4
Conoscere - Conoscersi - Comunicare
Sonia Fiori
H(+inf)
7
Passo 4
• Idem
C(9,B)
B(2,A)
7
2
3
2
E(4,B)
F(6,E)
3
A
D(+inf)
2
6
2
1
2
G(6,A)<(5,E)
Parte Terza
4
H(+inf)
Conoscere - Conoscersi - Comunicare
Sonia Fiori
8
Passo 5
• idem
C(9,B)
B(2,A)
7
2
3
E(4,B)
2
F(6,E)
3
A
D(+inf)
2
6
2
1
2
G(5,E)
Parte Terza
4
H(9,G)
Conoscere - Conoscersi - Comunicare
Sonia Fiori
9
Passo 6
• idem
C(9,B)
B(2,A)
7
2
3
2
E(4,B)
F(6,E)
3
A
D(+inf)
2
6
2
1
2
G(5,E)
Parte Terza
4
H(9,G)<(8,F)
Conoscere - Conoscersi - Comunicare
Sonia Fiori
10
Passo 7
C(9,B)
B(2,A)
7
2
3
2
E(4,B)
F(6,E)
3
A
D(11,C)
2
6
2
1
2
G(5,E)
4
H(8,F)
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
11
Passo 8
C(9,B)
B(2,A)
7
2
3
2
E(4,B)
F(6,E)
A
3
D(11,C)<(10,H)
2
6
2
1
2
G(5,E)
4
H(8,F)
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
12
Passo 9
Fine!
C(9,B)
B(2,A)
7
2
3
2
E(4,B)
F(6,E)
3
A
D(10,H)
2
6
2
1
2
G(5,E)
4
H(8,F)
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
13
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
14
Soluzione: peso 10
C
B
7
2
3
2
E
F
3
A
D
2
6
2
1
2
G
Parte Terza
4
H
Conoscere - Conoscersi - Comunicare
Sonia Fiori
15
Esercizi
• Trovare il cammino minimo dei grafi delle
fotocopie
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
16
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
17
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
18
Costruiamo un’aiuola
• fuochi = località
• lunghezza filo = lunghezza C
• tendere il filo e tracciare la curva
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
19
Facciamo buio
Forme generate da una torcia
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
20
Coniche
Sezioni di un cono
cerchio
ellisse
parabola
iperbole
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
21
Parole chiave
•
•
•
•
Algoritmo Dijkstra
cammino minimo
ellisse
coniche
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
22
Fine
terza parte
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
23
Soluzioni fotocopie
Parte Terza
Conoscere - Conoscersi - Comunicare
Sonia Fiori
24