(C)Problema ricorsivo di calcolo combinatorio
Salve a tutti, ho il seguente problema e vorrei trovare un algoritmo per risolverla :
Dati n oggetti ognuno con peso diverso, trovare un modo per distribuire
gli oggetti in j scatole (j
esempio:
ho questi tre oggetti A(1) B(2) C(3) e le scatole X e Y, visto che le
scatole sono identiche(specificato nel testo del problema)
per una distribuzione equa potrei fare in questo modo
X{A,B} e Y={C}
In questo momento sto pensando di modelare questo algoritmo
attorno ad una combinazione semplice di \binom {n} {k} con k
che varia da 2 a n-1, utilizzando anche un array di bit per segnare
ogni volta gli oggetti che decido di raggruppare.
I dubbi che mi sorgono adesso e' se questa problema si puo'
ottimizzare in qualche modo(backtracking) e se come approccio
e' giusto.
Dati n oggetti ognuno con peso diverso, trovare un modo per distribuire
gli oggetti in j scatole (j
esempio:
ho questi tre oggetti A(1) B(2) C(3) e le scatole X e Y, visto che le
scatole sono identiche(specificato nel testo del problema)
per una distribuzione equa potrei fare in questo modo
X{A,B} e Y={C}
In questo momento sto pensando di modelare questo algoritmo
attorno ad una combinazione semplice di \binom {n} {k} con k
che varia da 2 a n-1, utilizzando anche un array di bit per segnare
ogni volta gli oggetti che decido di raggruppare.
I dubbi che mi sorgono adesso e' se questa problema si puo'
ottimizzare in qualche modo(backtracking) e se come approccio
e' giusto.
Risposte
Ciao,
va bene che di probabilità non ho ancora finito il corso, sicuro che sia una Binomiale?
Essendoci i pesi, che rendono distinguibili gli oggetti a me pare può essere una statistica di Maxwell-Boltzmann...
Il backtracking in questi casi è una buona idea, appena capito che statistica o distribuizione sia (ci sono altre tecniche, ma più complesse, il backtracking per la sua semplicità è molto buono)
va bene che di probabilità non ho ancora finito il corso, sicuro che sia una Binomiale?
Essendoci i pesi, che rendono distinguibili gli oggetti a me pare può essere una statistica di Maxwell-Boltzmann...
Il backtracking in questi casi è una buona idea, appena capito che statistica o distribuizione sia (ci sono altre tecniche, ma più complesse, il backtracking per la sua semplicità è molto buono)
Innanzitutto dovresti precisare meglio il problema: cosa vuol dire distribuzione equa dei pesi? Le scatole devono essere riempite con l'esatto stesso peso oppure può non essere possibile e quindi è necessario minimizzare qualche funzione di costo?
Ad ogni modo, il problema sembra essere NP-completo (è una generalizzazione di partition) fortunatamente però partition ammette un algoritmo pseudopolinomiale. Il problema è che l'algoritmo di partiton (che è in sostanza lo stesso di subset sum) lavora con solo due scatole. Secondo me puoi fare in questo modo: sia $N$ la somma totale dei pesi degli oggetti da inserire; calcoli gli oggetti da inserire nella prima scatola con l'algoritmo per subset sum in modo che il sottoinsieme scelto dall'algoritmo sommi a $N/j$ e ripeti l'algoritmo per ogni scatola con gli oggetti rimanenti.
Ad ogni modo, il problema sembra essere NP-completo (è una generalizzazione di partition) fortunatamente però partition ammette un algoritmo pseudopolinomiale. Il problema è che l'algoritmo di partiton (che è in sostanza lo stesso di subset sum) lavora con solo due scatole. Secondo me puoi fare in questo modo: sia $N$ la somma totale dei pesi degli oggetti da inserire; calcoli gli oggetti da inserire nella prima scatola con l'algoritmo per subset sum in modo che il sottoinsieme scelto dall'algoritmo sommi a $N/j$ e ripeti l'algoritmo per ogni scatola con gli oggetti rimanenti.
"Deckard":
sia $N$ la somma totale dei pesi degli oggetti da inserire; calcoli gli oggetti da inserire nella prima scatola con l'algoritmo per subset sum in modo che il sottoinsieme scelto dall'algoritmo sommi a $N/j$ e ripeti l'algoritmo per ogni scatola con gli oggetti rimanenti.
ma messo in questo modo non è il problema dei cassetti o dei camion (dipende dal testo)?
Non saprei, lo conosco probabilmente col suo nome inglese quindi non so a quale problema ti riferisca; forse bin packing? Se è così la risposta è: ci assomiglia, ma in quel caso la dimensione delle scatole è finita. Il problema è più simile a partition.
@Deckard
Con distribuzione equa intendo una distribuzione ottimale, per esempio se ho tre scatole e tre oggetti diciamo di pesi 2 3 4, la distribuzione ottima e' un oggetto per ogni scatola, in modo da minimizzare il peso massimo di ogni scatola in parte (qua per minimizzare il peso massimo di una scattola distribuisco gli oggetti in tuttle le scatole, dato che mettendo quelli di peso 2 e 3 nella seconda scatola otterei come peso totale della stessa 5 che e' maggiore di 4)
Inoltre leggendo gli altri post stavo pensando, ricorsivamente di cominciare con gli oggetti di peso massimo e poi andare in modo discendente, mettendo un oggetto per scatola, quando ho finito le scatole, partire dal oggetto di peso minore, metterlo nella scatola dell'oggetto di peso massimo e ripetere l'operazione per le altre scatole ma percorrendo l'array di oggetti questa volta in modo ascendente(anche se in questo caso ho paura di finire in una soluzione di tipo greedy).
Con distribuzione equa intendo una distribuzione ottimale, per esempio se ho tre scatole e tre oggetti diciamo di pesi 2 3 4, la distribuzione ottima e' un oggetto per ogni scatola, in modo da minimizzare il peso massimo di ogni scatola in parte (qua per minimizzare il peso massimo di una scattola distribuisco gli oggetti in tuttle le scatole, dato che mettendo quelli di peso 2 e 3 nella seconda scatola otterei come peso totale della stessa 5 che e' maggiore di 4)
Inoltre leggendo gli altri post stavo pensando, ricorsivamente di cominciare con gli oggetti di peso massimo e poi andare in modo discendente, mettendo un oggetto per scatola, quando ho finito le scatole, partire dal oggetto di peso minore, metterlo nella scatola dell'oggetto di peso massimo e ripetere l'operazione per le altre scatole ma percorrendo l'array di oggetti questa volta in modo ascendente(anche se in questo caso ho paura di finire in una soluzione di tipo greedy).
"Deckard":
Non saprei, lo conosco probabilmente col suo nome inglese quindi non so a quale problema ti riferisca; forse bin packing? Se è così la risposta è: ci assomiglia, ma in quel caso la dimensione delle scatole è finita. Il problema è più simile a partition.
esatto "Bin packing" problema 35-1 del Cormen
Mi ero dimenticato della infinitezza delle scatole...
In questo caso allora, il backtracking non è applicabile. Bisogna utilizzare altre tecniche...sempre legate alla miglior definizione del problema.
Inoltre leggendo gli altri post stavo pensando, ricorsivamente di cominciare con gli oggetti di peso massimo e poi andare in modo discendente, mettendo un oggetto per scatola, quando ho finito le scatole, partire dal oggetto di peso minore, metterlo nella scatola dell'oggetto di peso massimo e ripetere l'operazione per le altre scatole ma percorrendo l'array di oggetti questa volta in modo ascendente(anche se in questo caso ho paura di finire in una soluzione di tipo greedy).
Secondo me la tua soluzione non è molto efficace: meglio ordinare i pesi in maniera decrescente e inserire di volta in volta l'oggetto più pesante rimasto nella scatola più vuota.
alla fine ragazzi ho trovato un algoritmo su cui modelare il mio problema
http://en.wikipedia.org/wiki/Multiprocessor_scheduling
grazie a tutti per il contributo.
http://en.wikipedia.org/wiki/Multiprocessor_scheduling
grazie a tutti per il contributo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo