8 Puzzle

Comparación de Estrategias de Búsqueda Admisibles y ε-Admisibles para el problema del 8-puzzle

Miguel Álvarez Álvarez
Inteligencia Artificial. 4º de Ingeniería Informática. EPSIG. Universidad de Oviedo. Campus de Viesques. E-33271 Gijón. UO3775@uniovi.es

Resumen. El objetivo de este documento consiste en realizar un estudio comparativo de diversas estrategias de búsqueda heurísticaaplicadas sobre el problema del 8-puzzle. En concreto, se considerará el algoritmo A* y se analizará su comportamiento para los heurísticos más habituales. Posteriormente se incluirán las estrategias ε-admisibles de ponderación estática, ponderación dinámica y Aε*. El estudio se centrará en comprobar el desempeño de estos algoritmos comparándolos con el A* original en función de diversos valores de ε.Para ello se tomará como referencia un banco determinado de ejemplos y se empleará un mismo heurístico como estándar para las cuatro estrategias.

Palabras Clave: 8-puzzle, Algoritmo A*, búsqueda heurística, ε–admisible.

1 Introducción
Para llevar a cabo el estudio se recurre al conocido problema del 8-puzzle puesto que constituye uno de los ejemplos típicos de uso en la InteligenciaArtificial, entre otras razones porque partiendo de un estado inicial lo que se pretende es llegar siempre a un mismo y único estado final. El 8-puzzle es un tablero de 3x3 que está constituido por ocho fichas numeradas (del 1 al 8) y un hueco vacío que permite llevar a cabo los movimientos de las fichas para alcanzar el objetivo. Estos movimientos se encuentran sujetos a una serie de restricciones que sedetallarán en el capítulo siguiente.

Figura 1. Estado final

2 Planteamiento del problema
Se pretende que partiendo de un estado inicial, es decir, una situación determinada del tablero se llegue con un número de movimientos mínimo al estado final mostrado en la figura anterior. En cada movimiento se permite desplazar una única ficha y sólo se autorizan aquellos realizados entre casillasque cumplan las siguientes restricciones: 1. Las casillas deben ser adyacentes. 2. Las casillas deben estar en la misma fila o en la misma columna, es decir, ser ortogonales. 3. La casilla destino debe estar vacía. A través de un banco de ejemplos utilizado para el estudio y que se compone de un total de 40 con diversos costes, entendiendo por coste el número de movimientos mínimo necesarios para irdel estado inicial al final, se lleva a cabo tanto el análisis de A* con los heurísticos h0, h1, h2 y h3, es decir, mismo algoritmo pero distintos heurísticos; como la comparación entre éste y las estrategias ε-admisibles de ponderación estática, ponderación dinámica y Aε*. En este otro caso los algoritmos varían ligeramente respecto al A* original pero se emplea el mismo heurístico paracompararlos entre sí (h2).

3 Métodos de resolución

3.1 Algoritmo A* El algoritmo A* se enmarca en el grupo de los algoritmos de búsqueda en grafos y constituye una especialización del BF. Bajo determinadas condiciones encuentra el camino de menor coste existente entre un estado inicial y uno objetivo. La principal característica de este algoritmo y que lo diferencia de los algoritmos voraces o delBF es el hecho de que éste explora estados teniendo en cuenta aquellos que resultan más prometedores para alcanzar la solución final desde un estado intermedio, combinado con el coste que ha supuesto llegar desde el estado inicial hasta ese intermedio. La función de evaluación es la siguiente: f(n)=g(n)+h(n) Donde g(n) es el coste del mejor camino desde el inicial hasta n y h(n) supone unaestimación positiva del coste del camino más corto desde n al objetivo. El algoritmo A* empleado presenta la siguiente estructura: ABIERTA = (inicial); Mientras NoVacia(ABIERTA) hacer N = ExtraePrimero(ABIERTA); Si EsObjetivo(n) entonces Devuelve Camino(inicial, n) y para; Fin si S=Sucesores(n); Añade S a la entrada de n en la TABLA_A; Para cada q de S hacer Si (q Є TABLA_A) entonces Rectificar(q, n,...