PDA

View Full Version : Problema dello zaino

ilop
06-09-2005, 14:18
Salve a tutti!
Qualcuno per caso ha la solozione con programmazione greedy del Problema dello Zaino nella sua versione generale, cioè dove è permesso inserire nello zaino anche frazioni di oggetti?
Grazie!
Gica78R
06-09-2005, 18:48
Salve a tutti!
Qualcuno per caso ha la solozione con programmazione greedy del Problema dello Zaino nella sua versione generale, cioè dove è permesso inserire nello zaino anche frazioni di oggetti?
Grazie!
E' la prima volta che sento parlare di programmazione greedy... :confused:
Se puo' esserti utile, ho trovato questi due link:

http://www.disi.unige.it/person/MoggiE/ASD/nota9

http://web.tiscali.it/vitaartificiale/knap.html

Il "Problema dello zaino" credo sia un problema di ottimizzazione, vero? Mi sa che l'ho fatto nel corso di Ricerca Operativa, tanti tanti anni fa :( (ma per noi era il "Problema della sporta" :p ).

Ciao
cionci
06-09-2005, 23:56
Un algoritmo greedy cerca di ottimizzare la funzione facendo scelte ad ogni momento più convenienti rispetto alle altre...

Ad esempio se un algoritmo greedy dovesse percorrere un grafo, ad ogni nodo con più di un percorso sceglierebbe quello di costo minore...
cionci
07-09-2005, 00:02
In pratica un algoritmo grredy ad ogni passo deve sempre effettuare una scelta che determina (se possibile), fra tutte le scelte possibili, quella che permette di ottenere il valore maggiore della funzione da massimizzare...

Hai M oggetti...
Al passo i-esimo hai messo k oggetti nello zaino...
Per arrivare al passo i+1 un algoritmo greedy sceglierà l'oggetto degli M-k rimasti che permette di ottenere il valore più alto della funzione da massimizzare...
Gica78R
07-09-2005, 09:14
In pratica un algoritmo grredy ad ogni passo deve sempre effettuare una scelta che determina (se possibile), fra tutte le scelte possibili, quella che permette di ottenere il valore maggiore della funzione da massimizzare...

Hai M oggetti...
Al passo i-esimo hai messo k oggetti nello zaino...
Per arrivare al passo i+1 un algoritmo greedy sceglierà l'oggetto degli M-k rimasti che permette di ottenere il valore più alto della funzione da massimizzare...
Non c'entra nulla con il backtracking?
Se ad ogni passo fai la scelta che ti massimizza la funzione, non e' detto che si giunga sempre ad una soluzione ammissibile, no? Quindi l'algoritmo deve valutare una situazione del genere e poter tornare indietro per effettuare una scelta differente.
O sono completamente fuori strada?
cdimauro
07-09-2005, 11:18
Il backtracking è un'altra cosa. Gli algoritmi che usano un approccio greedy funzionano esattamente come ha descritto cionci.

Nessuno, però, t'impedisce di usare entrambi gli approcci per cercare di risolvere un determinato problema... ;)
cionci
07-09-2005, 11:34
Non c'entra nulla con il backtracking?
Se ad ogni passo fai la scelta che ti massimizza la funzione, non e' detto che si giunga sempre ad una soluzione ammissibile, no? Quindi l'algoritmo deve valutare una situazione del genere e poter tornare indietro per effettuare una scelta differente.
O sono completamente fuori strada?
La soluzione che raggiungi è sempre ammissibile, ma non sai se è massima o meno...
Puoi anche applicare il backtracking anche ad un algoritmo greedy...ma cmunque per sapere se hai veramente il massimo dovresti ottenere tute le possibili soluzioni...

Supongo che con gli algoritmi genetici sarebbe carino da realizzare...
Fuzzo
21-09-2005, 12:51
Si, l'esame è quello di ricerca operativa :D
La soluzione del problema "rilassato" (frazioni) è questa:


Ordini gli oggetti per utilità/peso decrescenti
Effettui la scelta golosa, ovvero prendi dalla lista ordinata quanti più oggetti possibile fino a raggiungere il peso massimo
Imposti un flag a true se la soluzione è ammissibile, ovvero se non carichi oggetti frazionati
La soluzione con il flag a true e somma delle utilità maggiore è quella ottima (potrebbero essere più di una...)