* GREEDY METHOD ABBIAMO UN PROBLEMA SU UN INSIEME DI n ELEMENTI
OGNI ELEMENTO E’ DOTATO DI UN INSIEME DI PROPRIETA' CHE NE DEFINISCONO COSTO, QUANTITA', UTILITA’, ...
LA SOLUZIONE DEL PROBLEMA RICHIEDE DI IDENTIFICARE UN SOTTOINSIEME (o comunque una strutturazione) DI QUESTO INSIEME CHE
SODDISFI CERTI VINCOLI (LEGATI ALLE PROPRIETA' DEGLI ELEMENTI)
MASSIMIZZI (O MINIMIZZI) UNA CERTA FUNZIONE OBBIETTIVO (LEGATA ALLE PROPRIETA' DEGLI ELEMENTI)
* GREEDY METHOD IL METODO GREEDY (avido, avaro) SUGGERISCE DI
1. Ordinare gli elementi dell'insieme secodo una funzione ottimizzante legata alle loro proprieta' e valutabile indipendentemente per ciascun elemento.
2. Partire da una soluzione parziale data dall'insieme vuoto.
3. Scandire uno per uno gli elementi dell'insieme ordinato (nel passo 1) decidendo per ciascuno di essi se inserirlo nella soluzione o scartarlo, in base al fatto che la soluzione parziale ottenuta aggiungendolo sia o no legittima.
Perche' la soluzione cosi' ottenuta sia effettivamente ottima bisogna che la funzione ottimizzante di ordinamento sia adeguata,
adeguata rispetto al problema
adeguata rispetto alle proprieta' degli elementi.
* GREEDY METHOD struct item {
string nome;
struct { … } attributes; };
void greedy(int sizData, struct item data[],
struct item res[], int *sizRes) {
*sizRes = 0;
sort(data, sizData);
int i = 0;
while (i < sizData) {
if (feasible(res, sizRes, data[i])) {
res[*sizRes] = data[i];
*sizRes += 1;
}
i += 1;
}
}
* GREEDY METHOD feasible() DETERMINA SE (all'i-esima iterazione) LA SOLUZIONE OTTENUTA AGGIUNGENDO data[i] ALLA SOLUZIONE PARZIALE OTTENUTA FINO AD ALLORA (cioe' res[0..sizRes-1]) E' ANCORA LEGITTIMA
* GREEDY METHOD: esempio KNAPSACK Problema Knapsack
SONO DATI n OGGETTI E UNO ZAINO
L'OGGETTO i HA
PESO (“specifico”) w[i] (>0)
UTILITA' (“specifica”) p[i] (>0)
LO ZAINO HA CAPACITA' m LIMITATA
OGNI OGGETTO i PUO' ESSERE PRESO IN QUANTITA' x[i] CON 0 x 1
BISOGNA METTERE OGGETTI NELLO ZAINO IN MODO DA MASSIMIZZARE L'UTILITA' DEL SUO CONTENUTO:
massimizzare p[i]*x[i] con il vincolo w[i]*x[i] m
OGNI SOLUZIONE PER ESSERE ACCETTABILE DEVE SODDISFARE IL VINCOLO i=0 n-1 i=0 n-1
* GREEDY METHOD: esempio KNAPSACK E' OVVIO CHE LA SOLUZIONE OTTIMA RIEMPIE COMPLETAMENTE LO ZAINO
(il problema esiste ovviamente solo quando w[i] > m)
SI POSSONO CONSIDERARE DIVERSE FUNZIONI OTTIMIZZANTI DI ORDINAMENTO DI data:
1. Ordinare gli elementi secondo l’utilita’ (decrescente)
2. Ordinare gli elementi secondo il peso (crescente)
3. Ordinare gli elementi secondo il rapporto utile/peso (p/w) (decrescente)
E' FACILE VEDERE CHE NE' IL CRITERIO 1 NE' IL CRITERIO 2 PORTANO (SEMPRE) ALLA SOLUZIONE OTTIMA
IL CRITERIO 3 INVECE RISOLVE SEMPRE IN MODO OTTIMO IL PROBLEMA DEL KNAPSACK i=0 n-1
* GREEDY METHOD: esempio KNAPSACK struct item {
int nome; // nome >= 0
float p;
float w;};
struct itemInSack {
int nome;
float x;}; // 0 <= x <= 1
void greedyKnapack
(int n, struct item data[],
float capacity, // m
struct itemInSack result[])
{
int i;
// continua alla prossima pagina
* GREEDY METHOD: esempio KNAPSACK L'algoritmo di per se stesso non cambia al cambiare della funzione ottimizzante di ordinamento:
cambia solo la procedura sort() che esegue l'ordinamento.
Ovviamente cambia anche il risultato finale!
Quale e' la complessita' di greedy?
Di per se stesso greedy e' lineare: O(n)
(almeno nell'ipotesi che il calcolo della nuova soluzione parziale avvenga in tempo costante)
Ma comprende una procedura di ordinamento!
Se questa e' O(n*log(n)), greedy diventa anch'esso O(n*log(n))
In realta' a noi basterebbe meno dell'ordinamento: basterebbe uno heap come in heapsort, pero' poi bisogna comunque mantenerlo, il che ci riporta a O(n*log(n)).
* GREEDY METHOD: esempio KNAPSACK Teorema: la soluzione trovata con il criterio di ordinamento basato sulla massimizzazione del rapporto p[i]/w[i] e' ottima
Dimostrazione:
Sia x = [x0, …, xn-1] la soluzione fornita da greedyKnapsack().
Per come funziona l'algoritmo c'e' un valore j per il quale:
(k| 0k p[i]*x[i] (in realta’ )
in ogni caso posso assumere che lo zaino debba essere pieno:
w[i]*x[i] = m w[i]*y[i] = m i=0 n-1 i=0 n-1 i=0 n-1 i=0 n-1
* GREEDY METHOD: esempio KNAPSACK Dimostrazione (continua):
Consideriamo l'indice minimo k per cui e’ y[k]x[k]
Di necessita' sara' y[k]j e' impossibile, perche' lo zaino e' gia' pieno con i primi j+1 elementi, dato che k | 0kj : y[k]=x[k], e i primi j+1 elementi di x riempiono lo zaino
Allora pensiamo di modificare y facendo diventare y[k]=x[k]: per fare cio' diminuiremo in modo arbitrario i valori y[l] per l>k in modo da rispettare il vincolo di non overflow pur continuando a riempire lo zaino.
In questo modo otteniamo una nuova soluzione z che e' uguale a x fino all'indice k (e uguale a y fino all'indice k-1).
* GREEDY METHOD: esempio KNAPSACK Dimostrazione (continua):
La maggiorazione deriva dal fatto che, per il criterio ottimizzante di ordinamento utilizzato, risulta:
i | k
* GREEDY METHOD: esempio Minimum Cost Spanning Tree Consideriamo un grafo G = (V, E) non diretto e connesso, dove ad ogni lato e' associato un costo
Un suo spanning tree S = (V, T) e' un albero non diretto che connette tutti i nodi del grafo, e che ha come lati dei lati del grafo (cioe' T E)
N.B.: di quanti lati e’ composto T?
#V - 1
* GREEDY METHOD: esempio Minimum Cost Spanning Tree v1V, v2V : ! percorso in T che li congiunge.
Dim: Tra due nodi di un albero non diretto un percorso c'e' per forza (per definizione dalla radice dell'albero c'e' un percorso sia per raggiungere v1 che per raggiungere v2). Ce ne e' uno solo, altrimenti ci sarebbe un ciclo, e un albero non ha cicli.
Come e’ fatto il percorso? 1. risalgo da v1 al primo antenato comune 2. scendo fino a v2
Se a T aggiungo un altro lato di E (cioe' un lato l E-T) si ottiene un grafo con uno e un solo ciclo.
Dim: dato che c'era gia' un percorso tra i due nodi agli estremi del lato, aggiungendo questo lato si crea un ciclo.
Il ciclo e' unico perche' il percorso stesso era unico.
* Esempio Minimum Cost Spanning Tree: strategia di soluzione greedy V e’definito.
Costruisco T a partire da un insieme di lati vuoto, e aggiungendo man mano un lato per volta.
Aggiungendo lati a T lo mantengo a costo minimo, dato il numero corrente dei suoi lati.
N.B.: per come lo (ri-)costruisco, durante l’esecuzione della procedura T non si presentera’ come un grafo connesso (un albero) ma piuttosto come una foresta, che solo alla fine sara’ riunificata in un albero.
Quindi, i lati da aggiungere li ordino per costo crescente.
Constraint: aggiungendo un lato a T, T deve rimanere una foresta, cioe’ non devo creare dei cicli.
* GREEDY METHOD: esempio Minimum Cost Spanning Tree Una spanning forest su G e' un insieme di alberi non diretti
{ (V1, T1), (V2, T2), …, (Vk, Tk) } in cui
V1 V2 ..., Vk = V
ij Vi Vj =
i | 1ik : Ti E
consideriamo una foresta di almeno 2 alberi e sia
T = T1 T2 ... Tk
sia e = (v, w) un lato di costo minimo in E-T tale che se vVm allora wVm (per un qualche m1..k).
allora:
Teorema: c'e' uno spanning tree che include T {e} che e' di costo non maggiore di qualsiasi spanning tree che includa T
Dimostrazione: vedi prossima pagina.
* GREEDY METHOD: esempio Minimum Cost Spanning Tree Dimostrazione: per assurdo.
Sia S' = (V, T') uno spanning tree tale che TT' ed eT'.
Supponiamo (per assurdo) che il costo di T' sia minore del costo di tutti gli spanning tree che includono anche e.
Se aggiungo e a T' ottengo un ciclo: nel ciclo sono compresi sia nodi di Vm che nodi non di Vm, e quindi un altro lato e' con un estremo in Vm e uno non in Vm (N.B.: quindi e'T).
Per ipotesi e' costa non meno di e.
Consideriamo il grafo S = ( V, T' - { e' } { e } ):
questo grafo non ha cicli, perche' l'unico ciclo che aveva e' stato interrotto dalla rimozione di e'
tutti i suoi nodi sono connessi, dato che abbiamo creato un percorso alternativo a e' passando per e
Percio' S e' uno spanning tree di costo minore o uguale ad S' e contiene sia T che e.
* GREEDY METHOD: esempio Minimum Cost Spanning Tree set kruskal(set V, set E) {
set T = ;
set> VS = {{v} : vV};
// VS rappresenta la spanning forest
// ogni suo elemento e' un albero della
// foresta
edge heapOfEdges[?];
// questo non e' proprio legale in C ma lo
// abbiamo gia' fatto e spiegato in radixSort()
node v, w;
set V1, V2;
buildPriorityList(E, heapOfEdges);
// uno heap come in heapsort, in cui la
// radice e' l'elemento minimo
Comments