¿Hay un calendario de torneos para 18 jugadores, 17 rondas en grupos de 6, que es equilibrado en pares?

Question

Estamos interesados en una solución para el siguiente problema de programación, o de cualquier información acerca de cómo encontrar a él o a su existencia. Este viene de la vida real, así que no sólo va a ayudar a un matemático saciar su sed de conocimiento!

Tenemos 18 jugadores que estén jugando en un determinado deporte (digamos que el curling) en 3 diferentes callejones (6 jugadores por el callejón de) al mismo tiempo. Que jugar 17 partidos y queremos que cada combinación de 2 jugadores jugar exactamente 5 veces juntos.

(Como Douglas Zare señala en un comentario más abajo, esto es conocido como una de resolver diseño de bloque, con t=2, v=18, k=6, lambda=5 (a y b=51, y r=17)).

Nos preguntó su alrededor y alguien se acercó con una cerca de la solución: casi todos los pares de jugar 5 veces, excepto por un par de 6 y 4. La fuerza bruta parecía demasiado lento, así que probamos con un algoritmo genético, en vano (siendo principiantes en esto, no podríamos incluso llegar a la cerca de la solución que hemos tenido, así que no podemos sacar conclusiones de nuestros experimentos).

He encontrado cerca de la solución en mis viejos archivos, en caso de que alguien quiere trastear un poco.

{{1, 2, 3, 4, 5, 6}, {7, 8, 9, 10, 11, 12}, {13, 14, 15, 16, 17, 18}},
{{1, 6, 10, 12, 14, 16}, {2, 3, 8, 11, 15, 17}, {4, 5, 7, 9, 13, 18}},
{{1, 5, 7, 8, 15, 16}, {2, 4, 10, 11, 13, 14}, {3, 6, 9, 12, 17, 18}},
{{1, 4, 8, 9, 14, 17}, {2, 6, 7, 10, 15, 18}, {3, 5, 11, 12, 13, 16}},
{{1, 6, 8, 11, 13, 18}, {2, 4, 9, 12, 15, 16}, {3, 5, 7, 10, 14, 17}},
{{1, 2, 7, 12, 13, 17}, {3, 4, 8, 10, 16, 18}, {5, 6, 9, 11, 14, 15}},
{{1, 3, 9, 10, 13, 15}, {2, 5, 8, 12, 14, 18}, {4, 6, 7, 11, 16, 17}},
{{1, 5, 10, 11, 17, 18}, {2, 6, 8, 9, 13, 16}, {3, 4, 7, 12, 14, 15}},
{{1, 2, 9, 11, 16, 18}, {3, 6, 7, 8, 13, 14}, {4, 5, 10, 12, 15, 17}},
{{1, 4, 8, 12, 15, 18}, {2, 3, 7, 9, 11, 14}, {5, 6, 10, 13, 16, 17}},
{{1, 3, 7, 14, 16, 18}, {2, 5, 8, 9, 10, 17}, {4, 6, 11, 12, 13, 15}},
{{1, 5, 6, 9, 12, 14}, {2, 3, 10, 13, 15, 18}, {4, 7, 8, 11, 16, 17}},
{{1, 3, 10, 11, 12, 16}, {2, 4, 5, 8, 13, 14}, {6, 7, 9, 15, 17, 18}},
{{1, 2, 3, 4, 6, 17}, {5, 7, 11, 12, 13, 18}, {8, 9, 10, 14, 15, 16}},
{{1, 4, 7, 9, 10, 13}, {2, 12, 14, 16, 17, 18}, {3, 5, 6, 8, 11, 15}},
{{1, 2, 5, 7, 15, 16}, {3, 8, 9, 12, 13, 17}, {4, 6, 10, 11, 14, 18}},
{{1, 11, 13, 14, 15, 17}, {2, 6, 7, 8, 10, 12}, {3, 4, 5, 9, 16, 18}}

Answer 1

Una colección de $6$-tuplas en 18 puntos con la propiedad que cada par es cubierto $5$ veces es un diseño de bloques incompletos balanceados con $(v,k,\lambda) = (18,6,5)$ y $t=2$. La condición de que usted puede programar los partidos para ocurrir simultáneamente en $17$ rondas es que el diseño puede resolver.

Este artículo pretende construir puede resolver bloque diseños con parámetros incluyendo $(18,6,5)$.

Answer 2

Otros han publicado que una se puede resolver de bloque de diseño le ayudará a responder a la pregunta. Si quieres masticar algunos ciclos, considere el siguiente enfoque.

Hay 122 maneras de dividir un conjunto de 6 elementos en un máximo de 3 sets. Considere cómo un solución a su problema se ve en los primeros 6 elementos: cada una de las 17 sesiones produce una división de la 6 situado en una de las 122 maneras. Si en la primera sesión ha 6 personas, cada uno de los períodos de sesiones restantes se produce uno de los 122 particiones se mencionó anteriormente. Debido a la restricción de que cada par se produce en exactamente cinco de las sesiones, en las restantes 16 sesiones, usted no tendrá más de cuatro instancias de la misma partición. (Si usted hace un análisis similar a la de abajo basado en pares, usted encontrará que en la mayoría de los una instancia más de la trivial partición será permitido.)

Generar una lista de las combinaciones de particiones que puede ocurrir mientras se mantiene el restricción en los pares. Esto implica la elección de 16 elementos de un conjunto múltiple de (en la mayoría) 488 particiones, muchos de los cuales se imadmissible debido a que el par de restricción.

Si nos fijamos en cuántos pares son hechas por una partición, tenemos el trivial de la partición hacer 15 pares, 6 otros 10 pares, 15 a otros a 7 pares, a otros 25 a hacer 6 pares, a 15 de decisiones 3 pares. Puesto que usted desea 60 pares de los restantes 16 particiones, va a suceder que usted necesitará por lo menos 4 particiones que hacer 3 pares, en la mayoría de las 3 particiones que hacer 7 o más pares, y en la mayoría de las 4 particiones que hará 6 o más pares. Así que de los 16 elementos escogidos del anterior conjunto múltiple, en la mayoría de los 4 llegará a partir de un conjunto múltiple de más de 204 elementos, al menos 4 llegará a partir de un conjunto múltiple de 60 elementos, y el resto tendrá algunas restricciones. La idea es que un simple algoritmo de verificación parcial de la combinación y la rapidez de las malezas, por lo que su espacio de búsqueda es mucho menor que (488 elegir 16) artículos.

Una lista exhaustiva de todas estas combinaciones, de 16 de particiones puede ser pequeña, o puede ser grande; para el siguiente paso, yo recomiendo empezar con un no demasiado grande sublista: Pick 3 candidatos de la sublista y ver si pueden ser "cosido" juntos. Como un ejemplo, supongamos que elegir una combinación de 16 particiones, uno de los cuales es el trivial de la partición. A continuación, en orden a perfilar una solución juntos, necesito otra combinación que tiene una partición con un máximo de dos partes, porque no puedo usar una combinación en la que todos los 16 artículos que tienen 3 o más piezas.

Como intento de una costura, se puede ver que los intentos de violar la condición de la producción de más de 5 pares, entre los doce o 18 elementos utilizados para la costura. Como subexercise, considerar la combinación que consiste en el trivial de la partición seguido por cada uno de los 15 particiones de 6 elementos en 2 elemento de los conjuntos. A ver si se puede coser 3 copias de la combinación.

Gerhard "Me Preguntan Sobre El Diseño Del Sistema" Paseman, 2010.02.23