¿Qué algoritmo es bueno para buscar un diseño de lotería?

Question

Me interesa saber qué tipo de algoritmo sería adecuado para encontrar un diseño de lotería. He visto que se ha demostrado que $L(39,7,4,7)=329$ . Esta notación se explica en http://web.archive.org/web/20070824014211/http://www.maths.qmul.ac.uk/~pjc/csgnotes/LottoDesigns.pdf y dice lo siguiente:

En la lotería, se eligen siete números distintos $n_1<\ldots < n_7$ del conjunto $\{1,\ldots,39\}$ y forma una tupla $(n_1,\ldots,n_7)$ llamada fila. Es posible elegir 329 de tales filas de modo que para cualquier fila arbitraria $(n_1,\ldots,n_7),$ el conjunto de esas 329 filas contiene al menos una fila $(m_1,\ldots,m_7)$ tal que $$|\{n_1,n_2,n_3,n_4,n_5,n_6,n_7\}\cap \{m_1,m_2,m_3,m_4,m_5,m_6,m_7\}|\geq 4?$$ Creo que este resultado se debe a Hämäläinen basándose en la desigualdad $$L(39,7,4,7) \leq L(16,7,4,4) + L(23,7,4,4)\leq 76+253=329$$ que no conozco. Ahora la pregunta:

¿Es posible hacer una lista de $329$ filas del diseño $(39,7,4,7)$ explícitamente con un tiempo razonable? ¿Es el recocido simulado el mejor algoritmo para listar esas filas?

Pregunté esto en https://stackoverflow.com/questions/18486523/what-algorithm-is-a-good-to-search-a-lotto-design pero resultó una mala pregunta allí.

Answer 1

La pregunta parece citar por partes mi respuesta en la AOPS de 15 de julio de 2011, incluido el enlace de presentación . Lo que me extraña es que aquí el OP pide un diseño de lotería en particular $(39,7,4,7)$ mientras que mi respuesta fue constructivo y, de hecho, proporcionó toda la información para obtener dicho diseño. Esto es lo que hay que hacer.

La diapositiva nº 9 de la presentación enlazada constructivamente explica la desigualdad: $$L(39,7,4,7) \leq L(16,7,4,4) + L(23,7,4,4)\leq 76+253=329.$$ Desde $L(16,7,4,4) = C(16,7,4)$ y $L(23,7,4,4) = C(23,7,4)$ son diseños de cobertura, podemos obtener los bloques correspondientes a partir de Repositorio de cubiertas de La Jolla :

• $C(16,7,4) \leq 76$ ( bloquea )
• $C(23,7,4) = 253$ ( bloquea )

A saber, conseguir un diseño de lotería $(39,7,4,7)$ con 329 bloques, basta con tomar la unión de los bloques para $C(16,7,4)$ y los bloques para $C(23,7,4)$ donde los elementos de estos últimos bloques se incrementan todos en 16. Los bloques resultantes son:

 1  2  3  4  6  8 16                      \
 ...                                       } blocks from C(16,7,4)
 7  9 12 13 14 15 16                      /
 1+16  2+16  3+16  4+16  5+16  6+16  7+16 \
 ...                                       } blocks from C(23,7,4),
 7+16 11+16 15+16 17+16 18+16 19+16 20+16 /  with elements increased by 16

Answer 2

A $L(v,k,p,t)$ el diseño de la lotería es un subconjunto de $\binom{V}{k}$ donde $V = \{1,\ldots,v\}$ y $\binom{V}{k}$ es el conjunto de todos los $k$ -subconjuntos de elementos de $V$ . Desde $v$ es un número natural, el conjunto de todos los subconjuntos de $\binom{V}{k}$ es finito. Así que existe el algoritmo para enumerar todos estos subconjuntos finitos, y comprobar entonces la propiedad de diseño. Este " algoritmo ingenuo "terminará después de un número finito de pasos. Sin embargo, debido a la exposición combinatoria el esfuerzo es enorme, y no serás testigo de que este algoritmo termine salvo en los casos más pequeños.

Un enfoque más refinado es hacer un búsqueda de retroceso : Empiezas con el juego completo $\binom{V}{k}$ y tratar de eliminar un solo elemento en cada capa del árbol de búsqueda. De este modo, se evita tocar muchos subconjuntos innecesarios de $\binom{V}{k}$ .

Un gran obstáculo en este tipo de problemas son las copias isomórficas: Si tienes un diseño de lotería, cualquier permutación del conjunto base $V$ le dará de nuevo un diseño de lotería. Esto significa que, sin ninguna contramedida, su algoritmo de búsqueda devolverá millones de copias del mismo diseño de lotería. Las técnicas para reducir o evitar copias isomórficas del árbol de búsqueda son bastante sofisticados y, a menudo, no está claro cuál debería ser el enfoque más eficiente.

Estas técnicas permiten enumerar completamente todos los diseños de lotería de parámetros mayores que con el algoritmo ingenuo. Pero aún así, el espacio de búsqueda crece exponencialmente, y pronto no será posible resolver el problema por enumeración completa. Por lo tanto, para parámetros más grandes, los diseños "récord" no suelen producirse mediante un enfoque de enumeración completa. En su lugar, se utilizan algunos propiedades adicionales se introducen, o algún tipo de heurística se utiliza.

La discusión anterior es sobre un método general para construir diseños de lotería. No sé cómo se ha demostrado exactamente el resultado L(39,7,4,7) = 329. Normalmente, se hace mediante una combinación de argumentos teóricos que reducen el tamaño del espacio de búsqueda, y una enumeración por ordenador que es capaz de enumerar todas las posibilidades restantes.