Algoritmo A

JUEGO DE LAS 8-REINAS

El juego consiste en colocar 8 reinas en un tablero de ajedrez sin que se ataquen.

Una posibilidad es intentar lograr una solución de manera incremental,

acercándose a la meta poco a poco siguiendo una serie de decisiones locales basadas en la

información obtenida durante el proceso.

Hay que asegurarse que la secuencia de transformaciones sea sistemática, para no

generar configuraciones repetidas ni excluir configuraciones deseables.

Una forma de sistematizar la búsqueda es construyendo más que transformando

configuraciones.

Por ejemplo el hecho de que deba de haber sólo una reina por columna nos reduce

el número de alternativas a menos de 8 en cada renglón.

Sistematizamos la búsqueda para no recuperarnos de restricciones en operaciones

futras, es decir, una vez que violamos una restricción no podemos seguir añadiendo más

reinas para rectificarla.

Posibles candidatos de heurísticas:

1. Colocar reinas que dejen el mayor número de casillas sin atacar.

2. Colocar reinas cuyas diagonales amenacen menos casillas

En la implementación del algoritmo los números significan lo siguiente:

0= casilla libre

1= reina

2= casilla atacada

Se adjunta la implementación en java del Algoritmo A* del juego 8-reinas. El

usuario sólo deberá introducir la primera reina en la columna que desee de la primera fila,

el programa introducirá las siguientes reinas dependiendo de la heurística elegida.

IMPLEMENTACIÓN DEL

ALGORITMO A*

EN 8‐PUZZLE Y 8‐REINA

Trabajo realizado por:

Alonso García, Rubén

Sanz Fernández, Rafael

1. INTRODUCCIÓN

1.1. Introducción a los algoritmos de búsqueda informada y exploración

Los algoritmos de búsqueda informada son más eficientes que los algoritmos de

búsqueda no informada, debido a que éstos últimos pueden encontrar soluciones a

problemas generando sistemáticamente nuevos estados y probándolos con el objetivo.

Los algoritmos de búsqueda informada son muy útiles en problemas donde lo que

importa es el estado de solución en sí mismo, no el camino. Utilizan métodos inspirados en

la física estadística (temple simulado) y la biología evolutiva (algoritmos genéticos).

Un primer contacto con éstos algoritmos es el siguiente: “búsqueda primero el

mejor”, que es un caso particular del algoritmo general de “búsqueda de árboles” o

“búsqueda de grafos”, en el cuál se selecciona un nodo para la expansión basada en una

función de evaluación, f(n). La evaluación mide la distancia al objetivo.

Otro algoritmo importante es el “búsqueda voraz primero el mejor” que expande

el nodo más cercano al objetivo. Evalúa los nodos utilizando solamente la función

heurística:

f(n) = h(n)

En nuestro trabajo nos centraremos en la búsqueda A* y sus variantes.

2. CARACTERIZACIÓN DEL ALGORITMO A*.

Un algoritmo de búsqueda por el mejor nodo combina las características de los

métodos en anchura y en profundidad. Se caracteriza porque para cada nodo se generan

todos los posibles sucesores y de estos sólo se expande aquel que sea más prometedor

después de la aplicación sobre ellos de una función heurística h(n) que estima el coste del

camino desde cada nodo al objetivo. El uso de este tipo de algoritmo, al minimizar el coste

estimado hasta el objetivo, disminuye considerablemente el coste de la búsqueda.

Desafortunadamente, no es ni óptimo ni completo.

Por otra parte, la búsqueda de coste uniforme minimiza el coste del camino hasta

el nodo, g(n) , es decir, expande para cada conjunto de sucesores aquel cuyo camino desde

el nodo raíz tenga un menor coste. Este es un algoritmo óptimo y completo, pero puede ser

muy ineficiente.

Sería bueno poder combinar estas dos estrategias para conseguir las ventajas de

ambos. Afortunadamente, podemos hacer eso exactamente, combinando las dos funciones

de evaluación simplemente sumándolas:

f(n) = g(n) + h(n).

Ya que g(n) proporciona el coste del camino desde el nodo de inicio hasta el nodo

n, y h(n) es el coste estimado del camino de menos coste desde n hasta el objetivo, f(n) es el

coste estimado de la solución de menor coste que atraviesa el nodo n.

Si se intenta encontrar la solución de menor coste, es razonable intentar primero el

nodo con el menor valor de f. Lo bueno de esta estrategia, es que es más que razonable. Se

puede comprobar que es completa y óptima, dando una simple restricción de la función h.

La restricción es escoger una función h que nunca sobreestime el coste para

alcanzar el objetivo. Una función h de este tipo es una heurística admisible.

A este algoritmo se le conoce con el nombre de A*.

Los algoritmos de búsqueda heurística tradicionales como A* pueden llegar a

necesitar un espacio de almacenamiento que crece de manera exponencial con la longitud

de la solución del problema. Esto puede propiciar que, a pesar de que el problema tenga un

coste temporal relativamente asequible, el coste espacial lo convierta en un problema

intratable.

2.1. Optimalidad de A*

Definir f* - el costo de la solución óptima para la ruta

? A* expande todos los nodos con f(n)<f*

? A* podría expandir algunos de los nodos a la derecha del “contorno de la

meta”, para los cuales f(n) = f*, antes de seleccionar el estado meta.

La primera solución encontrada debe ser la óptima, dado que los nodos de todos los

contornos subsiguientes tendrán un costo f más alto y con ello un costo g más alto (todos

los estados meta tienen h(n) = 0).

Teorema: Sea h*(n) el costo real desde n hasta la meta. Si h(n) < h*(n) para todo nodo n,

entonces A* siempre va a encontrar un nodo meta óptimo.

Prueba: Sea s el nodo meta de mínimo costo. Sea que A* seleccione un nodo meta

subóptimo s’, donde g(s)<g(s’)

Sea n un nodo sin expandir en la ruta desde el nodo inicio y el nodo meta óptimo s. Notar

que ese nodo sin expandir necesariamente existe, de acuerdo con la suposición previa (en el

otro caso, s ya habría sido elegido como el nodo meta).

Puesto que n no ha sido elegido para su expansión en su

...