ALLA RICERCA DEI CAMMINI MINIMI

UN'INTRODUZIONE

Un esempio: il navigatore

Due compiti principali

  • Determinare la nostra posizione
  • Calcolare il cammino più veloce verso la destinazione

Determinare la nostra posizione

  • Simile a determinare epicentro di terremoto
    • Uso di satelliti e ricevitori invece che onde sismiche

Epicentro a 347 chilometri da Roma

Epicentro a 86 chilometri da Firenze

Epicentro a 280 chilometri da Milano

Calcolare i cammini minimi

Mappa di Pisa

Voi siete qui

Grafo di Pisa

Il problema

Calcolare i cammini minimi

L'algoritmo

Calcolare i cammini minimi

L'algoritmo

Calcolare i cammini minimi

L'algoritmo

Calcolare i cammini minimi

L'algoritmo

Calcolare i cammini minimi

L'algoritmo

Calcolare i cammini minimi

L'algoritmo

Calcolare i cammini minimi

L'algoritmo

Calcolare i cammini minimi

L'algoritmo

Calcolare i cammini minimi

L'ANALISI DELL'algoritmo

Correttezza

  • Non banale ma basata su semplice osservazione
    • Ogni sotto-cammino di un cammino minimo è un cammino minimo

Calcolare i cammini minimi

L'ANALISI DELL'algoritmo

Efficienza (n indica il numero di nodi)

  • Ogni nodo viene analizzato una e una sola volta
    • Quando diventa grigio
    • Quindi, n iterazioni
  • Quando un nodo è analizzato
    • Ogni altro nodo viene esaminato per vedere se la sua distanza migliora
    • Quindi, per ogni iterazione, n verifiche
  • In totale il tempo è quadratico nel numero di nodi
    • Se dobbiamo farlo per ogni possibile punto di partenza
      • Tempo cubico nel numero di nodi

Calcolare i cammini minimi

L'ANALISI DELL'algoritmo

n Numero operazioni Tempo
10 1000 1𝜇s
100 1000000 1ms
1000 1000000000 1s
10000 1000000000000 16.6m

Con un calcolatore che esegue un miliardo di operazioni al secondo

Bisogna fare di meglio...

Calcolare i cammini minimi

Il programma: i dati

f = fill(false,7)

Array : sequenza lineare di valori

  • Elemento in una qualunque posizione accessibile direttamente mediante il nome dell'array e la posizione
d = fill(typemax(Float64),7)
d[7] = 0

Array di valori di verità per indicare se nodo è stato analizzato

Array di numeri reali per memorizzare le distanze correnti

Calcolare i cammini minimi

Il programma: i dati

g = [0 6 0 0 0 0 0; 
     6 0 0 0 0 0 0; 
     4.5 4.5 0 0 0 0 0; 
     0 5 2.9 0 2.5 0 0; 
     0 0 6 2.5 0 3 9; 
     0 5 0 0 3 0 0; 
     0 0 0 0 9 0 0]

Array bidimensionale: tabella di valori

  • Elemento in una qualunque riga e una qualunque colonna accessibile direttamente mediante il nome dell'array, l'indice di riga e l'indice di colonna

Array bidimensionale delle distanze tra i nodi

  • 0 indica che non c'è collegamento

Calcolare i cammini minimi

Il programma: le funzioni

Struttura del programma

 

  • Per tante volte quanti sono i nodi del grafo
     
    • Trova il nodo x più vicino alla sorgente e non ancora analizzato
       
    • Aggiorna le distanze degli altri nodi se passando per x la loro distanza dalla sorgente diminuisce

 

Programmazione procedurale

  • Programma scomposto in funzioni semplici

Calcolare i cammini minimi

Il programma: le funzioni

Funzione per trovare il nodo x più vicino alla sorgente e non ancora analizzato

function findMinimum(d,f,n)
	min = typemax(Float64)
	x = 0
	for i = 1:n
		if d[i] < min && f[i] == false
			min = d[i]
			x = i
		end
	end
	return x
end

Calcolare i cammini minimi

Il programma: le funzioni

Funzione per aggiornare le distanze

function updateDistances(g,n,d,x)
	for y = 1:n
		if g[x,y]>0 && d[y]>d[x]+g[x,y]
			d[y] = d[x]+g[x,y]
		end
	end
end

Calcolare i cammini minimi

Il programma: le funzioni

Funzione principale

function dijkstra(g,n,s,d,f)
	for i = 1:n
		x = findMinimum(d,f,n)
		f[x] = true
		updateDistances(g,n,d,x)
	end
	return d
end

Calcolare i cammini minimi

Il programma: La verifica sperimentale

d = dijkstra(g,n,s,d,f)
println(d)
[18.9, 16.5, 14.4, 11.5, 9.0, 12.0, 0.0]

produce