Newsgroup: it.scienza.informatica
Titolo: Ottimalita' degli algoritmi greedy.

Ciao a tutti,
qualcuno sa come si fa, "in pratica", a determinare se le valgono le due
proprieta' dell'ottimitalita' degli algoritmi greedy?
1) Sottostruttura ottima:
Una soluzione globalmente ottima puo' essere ottenuta effettuando, in
sequenza, delle scelte localmente ottime (greedy).
2) Soddisfacimento scelta greedy:
Una soluzione ottima al problema contiene le soluzioni ottime ai
sottoproblemi
In pratica, avendo degli algoritmi, come devo muovermi per provare queste
proprieta'?
Io faccio davvero fatica a distinguerle.
Esempi:
- come calcoare il numero minimo di banconte necessarie di vario taglio per
cambiare tot euro;
- il problema dello zaino frazionario;
- il problema dello zaino 0-1;
Vi ringrazio anticipatamente per la vostra buona volonta' :)
wigga

 sottoproblemi
Non ho capito cosa vuoi sapere qui...
Spero di esserti stato di un minimo d'aiuto!!
S.

 Io faccio davvero fatica a distinguerle.
Bhè, francamente non ti biasimo: dette così sono spiegate malissimo.
Allora, andiamo con ordine (ma sinteticamente).
Gli algoritmi Greedy si basano sulla teoria (matematica) dei matroidi.
Sul Cormer/Rivest c'è qualche accenno.
Il mio consiglio è di studiarti questa teoria: l'informatica si basa sulla 
matematica (anzi, è una branchia della matematica), e senza non vai 
lontano.
Un matroide è una particolare struttura algebrica (non è una definizione 
esattissima) che gode di particolari ed interessanti proprietà:
Dato un insieme universo U, una proprietà P, un insieme di soluzioni I, 
abbiamo un matroide se
- L'insieme vuoto appartiene alle soluzioni
- Un insieme A contenuto in I è ancora una soluzione (questo coincide con il 
tuo punto 2)
- Vale la proprietà di scambio, ossia prese due soluzioni X ed Y, con 
|X|<|Y|, esiste sempre un elemento y appartenente ad Y che può essere 
aggiunto ad X, con X unito {y} ancora soluzione, ancora appartenente ad I
Per tagliare, un algoritmo greedy risolve all'ottimo un problema se e solo 
se questo è un matroide
Questa la teoria, passiamo alla pratica.
- Zaino 0-1
Da quello che ricordo (scusa, non associo i nomi ai problemi), è il problema 
di scegliere quali pesi prendere e quali non prendere massimizzando il 
valore del carico senza superare un vincolo.
Bene.
Supponiamo di avere i seguei pesi
9Kg (10€), 7Kg (8€), 5Kg (7€), 4Kg (5€)
Possiamo portare fino a 12 Kg.
- Anzitutto l'insieme vuoto appartiene alle soluzioni: se non prendo nessun 
peso, sicuramente porto meno di 12 Kg (banale)
- Un sottoinsieme delle soluzioni è ancora una soluzione: se prendo i pesi 
da 5Kg e da 4Kg (totale 9Kg) che soddisfano la proprietà, prendo un 
sottoinsiene (solo il peso da 4Kg), ho ancora una soluzione, perchè sono 
ancora sotto i 12Kg).
- Sfortunatamente non ho la proprietà di scambio: se prendo il peso da 9Kg, 
cardinalità 1, ed i pesi da 4 e da 5, quindi cardinalità 2, e sposto uno 
dei due nell'insieme formato dal peso da 9, violo la proprietà. Quindi il 
problema dello zaino non è un matroide, non è risolvibile con il greedy.
Cosa farebbe un greedy?
Ovviamente la scelta più "golosa". Sceglierebbe anzitutto il peso da 10€, 
mettendo 9Kg, raggiungendo un insieme massimale. Ma esiste un insieme 
ammissibile di 15€ (formato dai pesi di 7, 5, 4 kg).
Questo viola la tua proprietà 1. Il greedy non risolve all'ottimo questo 
problema.
Come controesempio, passiamo a qualcosa di molto tipico che il greedy 
risolve all'ottimo.
Minimo albero di copertura
- U è l'insieme degli archi
- P è la proprietà che gli archi non formano cicli (ossia l'insieme di archi 
forma una foresta) 
- I è l'insieme degli archi che non contengono cicli
- L'insieme vuoto (ossia nessun arco) è una foresta (definizione)
- Il sottoinsieme di una foresta è una foresta
- Se A e B sono due foreste, se sposto un arco dall'insieme di cardinalità 
maggiore all'altro, ho ancora una foresta.
I due punti da te citati vengono di conseguenza.
Ho cercato di essere sintetico (a costo della chiarezza e precisione)... 
spero però di averti dato almeno uno spunto.
Ciao!
F.

 matematica (anzi, è una branchia della matematica), e senza non vai
                         ^^^^^^^^^^
uhh..allora respira sott'acqua... hihi...
Scusate, non ho saputo resistere...

 F.
Ho letto tutto con attenzione, e ora mi vado a studiare i metroidi.
Grazie mille.. davvero, sei stato forte cavolo ;)
A presto!
wiggy