Cos'è un algoritmo efficiente per assegnare casualmente un pool di oggetti a un genitore usando regole specifiche

Question

Cos'è un algoritmo efficiente per assegnare casualmente un pool di oggetti a un genitore usando regole specifiche

#1 da (5 voti)
#2 da (2 voti)

7

Ho bisogno di alcune risposte esperte per aiutarmi a determinare l'algoritmo più efficiente in questo scenario.

Considera le seguenti strutture di dati:

type B { A parent; }

type A {
   set<B> children;
   integer minimumChildrenAllowed;
   integer maximumChildrenAllowed;
}

Ho una situazione in cui ho bisogno di recuperare tutti i bambini orfani (potrebbero essercene centinaia di migliaia) e assegnarli CASUALMENTE a genitori di tipo A in base alle seguenti regole.

Alla fine del lavoro, dovrebbe non rimanere orfano
Alla fine del lavoro, nessun oggetto A dovrebbe avere meno figli del suo minimo predesignato.
Alla fine del lavoro, nessun oggetto A dovrebbe avere più figli del suo massimo predeterminato.
Se esauriamo gli oggetti A, dovremmo creare una nuova A con i valori predefiniti per il minimo e il massimo e assegnare gli orfani rimanenti a questi oggetti.
La distribuzione dei bambini dovrebbe essere distribuita il più equamente possibile.
Potrebbero esserci già alcuni bambini assegnati ad A prima dell'inizio del lavoro.

Stavo giocando con il modo di farlo, ma temo che finirei semplicemente per andare in loop tra i genitori, dal più piccolo al più grande, e poi prendere un orfano per ciascun genitore.

Mi stavo chiedendo se esiste un modo più efficiente di gestirlo?

Modifica

Espandendo i criteri per una distribuzione uniforme dei bambini, dovremmo cercare di evitare una situazione in cui una A ha 2 o più figli di qualsiasi altra A, a meno che non siano iniziati in quel modo. Ad esempio, se A1 ha 4 figli e A2 e A3 hanno 1 figlio ciascuno e ci sono 2 orfani, A2 e A3 dovrebbero essere assegnati a tutti gli orfani che fanno una distribuzione uniforme di 4, 3 e 3 figli per ogni A.
Sì, capisco che potremmo finire dove rimane un orfano e un A che non ha raggiunto il suo minimo. Questa eccezione sarà gestita da un algoritmo separato che tenterà di dividere equamente una A in due oggetti e assegnare gli orfani rimanenti tra loro.

EDIT: 2

Ok, ho frainteso i requisiti della mia situazione. Il modello dati per A mostra la proprietà minima e massima, ma in realtà dovrebbe essere un'impostazione globale per ogni A. In sostanza è un requisito mancato che richiede il refactoring del modello di dati in un secondo momento.

Tutti A avranno lo stesso minimo e massimo ora. Questo in realtà cambia le cose in modo significativo! Ci scusiamo per la confusione.

algorithms efficiency

posta maple_shaft 12.09.2012 - 22:02

fonte

2 risposte

2

Supponendo di avere A esistenti con vari numeri di B già assegnati a loro, il mio primo passaggio a questo sarebbe probabilmente:

Ordina gli A per primi sul loro numero di B (chiamerà il ChildCount), e poi su un numero casuale come secondo fattore di ordinamento. Quindi hai una lista di A raggruppati per il loro ChildCount, il più basso per primo, ma quelli con lo stesso numero di bambini vengono inseriti casualmente nell'elenco. Quindi inizia dall'alto, assegnando B uno alla volta a quelli A con un ChildCount di 0. Al termine, ricomincia da capo e fallo per quelli con un ChildCount di 1. Quindi 2, ecc. Se A raggiunge il numero massimo di figli, rimuoverlo completamente dalla lista. Se ne rimangono ancora pochi, crea i nuovi A e riempili uno alla volta. Per evitare gli "orfani", se contrassegni i nuovi B assegnati come nuovi, puoi riprenderne alcuni da quelli di altre A con un conteggio massimo e bilanciare le cose (supponendo che ciò sia corretto durante il "tempo di assegnazione") e prima che tutto venga eseguito).

risposta data 13.09.2012 - 06:21

fonte

Leggi altre domande sui tag algorithms efficiency

Le specifiche funzionali sono un "documento di progettazione"? Come denominate le vostre librerie personali? [chiuso]

score 5 · Accepted Answer

Vorrei:

Calcola max * countOfA e min * CountOfA
Se non hai abbastanza B per riempire tutti i valori A minimi non puoi effettivamente soddisfare i criteri che hai elencato.
Se non si dispone di A sufficiente, aggiungere il numero minimo necessario (massimale di (SumOfAMaxes-B) / DefaultMaximum). Aggiorna la somma dei valori minimo e massimo di conseguenza.
Ora puoi calcolare il numero medio di bambini per il tuo set A. Questo è il tuo valore target. Tuttavia, questo di solito sarà frazionario. Capire quanti oggetti dovrebbero essere arrotondati per difetto, e quanti su. (Esempio, hai 100 genitori e la media è 3.4 40 avranno 3 come bersaglio e 60 ne avranno 4 come bersaglio).
Passa in rassegna i genitori e impostali sul valore di destinazione più alto, a meno che non siano già quel valore o superiore. Tieni traccia di quanti bambini hai lasciato da allocare mentre procedi. Quando esaurisci il valore alto (nell'esempio precedente ne avresti solo 60), assegna il valore più basso.
Quando hai finito con 4 potresti avere alcuni bambini non assegnati a causa di genitori esistenti con più figli del tuo valore target. In tal caso, torna al passaggio 4 ma assicurati che il nuovo valore di destinazione sia almeno uguale al valore del target precedente + 1.

Probabilmente non è ottimale, ma è piuttosto facile e probabilmente non così lontano. È abbastanza simile al commento originale di mcwise, anche se un po 'migliorato ed elaborato. Dati i requisiti aggiornati, non c'è molto per il problema.