Cálculo de matrices intercaladas óptimas

Abstract

El cálculo de matrices intercaladas exige hacer uso de estrategias mucho más eficientes que la búsqueda exhaustiva a ciegas. Para intentar encontrar una matriz intercalada de tamaño r x s con a lo más n colores, una búsqueda ciega requeriría explorar exactamente nrs posibilidades. El primer caso abierto era de tamaño 9 x 17 con 24 colores, por lo que se tendrían 24⁹ˣ¹⁷ = 1;487031 x 10²¹¹ posibilidades y se requerirían aproximadamente 4X10²⁰⁹ años de cálculo en una computadora moderna. Aunque resulta difícil determinar si la complejidad de un algoritmo de búsqueda con retroceso es asintóticamente mejor, sí es posible diseñar algoritmos que examinen una cantidad de matrices varios órdenes de magnitud por debajo del peor caso. Como primera estrategia de solución se diseñaron e implementaron dos modelos de programación entera a resolverse con Gurobi. Durante los experimentos, los modelos se probaron con un caso de tamaño 7 x 9, que es más pequeño que el primer caso abierto, cabe mencionar que en este caso y para el que ya se sabe que conjetura de Yuzvinsky se cumple; se dejaron correr los modelos por más de dos horas cada uno y no pudieron resolverlo, por lo que se concluyó en no continuar con esta estrategia para resolver los casos abiertos. Como una siguiente estrategia se diseñó un algoritmo de búsqueda con retroceso, pero como el espacio de búsqueda es muy grande, fue necesario tratar de hacer las asignaciones de color inteligentemente. Para ello se utilizó un algoritmo eficiente para conocer qué colores se podrían asignar en una celda sin afectar las asignaciones previas. Aunque con este algoritmo se resolvió al menos el primer caso abierto de tamaño 9 x 17, fue necesario utilizar otra estrategia para reducir el tiempo de búsqueda para matrices más grandes. Como una siguiente estrategia para acelerar el tiempo de búsqueda, se diseñó un algoritmo híbrido que combina búsqueda en amplitud y búsqueda en profundidad para poder hacer uso de la concurrencia del hardware. Esta estrategia logró acelerar el algoritmo y se resolvieron siete casos abiertos, que son 9 x 17, 9 x 18, 10 x 17, 9 x 19, 11 x 17, 9 x 20 y 9 x 21. Haciendo la observación de que un color con frecuencia máxima t puede aparecer en diagonal principal y que esto forza una matriz simétrica, se pueden precalcular todas las matrices simétricas de tamaño t x t para reutilizarlas al construir matrices más grandes. Esto reduce el tiempo de búsqueda porque solo se va llenando lo que falta. Añadiendo esta estrategia al algoritmo híbrido se logró reducir el tiempo en los primeros siete casos resueltos con el algoritmo híbrido que no usa esta estrategia y además se lograron resolver los casos 9 x 22, 10 x 19, 11 x 18, 10 x 21, 13 x 18 y 9 x 23, finalizando con trece casos resueltos y quedando seis casos abiertos. Se puede concluir que utilizar concurrencia en el algoritmo de búsqueda es una excelente opción para poder mejorar el rendimiento, pero la reutilización de trabajo previo también puede acelerar considerablemente la búsqueda de las matrices. Con estas ideas se podría diseñar alguna nueva estrategia que sea capaz de revisar los casos faltantes.