¿Qué es un algoritmo eficiente para asignar aleatoriamente un conjunto de objetos a un padre utilizando reglas específicas?

7

Necesito algunas respuestas de expertos para que me ayuden a determinar el algoritmo más eficiente en este escenario.

Considere las siguientes estructuras de datos:

type B { A parent; }

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

Tengo una situación en la que necesito buscar a todos los niños huérfanos (podría haber cientos de miles de estos) y asignarlos DE FORMA ALEATORIA a los padres del tipo A según las siguientes reglas.

  1. Al final del trabajo, no debería quedar huérfanos
  2. Al final del trabajo, ningún objeto A debería tener menos hijos que su mínimo prediseñado.
  3. Al final del trabajo, ningún objeto A debe tener más hijos que su máximo prediseñado.
  4. Si nos quedamos sin objetos A, deberíamos crear una nueva A con valores predeterminados para mínimo y máximo y asignar los huérfanos restantes a estos objetos.
  5. La distribución de los niños debe distribuirse de la manera más equitativa posible.
  6. Puede que ya haya algunos niños asignados a A antes de que comience el trabajo.

Estaba jugando con la forma de hacer esto, pero me temo que acabaría haciendo un bucle entre los padres ordenados de menor a mayor, y luego agarraría un huérfano para cada uno de ellos.

Me preguntaba si hay una manera más eficiente de manejar esto?

EDIT:

  • Ampliando los criterios para una distribución uniforme de niños, deberíamos intentar evitar una situación en la que cualquier A tenga 2 o más hijos que cualquier otro A, a menos que haya comenzado de esa manera. Por ejemplo, si A1 tiene 4 hijos, y A2 y A3 tienen 1 hijo cada uno y hay 2 huérfanos, entonces a A2 y A3 se les debe asignar un huérfano que haga una distribución uniforme de 4, 3 y 3 niños por cada A.

  • Sí, entiendo que podemos terminar donde queda un huérfano y una A que no ha alcanzado su mínimo. Este caso de excepción será manejado por un algoritmo separado que intentará dividir uniformemente una A en dos objetos y asignar a los huérfanos restantes entre ellos.

EDITAR: 2

Ok, entendí mal los requisitos en mi situación. El modelo de datos para A muestra las propiedades mínimas y máximas, pero en realidad debería ser una configuración global para cada A. En esencia, es un requisito perdido que requiere que el modelo de datos se refactorice más adelante.

Toda A tendrá el mismo mínimo y máximo ahora. ¡Esto realmente cambia las cosas significativamente! Perdón por la confusión.

    
pregunta maple_shaft 12.09.2012 - 22:02

2 respuestas

5

Yo:

  1. Calcular max * countOfA y min * CountOfA

  2. Si no tiene suficiente B para completar todos los valores A mínimos, no puede cumplir con los criterios que ha enumerado.

  3. Si no tiene suficiente A, agregue el número mínimo que necesita (techo de (SumOfAMaxes-B) / DefaultMaximum). Actualice la suma de los valores mínimo y máximo en consecuencia.

  4. Ahora puede calcular el número medio de hijos para su conjunto A. Este es su valor objetivo. Sin embargo, esto suele ser fraccional. Averigua cuántos elementos se deben redondear hacia abajo y cuántos. (Por ejemplo, tienes 100 padres y la media es 3.4. 40 tendrá 3 como objetivo y 60 tendrá 4 como objetivo).

  5. Recorra los padres y ajústelos al valor objetivo más alto a menos que ya tengan ese valor o más. Lleve un registro de cuántos hijos le quedan para asignar a medida que avanza. Cuando se quede sin el valor alto (en el ejemplo anterior, solo tendría 60), asigne el valor más bajo.

  6. Cuando haya terminado con 4, es posible que tenga algunos hijos no asignados debido a que los padres existentes tuvieron más hijos que su valor objetivo. Si es así, vuelva al paso 4, pero asegúrese de que su nuevo valor objetivo sea al menos igual al mínimo del valor objetivo anterior + 1.

Probablemente esto no sea óptimo, pero es bastante fácil y probablemente no esté tan lejos de ser óptimo. Es bastante similar al comentario original de mcwise, aunque un poco mejorado y elaborado. Teniendo en cuenta los requisitos actualizados, no hay mucho para el problema.

    
respondido por el psr 13.09.2012 - 02:24
2

Suponiendo que tienes A existentes con varios números de B ya asignados a ellos, mi primer paso probablemente sería:

Ordene las A primero en su número de B (llamará a eso ChildCount), y luego en un número aleatorio como segundo factor de clasificación. Así que tienes una lista de A agrupadas por su ChildCount, la más baja primero, pero luego las que tienen el mismo recuento de niños se colocan al azar en la lista entre ellas. Luego simplemente comience desde arriba, asignando las B una a la vez a las A con un recuento de niños de 0. Cuando termine, comience de nuevo en la parte superior y hágalo para las personas con un recuento de niños de 1. Luego 2, etc. Si una A alcanza su número máximo de hijos, elimínelo de la lista por completo. Si le sobran algunas B, cree las nuevas A y llénelas una por una. Para evitar "huérfanos", si marca las B recientemente asignadas como nuevas, puede recuperar algunas de las otras A con un recuento máximo, y equilibrar las cosas (suponiendo que sería correcto hacerlo durante el "tiempo asignado" , y antes de que todo esté comprometido).

    
respondido por el GrandmasterB 13.09.2012 - 06:21

Lea otras preguntas en las etiquetas