Problema De Las N-Reinas Por Método Tabú

23 de noviembre de 2012

Trabajo Final, Investigación de Operaciones I

Problema de estudio: Problema de las N-Reinas
Método utilizado: Búsqueda Tabú

Profesor: Pedro Lara
Alumno: *********
No. Cuenta: 210*******

UAM Azcapotzalco
Casa Abierta al Tiempo

Introducción
Un área importante de la investigación operativa es la de la programación matemática, la cual puede estar definidaen un dominio continuo o discreto. En el primero, el desarrollo de calculo diferencial y de los métodos exactos, como el simplex, proporcionan buenas herramientas para resolver los problemas de optimización, pero cuando las variables de decisión son discretas, especialmente si involucran una gran cantidad de variables, la búsqueda de soluciones exactas puede no ser posible porque, o no haysoluciones analíticas o no es viable su implementación en un medio computacional convencional.
El problema de las ocho reinas es un acertijo en el que se colocan ocho reinas sobre un tablero de ajedrez sin que se amenacen entre si. Fue propuesto por el ajedrecista alemán Max Bezzel en el año 1848. Ya que en el juego la reina amenaza a aquellas piezas que se encuentren en su misma fila, columna odiagonal (Ilustración 1), el juego consiste en colocar sobre un tablero de ajedrez ocho reinas sin que estas se amenacen entre ellas.

Ilustración 1
Durante los años, muchos matemáticos, incluyendo a Gauss y a Georg Cantor, han trabajado en este problema y lo han generalizado a n-reinas (donde n es un número arbitrario). Las primeras soluciones fueron ofrecidas por Franz Nauck en 1850. Nauck tambiénse abocó a las n-reinas (en un tablero de nxn de tamaño arbitrario). En 1874, S. Günther propuso un método para hallar las soluciones usando determinantes, y J.W.L. Glaisher redefinió su aproximación.
Comúnmente este problema suele resolverse empleando un esquema vuelta atrás (o Backtracking). Este problema tiene 2 Versiones hablando de su versión de “n-reinas”. La más simple consiste en encontrarexactamente una solución valida para un valor n dado. La otra versión, más difícil, consiste en encontrar todas las soluciones posibles para un único valor n.
Se puede observar que este problema tiene una solución (Q(1) = 1) para n = 1, no tiene solución para n = 2 y n = 3 y tiene 2 soluciones para n = 4. La Tabla 1 muestra el numero total de Soluciones Q(n) para 4 ≤ n ≤ 20 [5] [6].
Parasolucionar este problema, se han diseñado numerosos Algoritmos basados en algunos como Backtracking, Algoritmos Genéticos, Búsqueda local con resolución de conflictos, programación entera y redes neuronales entre otros.
Además, el Problema de las n reinas pertenece a la clase de problemas NP-completos [7], pero se resuelve fácilmente en tiempo polinomio cuando solamente se busca una solución [4](Ilustración 2)

Ilustración 2
Como la ilustración muestra el problema de las n-reinas para n=8 tiene 92 soluciones de las cuales soló 12 son esencialmente distintas (Ilustración 3).

Ilustración 3

Este problema puede resolverse de varias formas:
1. Enumerando todas las posibles alternativas y evaluando si se producen colisiones, en cuyo caso se tendría que evaluar factorial de n posiblessoluciones.
2. Usando un método de búsqueda local, como el greedy. Por ejemplo, si se asigna la reina 1 a la columna 1 aunque se permute exhaustivamente las otras 3 solo se consigue un óptimo local, es decir, el mínimo de colisiones posibles es una colisión y ya no se podría mejorar, (el algoritmo queda atrapado en un óptimo local), es decir, si se fija la reina 1 en la columna 1 nunca seencontrará una configuración con cero colisiones.
3. Modelándolo como un problema lineal de maximizar el número de reinas en un tablero de ajedrez sujeta a las restricciones de que en una fila solo haya una reina, al igual que en cada columna y, además que en cada diagonal haya una y solo una reina.
4. En el presente trabajo se tratara de resolver el problema de las n-reinas para n=8 por el...