8reinas

Backtracking 8 Reinas
Ramírez Monárrez Adriana Guadalupe
Análisis y Diseño de Algoritmos

8 Reinas
Backtracking
 Características:
o La
solución
puede
expresarse
como
una
n-tupla
(x1,x2, x3,…, xn) donde cada xi, es seleccionado de un conjunto finito Si.
o El problema se puede formular como la búsqueda de aquella tupla que
optimiza (maximiza o minimiza) un determinado criterioP(x1,…, xn).
El backtracking elimina la necesidad de llegar a todas las hojas (posibles soluciones) del
árbol (espacio de soluciones). Cuando para un nodo interno del árbol se puede asegurar
que noalcanza una solución se poda la rama completa dando “vuelta atrás” o
backtracking.
o Solución (x1, x1, x1,…, x1), xi ∈ Si,
o Espacio de soluciones de tamaño Π|Si|
o Solución parcial: (x1, x2,…,xk,?,?,…,?), xi ∈ Si,
Vector solución para el que aún no se han establecido todas sus
componentes.
o Función de poda/acotación.
Permite identificar cuándo una solución parcial no conduce a unasolución del
problema.

 Elementos

 Restricciones asociadas a los problemas
o Restricciones explícitas:
Restringen los posibles valores de las variables xi (definen el espacio de
soluciones delproblema ΠSi).
o Restricciones implícitas:
Establecen relaciones entre las variables xi (determinan las tuplas que
satisfacen el criterio P(x1,…xn): nos indican cuando una solución parcial nos
puedellevar a una solución).

El problema de las 8 Reinas
Colocar 8 reinas en un tablero de ajedrez de modo que no haya dos que se ataquen (una
reina ataca a quien esté en su misma fila, columna odiagonal).
Como cada reina debe estar en una fila diferente podemos suponer que la reina i se coloca
en la fila i.
Todas las soluciones pueden representarse como 8-tuplas (x1,…x8) en las que xi indicala
columna en que se coloca la reina i.

Backtracking 8 Reinas
Ramírez Monárrez Adriana Guadalupe
Análisis y Diseño de Algoritmos

 Restricciones explícitas:
Si = {1,2,3,4,5,6,7,8}, 1 ≤ i...