Algoritmi e Strutture Dati
Capitolo 11: Strutture di dati e Progettazione Algoritmi
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Introduzione
Dato un problema
✦
Non ci sono “ricette generali” per risolverlo in modo efficiente
✦
Tuttavia, è possibile evidenziare quattro fasi
✦
Classificazione del problema
✦
Caratterizzazione della soluzione
✦
Tecnica di progetto
✦
Utilizzo di strutture dati
✦
Note
✦
Non sono fasi strettamente sequenziali
✦
© Alberto Montresor
2
Classificazione di un problema
Fa parte di una classe più ampia di problemi?
✦
Problemi decisionali:
Il dato di ingresso soddisfa una certa proprietà?
✦
Soluzione: risposta sì/no
✦
Es: Stabilire se un grafo è connesso
✦
✦
Problemi di ricerca:
Spazio di ricerca: insieme di “soluzioni” possibili
✦
Soluzione ammissibile: soluzione che rispetta certi vincoli
✦
Es: posizione di una sottostringa in una stringa
✦
© Alberto Montresor
3
Introduzione
Problemi di ottimizzazione:
✦
Ogni soluzione è associata ad una funzione di costo
✦
Vogliamo trovare la soluzione di costo minimo
✦
Es: cammino più breve fra due nodi
✦
Problemi di approssimazione:
✦
A volte, trovare la soluzione ottima è computazionalmente impossibile
✦
Ci si accontenta di una soluzione approssimata:
✦
costo basso, ma non sappiamo se ottimo
✦
Es: problema del commesso viaggiatore
✦
© Alberto Montresor
4
Caratterizzazione della soluzione
Definire la soluzione dal punto di vista matematico
✦
Spesso la formulazione è banale...
✦
... ma può suggerire una prima idea di soluzione
✦
Es: Selection Sort:
✦
Data una sequenza di n elementi, una permutazione ordinata è data dal minimo seguita da una
permutazione ordinata dei restanti n-1 elementi
Le caratteristiche matematiche della soluzione possono suggerire una possibile
tecnica
✦
Esempio: sottostruttura ottima → programmazione dinamica
✦
© Alberto Montresor
5
Problema cammini minimi
Input
✦
Grafo orientato G=(V,E)
✦
Un nodo di partenza r
✦
Funzione di peso w: E → R
✦
Definizione
✦
Dato un cammino c = v1,v2, ..., vk con k > 1, il costo del cammino è dato da
✦
Output
✦
Trovare un cammino da r ad u, per ogni nodo u ∈ V , il cui costo sia minimo,
ovvero più piccolo o uguale del costo di qualunque altro cammino da r a u.
✦
© Alberto Montresor
6
Prospettiva
Cammini minimi da sorgente unica
✦
Input: nodo radice r
✦
Output: i cammini minimi che vanno da r a tutti gli altri nodi v
✦
Cammino minimo tra una coppia di vertici
✦
Input: una coppia di vertici r, d
✦
Output: un cammino minimo fra r e d
✦
Si risolve il primo problema e si estrae il cammino richiesto. Non si conoscono
algoritmi che abbiano tempo di esecuzione migliore.
✦
Cammini mimimi tra tutte le coppie di vertici
✦
Input: il grafo.
✦
Output: i cammini minimi fra tutte le coppie di vertici.
✦
Programmazione dinamica
✦
© Alberto Montresor
7
Problema cammini minimi
Come descrivere l’output:
✦
Si noti che due cammini minimi possono avere un tratto in comune….
✦
r
s
u
v
Non possono convergere in un nodo comune s dopo aver percorso un tratto iniziale
distinto
u
r
s
v
✦
Quindi, una soluzione ammissibile altro non è che un albero di copertura,
radicato in r, che include un cammino da r ad ogni altro nodo.
✦
© Alberto Montresor
8
Esempio
Nella figura
✦
✦
✦
un grafo con un ciclo negativo
✦
un grafo senza cicli negativi
✦
una soluzione ammissibile per G2
✦
una soluzione ottima per G2
Esempio di pesi negativi
Proprietario TIR
✦
Viaggiare carico → profitto
✦
Peso negativo
✦
Viaggiare scarico → perdita
✦
Peso positivo
✦
© Alberto Montresor
9
Caratterizzazione matematica soluzione
Definizione
✦
Sia T una soluzione ammissibile. Ogni nodo u è caratterizzato da un valore du,
che indica la distanza di u da r in T, uguale al costo del cammino fra r ed u in T
✦
Quali caratteristiche devono avere le distanze affinché T sia una soluzione ottima?
✦
Teorema di Bellman
✦
Una soluzione ammissibile T è ottima se e solo se valgono le seguenti condizioni:
✦
dv = du + w(u,v) per ogni arco (u,v) ∈ T
✦
dv ≤ du + w(u,v) per ogni arco (u,v) ∈ E
✦
Dimostrazione
✦
© Alberto Montresor
10
Programma prototipo
Note
✦
Se al termine dell’esecuzione qualche nodo mantiene una distanza infinita,
esso non è raggiungibile da r
✦
Come implementare la condizione ∃ ?
✦
© Alberto Montresor
11
Programma prototipo - maggiori dettagli
© Alberto Montresor
12
Programma prototipo - maggiori dettagli
© Alberto Montresor
13
Algoritmo di Dijkstra (1959)
Struttura dati
✦
Coda con priorità, realizzata tramite vettore ordinato
✦
© Alberto Montresor
14
Algoritmo di Dijkstra (1959)
© Alberto Montresor
15
Algoritmo di Dijkstra
Ipotesi: tutti i pesi sono positivi
✦
Ogni nodo viene estratto una e una sola volta
✦
Al momento dell’estrazione la sua distanza è minima
✦
Costo totale: O(n2)
✦
Costo Ripetizioni
Riga (1): O(n)
1
Riga (2):
O(n)
O(n)
Riga (3):
O(1)
O(n)
Riga (4): O(1)
O(m)
✦
✦
✦
✦
© Alberto Montresor
16
Algoritmo di Johnson (1977)
Struttura dati
✦
Coda con priorità, realizzata tramite Heap binario
✦
© Alberto Montresor
17
Algoritmo di Johnson
Ipotesi: tutti i pesi sono positivi
✦
Ogni nodo viene estratto una e una sola volta
✦
Al momento dell’estrazione la sua distanza è minima
✦
Costo totale: O(m log n)
✦
Costo
Riga (1): O(n)
Ripetizioni
1
✦
Riga (2):
O(log n)
O(n)
Riga (3):
O(log n)
O(n)
✦
✦
Riga (4): O(log n)
✦
© Alberto Montresor
O(m)
18
Algoritmo di Fredman-Tarjan (1987)
Struttura dati
✦
Coda con priorità, realizzata tramite Heap di Fibonacci
✦
© Alberto Montresor
19
Algoritmo di Fredman-Tarjan (1987)
Ipotesi: tutti i pesi sono positivi
✦
Ogni nodo viene estratto una e una sola volta
✦
Al momento dell’estrazione la sua distanza è minima
✦
Costo totale: O(m + n log n)
✦
Costo
Riga (1): O(n)
✦
Ripetizioni
1
Riga (2):
O(log n)
O(n)
Riga (3):
O(log n)
O(n)
✦
✦
Riga (4): O(1)
✦
© Alberto Montresor
O(m)
20
Algoritmo di Bellman - Ford - Moore (1958)
Struttura dati
✦
Coda
✦
www.xkcd.com
© Alberto Montresor
21
Algoritmo di Bellman - Ford - Moore (1958)
Funziona anche con pesi negativi
✦
Ogni nodo viene estratto al massimo n-1 volte
✦
Passata - definizione ricorsiva
✦
per k = 0, la zeresima passata consiste nell’estrazione del nodo r dalla coda S;
✦
per k > 0, la k-esima passata consiste nell’estrazione di tutti i nodi presenti in S al
termine della passata (k − 1)-esima.
✦
Passata k - cammini di lunghezza k
✦
Costo totale: O(mn)
✦
Costo
Riga (1): O(1)
Ripetizioni
1
✦
Riga (2):
O(1)
O(n2)
Riga (3):
O(1)
O(mn)
✦
✦
© Alberto Montresor
22
Algoritmo di Pape - D’Esopo (1974)
Struttura dati
✦
DeQueue
✦
© Alberto Montresor
23
Algoritmo di Pape - D’Esopo (1974)
Tempo di calcolo
✦
In generale, superpolinomiale
✦
In pratica, veloce per grafi che rappresentano reti di circolazione stradale
✦
© Alberto Montresor
24