Encuentra el grupo conjunto más pequeño para cubrir todas las posibilidades combinatorias

Question

que estoy haciendo algunos ejercicios en el algoritmo de combinatoria y tratando de encontrar la manera de resolver la cuestión a continuación:

Dado un grupo de 25 bits, ajuste (elegir) 15 (asuntos no permutables y orden no):

n!/(k!(n-k)!) = 3.268.760 

Ahora, para cada una de estas posibilidades construir una matriz donde cruzo cada miembro 25bit única contra todo otro miembro 25bit donde en la relación entre allí debe ser al al menos 11 bits configurados comunes (solo unos, no ceros).

Vamos a tratar de ilustrar representándolo como datos binarios, por lo que el primer miembro sería:

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits) 
0000000001011111111111111 second member 
0000000001101111111111111 third member 
0000000001110111111111111 and so on.... 
... 
1111111111111110000000000 up to here. The 3.268.760 member. 

Ahora cruzar estos valores a través de una matriz para el 1 x 1 Debo tener 15 bits comunes. Como el resultado es> = 11, es un resultado "útil".

Para el 1 x 2 tenemos 14 bits comunes por lo que también es un resultado válido.

Hacer eso para todos los miembros, finalmente, cruzar 1 x 3.268.760 debería dar como resultado 5 bits comunes, por lo que dado que es < 11 no es "útil".

Lo que necesito es averiguar (por matemática o algoritmo) cuál es el número mínimo de miembros necesarios para cubrir todas las posibilidades que tienen 11 bits comunes.

En otras palabras, un grupo de N miembros que si se prueban contra todos los demás puede tener al menos 11 bits comunes en todo el universo de 3.268.760 x 3.268.760.

Usando un algoritmo de fuerza bruta descubrí que con 81 miembro de 25 bits es posible lograr esto. Pero supongo que este número debería ser más pequeño (algo cerca de 12).

Estaba tratando de usar un algoritmo de fuerza bruta para hacer todas las variaciones posibles de 12 miembros sobre el 3.268.760 pero el número de posibilidades es tan grande que tomaría más de cien años calcularlo (3,156x10e69 combinaciones)

He buscado en Google sobre combinatoria, pero hay tantos campos que no sé en los que deberían encajar estos problemas.

Así que cualquier dirección sobre qué campo de combinatoria, o cualquier algoritmo para estos problemas es muy apreciada.

PD: Solo como referencia. La "similitud" de dos miembros se calcula utilizando:

(Not(a xor b)) and a 

Después de que hay un pequeño bucle recursivo para contar los bits dado el número de bits comunes.

EDIT: Como lo prometido es deuda (@btilly) en el comentario a continuación aquí está la imagen 'fractal' de las relaciones oscila o link to image

La escala de color de rojo (partido de 15bits) a verde (11 bits partido) a negro para valores menores de 10 bits.

Esta imagen es solo una muestra de los primeros 4096 grupos.

Answer 1

Este tipo de problema es extremadamente difícil, no debe esperar poder encontrar la respuesta exacta.

Una solución codiciosa debe producir una respuesta "bastante buena". Pero ... ¿cómo ser codicioso?

La idea es elegir siempre el siguiente elemento para ser el que va a coincidir con tantas posibilidades como sea posible que actualmente no coinciden. Desafortunadamente con más de 3 millones de miembros posibles, debe intentar emparejar contra millones de miembros no emparejados (tenga en cuenta que su próxima conjetura podría coincidir con la de otro miembro de su conjunto de candidatos ...), incluso elegir ese próximo elemento probablemente no sea factible.

Así que tendremos que ser codiciosos para elegir el siguiente elemento. Elegiremos cada bit para maximizar la suma de las probabilidades de coincidir eventualmente con todos los elementos actualmente no coincidentes.

Para que necesitaremos una tabla de consulta de 2 dimensiones P tal que P(n, m) es la probabilidad de que dos miembros aleatorios va a llegar a tener al menos 11 bits en común, si m de los primeros n bits que son 1 en el primer miembro también son 1 en el segundo. Esta tabla de 225 probabilidades debe ser precalculada.

