Newsgroup: it.scienza.informatica
Titolo: algoritmo dello zaino modificato

Ciao Ragazzi volevo proporvi un problema che rassomiglia un pò al problema 
dello zaino in programmazione dinamica. Praticamente io ho una montagna di 
mp3 di dimensione varia,quello che mi serve è un algoritmo che produca in 
output n liste di mp3 distinte, dove n sarebbe il numero minimale di cd 
necessari per masterizzare tutti gli mp3.E'chiaro che un mp3 che compare in 
una lista non deve comparire in nessun altra! Io penso che sia simile al 
problema dello zaino discreto, solo che in questo caso abbiamo n 
zaini.Ovviamente la soluzione andrebbe bene anche nel caso di DVD, in 
pratica io dovrei dare in input la dimensione del supporto, la cartella o le 
cartelle contenenti i files e in output dovrei avere il numero di supporti 
necessari e le liste dei file da masterizzare in ognuno dei supporti! Io mi 
sto scervellando da un mese se qualcuno ha un idea... 

 necessari per masterizzare tutti gli mp3
Per la cronaca questo problema rientra nel vasto campo del
BIN PACKING (cercare con google).
Per un problema cosi' semplice penso tu possa anche lasciare
perdere soluzioni sofisticate. E' difficile che una scelta
lievemente subottimale faccia aumentare di 1 il numero di CD
o DVD ottimali. (dovrebbe proprio essere un caso in cui
gli mp3 riempiono quasi esattamente i supporti)
Io a suo tempo ho avuto un problema simile e ho usato con
successo una semplice euristica che non garantisce l'ottimalita',
ma sicuramente si avvicina, considerando che di solito
gli mp3 sono piccoli rispetto agli "zaini" in cui vuoi ficcarli.
Non ricordo esattamente il metodo che ho usato, so solo
che ci avro' messo mezzora a programmarlo e funzionava
accettabilmente.
Piu' o meno avrebbe potuto essere cosi':
Mettevo gli mp3 in ordine dal piu' grande al piu'
piccolo (per provare a mettere prima a posto quelli
grandi che sono i piu' difficili).
A questo punto riempivo un disco alla volta,
indipendentemente.
Per riempire un disco ci mettevo dentro tutti
i pezzi possibili (andando in ordine di dimensione
decrescente) tra quelli disponibili, poi effettuavo
una piccola ottimizzazione locale in questo modo:
se il CD corrente aveva un spazio libero minore di
una certa soglia allora lo davo per buono, altrimenti
andavo a vedere, per ogni brano nel CD, se esisteva
una coppia di brani nella lista la cui lunghezza complessiva
era maggiore del brano in esame, ma minore di brano+spazio
libero. In questo modo sostituendo la coppia trovata al
brano in esame miglioravo l'impaccamento.
Questa procedura veniva iterata, fino a che lo
spazio libero era sopra la soglia ed era
possibile trovare una tripla (brano nel CD e 2 brani
nella lista) che miglioravano l'impaccamento.
Una volta completato un CD con questo sistema,
passavo a riempirne un altro, fino ad esaurimento.
Se i brani nella lista sono tanti, tipo
migliaia e migliaia, o se se usi un linguaggio
di programmazione "lento", allora invece di controllare
tutte le possibile triple (che sono potenzialmente molte,
per esempio se in un CD ci stanno 100 mp3 e se hai 10.000 brani
da mettere a posto avrai circa 100x10.000x10.000 controlli da
fare, cosa assolutamente improponibile,
allora conviene stabilire a priori che non confronti tutte
le possibili coppie, ma un certo numero di coppie scelte
a caso (che dipendera' idealmente dagli altri parametri).
Su questa falsariga puoi inventarti decine di euristiche simili.
Per esempio puoi usare questo metodo ancora piu'
semplice:
metti in ordine decrescente di lunghezza gli mp3.
poi iterativamente, per ogni brano:
(dovrebbe essere la strategia first-fit)
metti il brano nel primo CD "gia' iniziato" nel
quale entra. Se non entra in nessun CD "gia' iniziato"
crei un nuovo CD e ci metti il brano.
Prosegui cosi' fino ad esaurire i brani.
(al primo passo, non essendoci CD "gia' iniziati",
ne creerai ovviamente uno).
Qui puoi introdurre modifiche:
invece di ficcare il brano nel PRIMO cd nel
quale entra puoi metterlo nel cd nel quale
entra MEGLIO (cioe' lascia meno spazio libero).
Oppure invece di ordinare i brani in modo
decrescente puoi metterli a caso e
applicare la semplice euristica sopra 1000
volte e scegliere il risultato migliore
in termini di numero di CD.
E' chiaro che se per motivi puramente di
lunghezza gli MP3 occupano 12 CD e mezzo
e tu trovi un impaccamento anche non ottimale
in termini dei singoli riempimenti, che occupa
13 CD allora hai comunque trovato una soluzione
ottimale e ti puoi fermare.
ciao,
g.


Scusa, forse non ho capito bene il problema, ma se l'ho capito la 
soluzione è banale.
Iteri n volte l'algoritmo per lo zaino discreto.
Dov'è che sbaglio?

 Dov'è che sbaglio?
Effettivamente a pensarci con un po' di + calma, il problema non è così 
semplice come mi era sembrato a primo impatto. Ho capito perché iterare 
n volte lo zaino disceto non produce un risultato ottimale. Se trovo 
tempo in questi giorni ci penso un po'... vedremo.

Capitan Harlock ha scritto:

Ummm... credo che una soluzione si possa trovare(usando una variante del 
problema dello zaino binario...) però è comunque sbagliata perchè una 
persona NORMALE raggruppa gli mp3 in base al gruppo o al tipo di musica 
non alla dimensione !!. Una variante interessante che riduce la 
dimensione del problema è come mettere vari gruppi di mp3 dentro ad un 
cd in modo ottimale.
Markone.
ByebYe

 cd in modo ottimale.
Esattamente il problema che ho avuto io: si trattava di trovare, dato un
insieme di album, il sottoinsieme che meglio utilizzasse lo spazio di un cd.
Non avevo tempo di studiare il metodo dello zaino, e ho risolto col
brute-force: dati n album, prendo i numeri da 1 a 2^n, in notazione binaria
(che mi rappresenta la presenza, 1, o meno, 0, dell'album i-esimo), da cui
poi calcolavo l'occupazione di questa "rappresentazione"; viene scelta che
minimizza lo spazio sprecato sul cd.
E' un metodo lento alla morte (con 22 album su un PIII a 866MHz impiega
circa 2 minuti per trovare la soluzione) in quanto esponenziale, ma la
precisione e' assicurata: viene *sicuramente* scelta la configurazione
migliore, in quanto le analizzo *tutte*.
Non e' dunque applicabile per un numero elevato di elementi (centinaia di
mp3 singoli).
Dal momento che sono in fase di migrazione ai dvd, questo algoritmo non e'
piu' utilizzabile. Aspetto quindi qualche soluzione interesante da questo
thread.
Ciao

 
Esiste FillCD (
www.fillcd.com
) e ho visto che come algoritmo usa quello 
"dal più grosso al più piccolo". Comunque una soluzione accettabile l'ha 
proposta "Caro Estintore" (strategia first-fit credo ).
M.

 proposta "Caro Estintore" (strategia first-fit credo ).
Si, mi sembra di avere proposto una first-fit. Poi uno puo' fare 
eventualmente dei raffinamenti con delle ricerche locali iterate 
casuali. Mi sembra di averne proposta una. Ora cerco di fare un
discorso piu' generale.
Una volta che uno ha ottenuto una soluzione, puo' provare
a vedere se, per esempio, scambiando una coppia di brani (ovviamente su 
2 CD diversi) o spostandone 1 da un disco ad un altro si ottiene
un miglioramento della funzione da minimizzare (che sara' per esempio
una funzione dello spazio vuoto complessivo, magari pesata in modo
da favorire l'insorgenza di molti dischi con poco spazio vuoto ed
un unico disco (quello magari mezzo pieno) con molto spazio vuoto.
Quindi come dicevo, fissata questa funzione da ottimizzare, e partendo
da una prima soluzione ottenuta molto rapidamente con un first-fit o un
best-fit (vedasi gli algoritmi di "bin packing"),
si stabilisce un criterio in base al quale si passa da una soluzione
corrente ad una soluzione modificata (scambio, spostamento).
Si genera la soluzione modificata e si vede se la soluzione cosi'
ottenuta e' migliore (in base alla funzione da ottimizzare). Se e'
migliore si prende come nuovo punto di partenza mentre se e' peggiore si 
prova un altra modifica. E cosi' via fino a che si arriva ad un
punto in cui queste modifiche semplici (quindi in un certo senso locali,
visto che non cambiano globalmente la soluzione corrente) non possono
essere applicate ulteriormente per migliorare la soluzione.
Saremo cosi' arrivati ad un ottimo locale, che non sara' quasi 
sicuramente uguale all'ottimo globale, ma probabilmente migliore
di quello da cui siamo partiti.
Questo procedimento si puo' applicare con tante varianti a molti
problemi di ottimizzazione discreta. Ha il vantaggio (rispetto
ad una euristica molto furba o alla ricerca esaustiva della soluzione)
di usare come punto di partenza una soluzione ottenibile facilmente
(velocemente) e che di solito non e' pessima. E poi raffina la soluzione
con un meccanismo elementare che puo' essere iterato velocemente
milioni di volte. Un ulteriore raffinamento di questa ricerca locale
iterata consiste nella possibilita' di accettare come nuovo punto
di partenza una soluzione un po' peggiore di quella corrente (con una
probabilita' piccola che dipendera' da vari fattori). Questo meccanismo
che rientra nel filone del "simulated annealing" ha il pregio di 
permettere (per certi problemi, non so se vale anche nel caso del
bin packing) di "sfuggire" da un ottimo locale non tanto buono 
accettando una soluzione un po' peggiore che pero' non essendo un ottimo
locale e' ancora passibile di miglioramento.
scusate la prolissita'...
ciao,
g.

 proposta "Caro Estintore" (strategia first-fit credo ).
L'algoritmo proposto da Caro Estintore puo' andar bene nel caso di un gran
numero di file (una collezione di mp3, che mi posso anche ottimizzare "ad
occhio"...) ma nel caso di file di grandi dimensioni, vorrei poter avere la
*migliore* configurazione possibile. Ed ho paura che l'unico modo si andare
di full scan.
Ciao