Algoritmo A
Enviado por jhusepi • 9 de Septiembre de 2013 • 1.817 Palabras (8 Páginas) • 369 Visitas
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
...