Uno podría suponer que resolver un rompecabezas debe ser labor trivial para una computadora. Sin embargo, la tarea es mucho más difícil de lo que habíamos imaginado. El reconocimiento de patrones es cosa sencilla cuando se tiene una orientación específica, pero si no se sabe para qué lado va orientada una pieza, se verán los posibles invonvenientes.
Andrew Gallager, de la Universidad de Cornell en Ithaca, Nueva York, acaba de mostrar cómo con su algoritmo puede resolver un rompecabezas de 10 milpiezas en unas 24 horas. Esto es tres veces el récord del año pasado, de un rompecabezas de 3,300 piezas. El algoritmo de Gallagher ha mejorado el enfoque estándar, que es lo mismo que hacen los humanos: encontrar grupos de piezas que se parecen entre sí y trabajar a partir de ahí.
El algoritmo incluso trabaja con piezas cuadradas, que son más difíciles de resolver que las tradicionales piezas de rompecabezas porque no se tiene ninguna pista acerca de la orientación. Puede además resolver problemas que mezclen piezas cuadradas con piezas de rompecabezas tradicionales sin necesidad de saber cuántas piezas tiene el rompecabezas o sus dimensiones.
Y aunque crea que el problema es fácil, considere en cuántas diferentes maneras se pueden acomodar piezas de un rompecabezas, incluso con relativamente pocas. Evidentemente no se pueden intentar todas las posibles combinaciones y aún así, ¿cómo poder reconocer que se tiene una solución? La conclusión es simple: resolver rompecabezas es un problema NP-difícil.
El algoritmo usa un método de recorrer un árbol agregando una nueva medida concerniente a la similitud de las piezas. Esta medida de similitud está basada en la bien conocida distancia Mahalanobis, la cual fue introducida en 1936 y se basa en la correlación estadística entre variables por las cuales patrones diferentes pueden ser identificados y analizados. En el caso del problema que nos ocupa, esta medida escala la distancia entre distribuciones por su dispersión. La nueva medida compara piezas usando el gradiente de intensidad cerca del borde, escalado por la covarianza del canal de color (simple ¿verdad?). Aún con todas estas técnicas, se desarrolló una heurística para hallar la solución aproximada en un tiempo razonable.
Se puede observar el algoritmo en acción en los siguientes dos videos:
Si alguien piensa que esto es tarea de alguien que no tiene nada que hacer, debe notarse que el algoritmo podría servir para recuperar documentos que han sido pasados por esas máquinas trituradoras que hacen tiras de papel de los mismos, como en el caso del concurso organizado por DARPA.
La pregunta finalmente sería: ¿Podría hacerlo usted mejor? Considerando que el reconocimiento vía una cámara de video ya no es un problema y que, además, hay tarjetas gráficas con procesadores y núcleos múltiples, GPUs, cualquier podría intentar mejorar este algoritmo, o crear uno nuevo usando paralelismo. ¿No se anima a intentarlo?
Referencias: Resolución de rompecabezas (paper) y i-programmer