Algoritmi e Strutture Dati
Capitolo 15 - Ricerca locale
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
Un approccio miope, ma talvolta efficace è quello della ricerca locale
✦
se si conosce una soluzione ammissibile (non necessariamente ottima) ad un
problema di ottimizzazione, si può cercare di trovare una soluzione migliore
nelle “vicinanze” di quella precedente. Si continua in questo modo fino a quando
non si è più in grado di trovare soluzioni migliori
✦
© Alberto Montresor
2
Shell-sort
Definizione
✦
In una sequenza di n elementi a1, ..., an, un’inversione è data da una coppia di
elementi ai e aj tali che i < j e ai > aj.
✦
Il problema dell’ordinamento degli n elementi può essere formulato come problema di
ottimizzazione nel modo seguente:
✦
ordinamento
✦
Data la sequenza a1, . . . , an, trovare una permutazione degli n elementi che
minimizzi il numero totale di inversioni
✦
Esempio:
✦
1,7,3,4 ha due inversioni
✦
1,3,4,7 ha zero inversioni (è ordinata)
✦
© Alberto Montresor
3
Shell-sort
Definizioni
✦
si supponga per semplicità che gli n elementi a1, ..., an siano tutti distinti
✦
sia π una permutazione degli indici 1,...,n
✦
sia aπ la corrispondente permutazione degli elementi.
✦
sia aπ − {ai} la sequenza aπ dalla quale è stato tolto un generico elemento ai.
✦
Un intorno I(aπ) può essere definito come l’insieme di tutte le permutazioni di aπ
che, a meno di un elemento ai, hanno elementi uguali nella stessa posizione relativa:
✦
Criterio di miglioramento
✦
Le sequenze di I(1,7,3,4) che diminuiscono il numero di inversioni sono
1, 3, 7, 4 e 1, 3, 4, 7
✦
© Alberto Montresor
4
Shell-sort
Insertion sort
✦
Lavora riducendo il numero di inversioni nella sequenza originale
✦
Vantaggi
✦
Richiede pochi passi quando la sequenza è “quasi” ordinata (poche inversioni)
✦
Svantaggi
✦
Sposta solo elementi adiacenti fra di loro, eliminando ad ogni passo una sola
inversione
✦
Shell-sort
✦
E’ possibile mantenere i vantaggi di Insertion Sort, eliminando gli svantaggi?
✦
Algoritmo proposto da Shell nel 1959
✦
© Alberto Montresor
5
Shell-sort
Idea
✦
Invece di considerare elementi a distanza 1, considera elementi a distanza...
1093, 364, 121, 40, 13, 4, 1
✦
© Alberto Montresor
6
Shell-sort
Esempio di funzionamento
✦
© Alberto Montresor
7
Shell-sort
Alcuni commenti sulla complessità
✦
© Alberto Montresor
8
Shell-sort
Commenti finali
✦
Valida alternativa ad algoritmi asintoticamente più efficienti per valori di n non
troppo elevati
✦
Ordinamento iterativo, in loco
✦
© Alberto Montresor
9
Problemi di flusso
Rete di flusso
✦
Una rete di flusso G = (V,E,s,p,c) è data da
✦
un grafo orientato G = (V,E),
✦
da una coppia di vertici di V detti sorgente s e pozzo p,
✦
da una funzione di capacità a valori interi positivi c:V ×V →Z+ ∪{0},
tale per cui c(u,v)=0 se (u,v) ∈ E.
✦
Flusso
✦
Una funzione a valori interi f : V × V → Z che soddisfa le seguenti proprietà
✦
Simmetria opposta: f(u, v) = −f (v, u) per ogni coppia u, v ∈ V
✦
Vincolo di capacità: f(u, v) ≤ c(u, v) per ogni coppia u,v ∈ V
✦
Conservazione del flusso: ∑v f(u, v) = 0 per ogni nodo u ∈ V − {s, p}
✦
© Alberto Montresor
10
Definizioni
Valore di flusso
✦
Il valore di un flusso f è la quantità di flusso uscente da s.
✦
Problema flusso massimo
✦
Data una rete G=(V,S,s,p,c), si vuole trovare un flusso f* di valore massimo:
✦
© Alberto Montresor
11
Definizioni
Capacità residua
✦
La capacità residua di un flusso f in una rete G = (V, E, s, p, c) è una funzione
r :V ×V →R+ ∪{0} tale che r(u,v) = c(u,v)−f(u,v).
✦
Rete residua
✦
La rete di flusso residua R=(V, Er, s, p, r) ha lo stesso insieme di nodi, la stessa
sorgente e pozzo, la capacità residua r, mentre l’insieme Er contiene un arco per tutte
le coppie di nodi u,v tali che r(u,v) > 0
✦
Flusso nullo
✦
Un flusso nullo è una funzione f0 :V ×V →R+ ∪{0} tale che f0(u,v) = 0.
✦
Somma di flussi
✦
f1+f2 è una funzione tale per cui (f1+f2)(u,v) = f1(u)+f2(v)
✦
© Alberto Montresor
12
Definizioni
Cammino aumentante
✦
Un cammino aumentante per f è un cammino da s a p in R.
✦
Capacità del cammino
✦
è uguale alla capacità più piccola tra quelle di tutti gli archi (u, v) che compaiono
nel cammino
✦
Flusso aumentante
✦
Dato
✦
un cammino aumentante (u1, u2), (u2, u3), ..., (un-1, un) con s≡u1, p=un, e
✦
la sua capacità δ,
✦
si definisce un flusso aumentante g come segue:
✦
g(ui-1, ui) = δ, g(ui, ui-1) = δ
✦
g(u,v) = 0 altrimenti
✦
© Alberto Montresor
13
Metodo delle reti residue
Idea informale
✦
1.Si costruisce il flusso ottimo a partire da un flusso ammissibile, cercando
nell’intorno di quest’ultimo.
2.Il flusso corrente f viene inizializzato con il flusso nullo f0
3.Si ripeteno le seguenti operazioni
1.Si calcola la rete residua R=(V,E,s,t,cf) ottenuta dalla rete originale sostituendo
la capacità residua alla capacità originale
2.Si cerca un flusso aumentante g per R
3.Si somma g ad f
4.finché g ≠ f0
© Alberto Montresor
14
Metodo delle reti residue
© Alberto Montresor
15
Versione in Java
© Alberto Montresor
16
Versione in Java
© Alberto Montresor
17
Esempio
© Alberto Montresor
18
Esempio
© Alberto Montresor
19
Taglio
Definizioni
✦
Un taglio (S,P) è una partizione dell’insieme dei nodi tale che
s∈S, p∈P, S∪P =V, ed S∩P =∅.
✦
La capacità del taglio è c(S, P ) = ∑u∈S,v∈P c(u, v).
✦
Un taglio di capacità minima è detto taglio minimo.
✦
Se f è un flusso ed (S, P) è un taglio, allora il flusso che attraversa il taglio è
✦
© Alberto Montresor
20
Alcune proprietà interessanti
Lemma
✦
Il valore di un flusso è uguale al flusso che attraversa un qualsiasi taglio, il quale a
sua volta non supera la capacità del taglio stesso, cioè che |f| = f(S,P) ≤ c(S,P)
✦
Dimostrazione: alla lavagna
✦
Teorema (flusso massimo / taglio minimo)
✦
Le condizioni seguenti sono tra loro equivalenti:
1. f è un flusso massimo
✦
2. non esiste alcun cammino aumentante per f
3. esiste un taglio (S,P) tale che |f| = c(S,P)
Dimostrazione: alla lavagna
✦
© Alberto Montresor
21
Alcune varianti
Ford-Fulkerson (1956)
✦
Si trova un cammino aumentante utilizzando un qualunque algoritmo di visita
✦
Assume che la capacità siano intere
✦
Ogni cammino aumentante aumenta il flusso di almeno 1
✦
Complessità: O(|f*| (m+n)) (valore del flusso massimo × costo di una visita)
✦
Edmonds-Karp (1972)
✦
Basato su visite in ampiezza
✦
Complessità: O(nm2)
✦
Nota: caso particolare di Ford-Fulkerson, vale il limite superiore più stretto
✦
Algoritmo dei tre indiani (Kumar, Malhotra, Maheswari, 1978)
✦
Complessità: O(n3)
✦
© Alberto Montresor
22