Esta tabla puede ser fácilmente calcula utilizando las siguientes reglas:

1. P(15, m) es 0 si m < 11, 1 de otra manera.

2. Para n < 15:

   P(n, m) = P(n+1, m+1) * (15-m)/(25-n) + P(n+1, m) * (10-n+m)/(25-n) 
   

Ahora vamos a empezar con unos pocos miembros que son "muy lejos" de la otra. Mi sugerencia sería:

1. primeros 15 bits de descanso, 1 0.
2. primeros 10 bits 0, 1. descanso
3. primeros 8 bits 1, 7 últimos 1, descanso 0.
4. bits 1 -4, 9-12, 16-23 son 1, descanso 0.

Ahora, comenzando con su universo de (25 eligen 15) miembros, elimine todos los que coincidan con uno de los elementos de su colección inicial.

A continuación vamos al corazón del algoritmo.

While there are unmatched members: 
    Find the bit that appears in the most unmatched members (break ties randomly) 
    Make that the first set bit of our candidate member for the group. 
    While the candidate member has less than 15 set bits: 
     Let p_best = 0, bit_best = 0; 
     For each unset bit: 
      Let p = 0 
      For each unmatched member: 
       p += P(n, m) where m = number of bits in common between 
          candidate member+this bit and the unmatched member 
          and n = bits in candidate member + 1 
      If p_best < p: 
       p_best = p 
       bit_best = this unset bit 
     Set bit_best as the next bit in our candidate member. 
    Add the candidate member to our collection 
    Remove all unmatched members that match this from unmatched members 
The list of candidate members is our answer 

No he escrito el código, por lo tanto, no tengo idea de qué tan buena será la respuesta que producirá este algoritmo. Pero asumiendo que no es mejor que tu actual, para 77 candidatos (hicimos trampa y comenzamos con 4) tienes que hacer 271 pases a través de tus candidatos sin competencia (25 para encontrar el primer bit, 24 para encontrar el segundo, etc. hasta 11 para encontrar el 15 y uno más para eliminar los miembros coincidentes). Eso es 20867 pases. Si tiene un promedio de 1 millón de miembros no igualados, eso es del orden de 20 mil millones de operaciones.

Esto no será rápido. Pero debería ser computacionalmente factible.

Answer 2

tl; dr: quiere resolver dominating set en un gráfico grande y extremadamente simétrico.Biltly tiene razón en que no deberías esperar una respuesta exacta. Si este fuera mi problema, probaría la búsqueda local comenzando con la solución codiciosa. Elija un conjunto e intente deshacerse de él cambiando los otros. Esto requiere estructuras de datos para realizar un seguimiento de los conjuntos que se cubren exactamente una vez.

EDITAR: Bien, aquí está una mejor idea para un límite inferior. Por cada k de 1 al valor de la solución óptima, hay un límite inferior de [25 elija 15] * k/[cobertura conjunta máxima de k conjuntos]. Su límite de 12 (en realidad 10 según mis cálculos, ya que olvidó algunos vecinos) corresponde a k = 1. Boceto de prueba: arregle una solución arbitraria con m conjuntos y considere la mayor cobertura que puede obtenerse por k de la m. Construye una solución fraccional donde todas las simetrías de las k elegidas se promedian juntas y se escalan para que cada elemento se cubra una vez. El costo de esta solución es [25 elegir 15] * k/[cobertura conjunta máxima de esos k conjuntos], que es al menos tan grande como el límite inferior que estamos buscando. Sin embargo, sigue siendo al menos tan pequeño como la solución m-set original, ya que los rendimientos marginales de cada conjunto disminuyen.

La cobertura máxima de la computación es en general difícil, pero hay un factor (e/(e-1)) - algoritmo de aproximación (≈ 1.58): codicioso, que suena como que podría implementar rápidamente (nota: necesita elija el conjunto que cubra los otros conjuntos más descubiertos cada vez). Al multiplicar la solución codiciosa por e/(e-1), obtenemos un límite superior en la cobertura máxima de k elementos, que es suficiente para alimentar el límite inferior descrito en el párrafo anterior.

Advertencia: si este límite superior es mayor que [25 elija 15], ¡entonces k es demasiado grande!