Raggruppamento di matrici arbitrarie di dati in N bin

Question

Desidero raggruppare una matrice di valori casuali di valori casuali nei gruppi n, in modo che la somma dei valori in qualsiasi gruppo/bin sia la più uguale possibile.

Quindi, per i valori [1, 2, 4, 5] e n = 2, le tazze di uscita devono essere [sum(5+1), sum(4+2)].

Alcune possibilità che si verificano a me:

• completa ampiezza esaustivo prima ricerca
• processi casuali con condizioni hard coded
• Inizia da un capo all'altro della array ordinato l'arresto, il raggruppamento fino a quando la somma è uguale alla media globale e passare al gruppo successivo fino a

Sembra la soluzione ottimale (dove la somma del il contenuto dei bin è il più possibile uguale dato l'array di input) è probabilmente non banale; quindi al momento mi sto appoggiando all'ultima opzione, ma ho la sensazione che forse mi mancano soluzioni più eleganti?

Answer 1

Questo è un problema NP-difficile. In altre parole, non è possibile trovare una soluzione ottimale senza esplorare tutte le combinazioni e il numero di combinazioni è n^M (dove M è la dimensione della matrice, e n il numero di fagioli). È un problema molto simile a clustering, che è anche NP-rigido.

Se il set di dati è abbastanza piccolo da gestire, un algoritmo di forza bruta è il migliore (esplorare tutte le combinazioni).

Tuttavia, se il set di dati è grande, ti consigliamo un algoritmo tempo-polinomiale che non ti fornisca la soluzione ottimale, ma una buona approssimazione. In tal caso, suggerisco di utilizzare qualcosa di simile a K-Means ...

Passo 1. Calcolare la somma prevista per contenitore. Diamo A come array, quindi la somma prevista per bin è SumBin = SUM (A)/n (la somma di tutti gli elementi nell'array rispetto al numero di contenitori).

Fase 2. Mettere tutti gli elementi dell'array in qualche collezione (ad esempio un altro array) che chiameremo La Borsa (questo è solo un concettuale, in modo da capire i prossimi passi).

Passo 3. Partizione Il sacchetto in n gruppi (preferibilmente in modo casuale, in modo che ciascun elemento finisce in qualche bin i con probabilità 1/n ). A questo punto, i tuoi contenitori hanno tutti gli elementi, e The Bag è vuoto.

Passaggio 4. Calcolare la somma per ciascun contenitore. Se il risultato è uguale all'ultima iterazione, , uscita. (Questo è il aspettativa fase di K-Means)

Fase 5.Per ciascun bin i, se somma è superiore SumBin, scegliere il primo elemento superiore SumBin e messo nuovamente in Il sacchetto; se la somma è inferiore a SumBin, selezionare il primo elemento inferiore a SumBin e rimetterlo in The Bag. Questo è il gradino di discesa del gradiente (noto anche come maximization step) di K-Means.

Punto 6. Andare al passo 3.

Questo algoritmo è solo un'approssimazione, ma è veloce e garantito a convergere.

Se siete scettici circa un algoritmo randomizzato come sopra, dopo la prima iterazione quando si torna al punto 3, invece di assegnare elementi in modo casuale, è possibile farlo in modo ottimale eseguendo il Hungarian algorithm, ma io non sono certo che garantirà risultati migliori nel complesso.