Evitar la sobreventa y la asignación de recursos limitados con propiedades superpuestas.

Question

Estoy tratando de resolver el problema de evitar la sobreventa de recursos limitados.

Considere los recursos (personas) que se describen por un conjunto de propiedades donde cada propiedad pertenece a una categoría diferente (propiedades de ejemplo de cuatro categorías:hombre, 25-30 años, 2 hijos, interesado en los juegos).

Los compradores quieren asignar acceso a los recursos.Los compradores pueden especificar un subconjunto de categorías y una propiedad de cada categoría (ejemplo:asignar 1000 hombres, de 25 a 30 años de edad o asignar 100 mujeres, de 25 a 30 años de edad, interesadas en la música).

En mi ejemplo de la vida real, tengo más de 6 millones de conjuntos posibles de propiedades (perfiles) donde, para cada conjunto de propiedades, sé cuántos perfiles existen.

Mi enfoque inicial fue construir un gráfico como el siguiente:

y luego recorrer usando pesos de borde, por ejemplo, validando si se puede satisfacer la demanda de 100 mujeres, edad 2:

1. compruebe si el tamaño (mujer, edad 2) <100
2. para cada padre:
   1. compruebe si el tamaño (padre) <100 y vaya a 2.
3. para cada niño:
   1. compruebe si tamaño (niño) <100 * peso (borde (nodo, niño)) vaya a 1.

(El algoritmo anterior está simplificado y no impide visitar el mismo nodo varias veces)

Todo funciona bien cuando el gráfico es pequeño; sin embargo, cuando aumenta el número de nodos y bordes (dependencias) entre nodos (grupos de universos de perfil), no se escala muy bien.

Considere el ejemplo:

• gráfico grande, 6 m de nodos, más de 20 m de bordes
• El comprador quiere asignar 1000 hombres (y solo hay hombres y mujeres en la categoría de género)

El algoritmo comenzaría con el nodo 'macho' de nivel superior que probablemente tiene más de 10 m de bordes salientes y se requerirían más de 10 m de comprobaciones (y probablemente cada uno de esos 10 m de bordes salientes tiene bordes entrantes que también deben verificarse).

Estaba tratando de encontrar un enfoque diferente pero fallé.Estaba intentando buscar en Google las soluciones existentes, pero parece que ni siquiera puedo nombrar el problema correctamente.Cualquier referencia a cómo es similar este problema sería buena para mí como punto de partida.

Gracias por los comentarios/ayuda.

Dos gráficos más para presentar el crecimiento exponencial del gráfico:3 categorías

4 categorías

Actualizar

Respecto al tamaño, asumiendo 8 categorías de propiedades donde cada categoría tiene:2, 6, 6, 6, 6, 8, 1140, 150 valores respectivamente y luego el número estimado de perfiles:2*6^4*8*1140*150 ~= 3,5 * 10^9.Número de nodos en el gráfico:al menos 7 * 10^9, número de aristas en el gráfico:al menos 140 * 10^9.

Actualización #2

La fórmula para el número de nodos es:

$\sum_{i<n}\prod_{k<i \atop j_1, j_2, ..., j_k < n} s_{j_{1}} ...s_{j_{n}}$

donde $n$ es el número de categorías y $s_x$ es el tamaño de la categoría $x$.

Entonces, en mi ejemplo, habría 11'169'108'657 nodos.

Actualización #3

Según el consejo de @Raphael: he reducido el número de nodos y ahora la fórmula es:

$\sum_{i<n-M}\prod_{k<i \atop j_1, j_2, ..., j_k < n} s_{j_{1}} ...s_{j_{n}}$

donde $M<n$ y se supone que la distribución de recursos entre las porciones más pequeñas del universo es igual.Al mismo tiempo, se eliminaron muchos bordes del gráfico.

Ejemplo de reducción del tamaño del subgráfico:

Answer 1

Por lo tanto, la estructura de datos que contiene punteros para cada combinación posible de clasificadores es enorme. Claro, pero ¿por qué construirlo en absoluto? ¡No engreques esto!

Simplemente almacene los perfiles en una base de datos y haga un barrido de filtrado (tiempo lineal) para cada consulta, es decir, seleccione/cuente con la demanda. Para unos pocos millones de registros, eso no debería requerir más preprocesamiento.

Si el número de solicitudes es grande y/o necesita De Verdad Pequeños tiempos de respuesta, puede pensar en el almacenamiento en caché o en la creación de clases de equivalencia a lo largo de algunos clasificadores populares, o a lo largo de clasificadores con pocas clases grandes. Luego, el barrido lineal solo debe hacerse en pequeñas listas.

Por ejemplo, puede dividir su base de datos a lo largo de género y edad (suponiendo que se incluyan en la mayoría de las consultas de los clientes)

$ qquad {m, w, o } times {0..5, 10..15, dots, 95..100 } $

donde los valores obviamente dependen de sus datos. Luego, cada consulta requerirá solo unas pocas de estas pequeñas listas, e incluso puede paralelarse si almacena los trozos individuales por separado.