Hay un nombre para este problema que puedo búsqueda de enfoques en

Question

Tengo una colección de una colección de números que necesito encontrar el menor número de grupos a poner en mientras que el conjunto diferente de números en cada conjunto no exceda un umbral. Por ejemplo:

Collection A: 1,2,3
Collection B: 1,2,4,5
Collection C: 1,3,5,7,9
Collection D: 6,7,8,9,10,11
Threshold: 6

Una solución válida sería:

Grouping 1: A,B {1,2,3,4,5}
Grouping 2: C   {1,3,5,7,9}
Grouping 3: D   {6,7,8,9,10,11}

O

Grouping 1: B   {1,2,4,5}
Grouping 2: A,C {1,2,3,5,7,9}
Grouping 3: D   {6,7,8,9,10,11}

En mi real problema del número de colecciones es de 1000+, cada uno con 50 a 300 números y mi Umbral es de 600. Estoy buscando el siguiente.

1. Hay una matemática común nombre para este tipo de problema puedo investigación.
2. Es un buen enfoque para la resolución de un problema que se traduce en el menor número de Agrupaciones.

La determinación de la afinidad de 2 Colecciones es trivial (Unión y comparar frente a cada individuo de la colección), pero cuando me pongo a pensar en un número arbitrario de las colecciones se agrupan me parece que no puede pensar en ninguna no la fuerza bruta manera de atacar el problema que tendría una enorme cantidad de tiempo para que un equipo pueda resolver, incluso después de 100 colecciones.

Answer 1

Si tu conjuntos disjuntos, tendría el clásico de reciclaje de problemas de embalaje. Aparece cuando se agrupan dos conjuntos de eliminar los elementos duplicados. Para el reciclaje del embalaje problema, hay heurística (el más grande primero, fit), que han demostrado no demasiado lejos de la óptima. Usted puede comenzar buscando mayor superposición entre los conjuntos, ya que reduce el número de elementos a colocar en bandejas.