Raggruppamento di numeri per ridurre al minimo i mezzi di gruppo

Question

Raggruppamento di numeri per ridurre al minimo i mezzi di gruppo

#1 da (1 voti)

4

Ho bisogno di trovare un modo o un algoritmo per raggruppare i membri di un dato insieme di dati (di interi positivi) in modo che la differenza tra i mezzi di gruppo sia ridotta al minimo (non massimizzata, come al solito).

Ci sono due limitazioni:

Il numero di gruppi non deve superare log (N) base 2. N è la dimensione dell'array di input. Supponiamo che N = 16, sempre.
La dimensione del gruppo dovrebbe essere almeno log (N) base 2. Nell'esempio seguente, la dimensione del gruppo dovrebbe essere almeno 4.

Cercando sul WEB, ho trovato il seguente algoritmo avido. Si prega di vedere anche sotto l'esempio.

ordina i numeri nell'ordine decrescente
prendi i primi elementi K e inseriscili in gruppi diversi. Qui, K è il numero di gruppi.
per i successivi elementi (N - K), inseriscili nel gruppo con la somma più bassa. ripetere questo fino al completamento di tutti i numeri.

Possiamo ottenere un algoritmo migliore in termini di complessità temporale? È gradita una guida per una soluzione migliore a questo problema.

Esempio:

for input array = (11, 11, 14, 16, 17, 18, 18, 19, 20, 21, 22, 25, 25, 26, 28, 31)

The solution:  (where sd: standard deviation, cv: coefficient of variation)

    group           mean    sd  cv
(31, 20, 17, 11)    19.8    8.4 0.4 
(28, 21, 18, 11)    19.5    7.1 0.4
(26, 21, 19, 14)    20.0    5.0 0.3
(25, 22, 18, 16)    20.3    4.0 0.2

algorithms time cluster

posta samarasa 27.05.2012 - 19:08

fonte

1 risposta

Leggi altre domande sui tag algorithms time cluster

Progettazione di un processo ETL basato sul contenuto con .NET e SFDC Layout di viste matematiche (iOS)

score 1 · Accepted Answer

Intuitivamente, anche se i tuoi gruppi sono rilassati, penso che il tuo problema sia un'istanza del problema di imballo dei rifiuti , che è NP-difficile. Forse dovresti chiedere al gruppo CS Theory se si tratta di un'istanza di BPP / BPP generalizzato.

Il tuo avido algoritmo funziona in complessità linearithmic (ordinamento in O (n log n) , binning in O (n log log n) , assumendo l'uso di heap, perché il tuo il numero di bin è ~ log n), ma non è ottimale (è facile trovare sequenze che lo ingannino).

Puoi fare un avido best-fit in O (n log log n) - trovare la media dei numeri in tempo lineare (senza ordinamento), e poi per ogni numero cerca di adattarlo in un contenitore tale che la media attuale rimanga il più vicino possibile alla media totale - questa dovrebbe essere un'operazione log-logaritmica rispetto a n . Se questa è una soluzione appropriata per il tuo problema dipende da quanto lontano ti puoi permettere di essere ottimale.

Tuttavia, tieni presente che non puoi andare meglio di questo O (n log log n) - perché qualunque schema intelligente tu usi, dovrai selezionare ogni elemento e scartarlo.