[C] algoritmo partizionamento equiripartito

[misterx]

il titolo è un pò strano e pur avendo studiato diversi algoritmi non ho memoria di quale usare per risolvere un problema di tale tipo.

Ho un certo numero di pesi: 1 Kg, 2 Kg, 10 Kg etc... di peso ignoto e voglio equiripartire tali pesi in ad esempio 3 contenitori uguali in modo che ogni contenitore possegga circa il medesimo peso.

Di primo acchito ho pensato:

1 + 2 + 10 : 3 = 4,..... quindi ogni contenitore deve contenere almeno 4 Kg

Siccome l'esempio è brutto avrei che il primo contenitore conterrebbe 1 Kg, il secondo 2 Kg ed il terzo 10 Kg in quanto i pesi dati non sono suddivisibili materialmente.

Potrei avere allora: 2, 33, 16, 22, 45, 100, 48, 25, 67, 55 etc....

2+33+16+22+45+100+48+25+67+25 : 3 = 137,6666 (138)

ora dovrei trovare tre gruppi che si avvicinino a 138 per equiripartire: come faccio?

grazie

[fero86]

scusa ma il problema andrebbe decisamente formulato meglio. cosa vuol dire che hai "un certo numero di pesi di peso ignoto"? cos'é il peso di un peso?
e soprattutto cosa vuol dire "circa il medesimo peso"?

edit - provo a rispondere da solo a questa mia ultima domanda. diciamo che il tuo scopo é minimizzare il peso finale contenuto in ogni contenitore, giusto? in questo caso la soluzione non é unica perché potrebbero presentartisi dei tradeoff; per esempio supponi di avere 3 pesi da 1 kg ciascuno e di doverli mettere in due contenitori: le due soluzioni sono ({1, 1}, {1}) e ({1}, {1, 1}).

[misterx]

Originariamente inviato da fero86

scusa ma il problema andrebbe decisamente formulato meglio. cosa vuol dire che hai "un certo numero di pesi di peso ignoto"? cos'é il peso di un peso?
e soprattutto cosa vuol dire "circa il medesimo peso"?

ciao,
significa che il peso dei dati in ingresso può variare di volta in volta; questo per evitare di scrivere una sorta di algoritmo che risolverebbe solo quel tipo di problema, come nel mio esempio per intenderci.

Circa il medesimo peso significa che una volta calcolato il peso suddiviso per i tre contenitori, non importa che il peso di ognuno sia precisamente quello ottenuto con somma e divisione, ma che ci si avvicini il più possibile.

A me è venuto in mente un approcio greedy:
- ordino i dati in ingresso
- prendo l'ultimo e lo sommo al primo
- se minore del valore atteso, sommo anche il secondo da sinistra e mi fermo quando è <= a quello atteso (138 dell'esempio)

- prendo il secondo velore da destra e ripeto

il problema è che è una approssimazione banalotta e non la migliore possibile

[fero86]

Originariamente inviato da misterx

significa che il peso dei dati in ingresso può variare di volta in volta; questo per evitare di scrivere una sorta di algoritmo che risolverebbe solo quel tipo di problema, come nel mio esempio per intenderci.

tralascio perché non ci ho capito un'acca

A me è venuto in mente un approcio greedy:
- ordino i dati in ingresso
- prendo l'ultimo e lo sommo al primo
- se minore del valore atteso, sommo anche il secondo da sinistra e mi fermo quando è <= a quello atteso (138 dell'esempio)

- prendo il secondo velore da destra e ripeto

il problema è che è una approssimazione banalotta e non la migliore possibile

a me non sembra greedy...
quale sarebbe la scelta locale migliore?


ti faccio un esempio di algoritmo greedy: iteri sui pesi e per ogni peso scegli il contenitore in cui metterlo in base al criterio greedy. un esempio di criterio greedy é di scegliere il contenitore con meno peso.

[misterx]

Originariamente inviato da fero86

tralascio perché non ci ho capito un'acca



a me non sembra greedy...
quale sarebbe la scelta locale migliore?


ti faccio un esempio di algoritmo greedy: iteri sui pesi e per ogni peso scegli il contenitore in cui metterlo in base al criterio greedy. un esempio di criterio greedy é di scegliere il contenitore con meno peso.

eppure non mi sembra di essere così poco chiaro, sarà l'orario.
Se proseguivo col mio esempio si notava meglio l'algoritmo greedy, algoritmo che dovrebbe procedere sino ad ottenere la soluzione ottima pur intraprendendo una strada(numero di somme) NON ottima(ricordo vagamente il problema del resto e simili).
Ma greedy è goloso e si accontenta di raggiungere alla soluzione anche se non ottima.
Per fare un esempio: se dovesse arrivare a 138 Kg, prenderebbe 100+qualcosa+qualcosa d'altro sino a raggiungere 138 ma non è detto che sia l'unica e la soluzione migliore in quanto potrebbero esisterne altre ancora migliore: così dovrebbe andare meglio.

Ma non abbiamo ancora risolto il mio problema.

Originariamente inviato da fero86

tralascio perché non ci ho capito un'acca



a me non sembra greedy...
quale sarebbe la scelta locale migliore?


ti faccio un esempio di algoritmo greedy: iteri sui pesi e per ogni peso scegli il contenitore in cui metterlo in base al criterio greedy. un esempio di criterio greedy é di scegliere il contenitore con meno peso.

eppure non mi sembra di essere così poco chiaro, sarà l'orario.
Se proseguivo col mio esempio si notava meglio l'algoritmo greedy, algoritmo che dovrebbe procedere sino ad ottenere la soluzione ottima pur intraprendendo una strada(numero di somme) NON ottima(ricordo vagamente il problema del resto e simili).
Ma greedy è goloso e si accontenta di raggiungere alla soluzione anche se non ottima.
Per fare un esempio: se dovesse arrivare a 138 Kg, prenderebbe 100+qualcosa+qualcosa d'altro sino a raggiungere 138 ma non è detto che sia l'unica e la soluzione migliore in quanto potrebbero esisterne altre ancora migliore: così dovrebbe andare meglio.

Ma non abbiamo ancora risolto il mio problema.

[gugoXX]

Devi innanzitutto definire un target.
Quando e' una soluzione migliore di un'altra?

Perche'
30-30-220 e' peggiore di
40-40-200 ?

Una volta che hai deciso la tua funzione obiettivo, puoi enumerare tutte le disposizioni possibili, cercando quella di valore massimo. (Esponenziale)

Oppure passi alla programmazione dinamica e otterrai il tuo risultato ottimo. (Polinomiale anomalo).
Per suggerimenti sulla programmazione dinamica puoi iniziare a leggere questo vecchio post.
http://www.hwupgrade.it/forum/showthread.php?t=1884158

[fero86]

Originariamente inviato da gugoXX

Una volta che hai deciso la tua funzione obiettivo, puoi enumerare tutte le disposizioni possibili, cercando quella di valore massimo. (Esponenziale)

dissento: il problema é arcinoto e si sa che l'algoritmo greedy che seleziona il contenitore piú leggero (quello che contiene meno peso) fornisce sempre soluzioni ottime*. se mi sbaglio (che é possibilissimo) forniscimi un controesempio.

*la condizione di ottimalitá puó essere data dichiarando ottime le disposizioni che minimizzano il peso contenuto nel contenitore che contiene il peso maggiore.

Oppure passi alla programmazione dinamica e otterrai il tuo risultato ottimo. (Polinomiale anomalo).

polinomiale con che esponente? l'algoritmo greedy ottimo richiede tempo O(n * m) con n = numero di pesi ed m = numero di contenitori.

Originariamente inviato da misterx

[...] Ma greedy è goloso e si accontenta di raggiungere alla soluzione anche se non ottima.

forse mi sbaglio ma non mi dai l'idea di sapere cos'é un algoritmo greedy.

[misterx]

se non ricordo così male citando questo esempio: http://www.hwupgrade.it/forum/showthread.php?t=1884158

avendo a disposizione certi tagli di monete: 5, 9, 17, 30, 52, 111, 209 e volendo comporre il valore 156 le soulzioni potrebbero essere

questo è greedy
Un risultato per il punto 2 poteva essere p.es.
156 = 30+30+30+30+9+9+9+9

questo non lo è
Mentre il risultato, ottimo, per il punto 3, doveva essere
156 = 52+52+52

[oNaSsIs]

Se ho capito bene il tuo problema sarebbe quello di trovare un algoritmo efficiente che carichi in modo equo, o quasi, un certo numero di contenitori, nel tuo caso 3.
Il problema generale è di tipo NP e si chiama Load Balancing, però esistono dei semplici algoritmi di approssimazione che ottengono buoni risultati.
Per esempio quello che prima mi sembra abbia suggerito tu stesso, ossia ordinare in modo decrescente i pesi e assegnare ogni volta il peso alla macchina con carico minore è un algoritmo 3/2 approssimante. Nel caso in cui non dovesse bastarti questa approssimazione, che mi sembra comunque buona, so che esiste un algoritmo di Graham che è 4/3 approssimante.
Per quanto riguarda la dimostrazione del primo se dovessi averne bisogno non ho problemi a fornirtela, invece sull'ultimo non ti saprei aiutare.

[misterx]

Originariamente inviato da oNaSsIs

Se ho capito bene il tuo problema sarebbe quello di trovare un algoritmo efficiente che carichi in modo equo, o quasi, un certo numero di contenitori, nel tuo caso 3.
Il problema generale è di tipo NP e si chiama Load Balancing, però esistono dei semplici algoritmi di approssimazione che ottengono buoni risultati.
Per esempio quello che prima mi sembra abbia suggerito tu stesso, ossia ordinare in modo decrescente i pesi e assegnare ogni volta il peso alla macchina con carico minore è un algoritmo 3/2 approssimante. Nel caso in cui non dovesse bastarti questa approssimazione, che mi sembra comunque buona, so che esiste un algoritmo di Graham che è 4/3 approssimante.
Per quanto riguarda la dimostrazione del primo se dovessi averne bisogno non ho problemi a fornirtela, invece sull'ultimo non ti saprei aiutare.

ciao,
ma i problemi di Load Balancing sono quelli risolti dai router o switch nelle reti?

L'idea del riordino e poi di prelevare quello più grande e sommarlo a quelli più piccoli approssimando mi era ventuta dai vari ricordi degli algoritmi di riordino: peccato per la non precisione

[tuccio`]

http://twiki.di.uniroma1.it/pub/Algo...isp_greedy.pdf

a pagina 27 di questo pdf (sarebbe RIPARTIZIONE2), c'è un algoritmo di approssimazione (è per 2 insiemi, ma puoi facilmente adattarlo a 3.. non so come cambi il rapporto di approssimazione cambiando a 3, però comunque a senso direi che rimane decente) di complessità O(nlogn)

[fero86]

Originariamente inviato da oNaSsIs

Il problema generale è di tipo NP [...]

non mi risulta minimamente...

[gugoXX]

Originariamente inviato da fero86

dissento: il problema é arcinoto e si sa che l'algoritmo greedy che seleziona il contenitore piú leggero (quello che contiene meno peso) fornisce sempre soluzioni ottime*. se mi sbaglio (che é possibilissimo) forniscimi un controesempio.

Ma cosa sarebbe arcinoto non capisco.
Il problema non e' ben formulato, non abbiamo una funzione obiettivo e non si parla di contenitore piu' leggero.

Data come funzione obiettivo il minimizzare la distanza quadratica dalla media posso tirare fuori un esempio:

2,5,5,5,7,7
media su 3 contenitori = 31/3 = 10
Un algoritmo greedy che inizi riempiendo i pesi piu' leggeri svolgerebbe

2+5 = 7 (mi fermo perche' al prossimo arriverei a 12, oltre la media, oppure continuo? Perche' prenderlo? Perche' non prenderlo? Backtracking?)
5+5 = 10
7+7 = 14
Distanza quadratica media totale = 3^2 + 4^2 = 25

Se invece avessi eseguito (che poi non esiste un solo greedy, quindi boh?...)
2+7 = 9
5+5 = 10
5+7 = 12
avrei una distanza quadrativa totale pari a 1^2 + 2^2 = 5

polinomiale con che esponente? l'algoritmo greedy ottimo richiede tempo O(n * m) con n = numero di pesi ed m = numero di contenitori.

greedy ottimo non ha significato.
O e' greedy, e quindi spera solo di trovare la soluzione perfetta utilizando ottimi locali, oppure e' ottimo, ovvero trova la soluzione perfetta in complessita' minore possibile.
Altrimenti anche l'enumerazione completa di tutte le soluzione sarebbe ottima in quanto troverebbe sicuramente la soluzione perfetta. Ma non e' un algoritmo ottimo in quanto e' dimostrabile non essere l'algoritmo alla complessita' minore possibile.

LP fornisce polinomiali anomale perche' il peso non e' dato dalla numerosita' degli elementi quanto piu' al loro valore.
Non sono quindi algoritmi ottimi, ma risolvono classi di problemi NP-Hard per i quali non e' possibile (finora) dimostrare l'esistenza di soluzioni migliori.
Nel nostro caso il coefficiente sarebbe 7, essendo 7 il valore piu' grande dei pesi.
E un algoritmo LP solitamente e' di coefficiente 1. Nel nostro caso potrebbe quindi essere O(nm) con n=3 e M =7




....


1,2,2,3,7,7,9,11 Media 14
Come procediamo?

[misterx]

Originariamente inviato da oNaSsIs

Per esempio quello che prima mi sembra abbia suggerito tu stesso, ossia ordinare in modo decrescente i pesi e assegnare ogni volta il peso alla macchina con carico minore è un algoritmo 3/2 approssimante. Nel caso in cui non dovesse bastarti questa approssimazione, che mi sembra comunque buona, so che esiste un algoritmo di Graham che è 4/3 approssimante.
Per quanto riguarda la dimostrazione del primo se dovessi averne bisogno non ho problemi a fornirtela, invece sull'ultimo non ti saprei aiutare.

ho usato un algoritmo simile senza dover riordinare ed approssima in modo sufficientemente preciso: in pratica riempio un contenitore alla volta

grazie a tutti

[oNaSsIs]

Se l'algoritmo consiste semplicemente nell'assegnare i pesi, senza prima averli ordinati, al contenitore con carico minore, bé questo è un algoritmo greedy 2-approssimante e l'analisi in questo caso è essenzialmente tight.