8 Puzzle

Universidad Sim´n Bol´ o ıvar Departamento de Computaci´n y Tecnolog´ de la Informaci´n o ıa o CI-2693 Laboratorio de Algoritmos III Trimestre Septiembre-Diciembre de 2008

Proyecto 2: Resolviendo el 8-Puzzle con A*
1. Objetivo

El objetivo del proyecto es el de resolver el problema del 8-Puzzle con un algoritmo informado de b´squeda de caminos de costo m´ u ınimo, espec´ ıficamente A*

2.Descripci´n del problema o

El problema de 8-Puzzle [7], como lo describe Russel y Norvig [5] consiste, como se muestra la figura 1, en tablero de 3 X 3, el cual contiene 8 bloques cuadrados numerados (del 1 al 8) y un cuadrado vac´ (En ıo nuestra representaci´n ser´ numerado con 0). Los cuadrados adyacentes al espacio vac´ pueden moverse o a ıo a ese espacio. El objetivo es alcanzar un estadometa, el cual se puede observar en la tabla derecha de la figura 1. Una f´rmulaci´n posible del problema es la siguiente: o o Estados: Un estado indica la posici´n de cada uno de los nueve cuadrados dentro del tablero o Estado Inicial: Un estado cualquiera Funci´n para obtener sucesores: A partir de un estado se generan los estados v´lidos que o a resultan de las cuatros posibles acciones. Lasacciones posibles son: mover el cuadrado a la izquierda, derecha, arriba y abajo Costo del camino: Cada movimiento o paso, tiene un costo de uno (1), por lo tanto el camino desde un estado inicial a un estado meta es igual al n´mero de pasos (o movimentos) que se dan u para alcanzar el estado meta. Funci´n de prueba de meta: Determina si un estado es el estado meta. o En la figura 2, cortes´ de Bermany Paul [1], se puede observar la arborescencia obtenida al resolver ıa el 8-Puzzle con el algoritmo de B´squeda en amplitud. Nuestro objetivo es encontrar el camino m´s corto, u a el cual en la figura 2 se muestra resaltado. Note que el grafo para este problema es ´ ımplicito. Es decir, dado un estado inicial se obtienen los estados sucesores con una funci´n. No se guarda todo el grafo, que o estodas las posibles combinaciones del tablero, en memoria. 8 4 7 1 6 3 2 5 1 4 7 2 5 8 3 6

Figura 1: Ejemplo de Estado Inicial y Estado Final del 8-Puzzle

3.

Algoritmos informados de b´ squeda de caminos m´ u ınimos

Se desea que resolver el 8-Puzzle con el algoritmos informado conocido como A* [6]. El algoritmo A* esta descrito en el libro de Meza y Ortega [3]. Tambien se encuentra unabuena explicaci´n del algoritmo o A* y del 8-Puzzle en libro de Rusell y Norvig [5]. En el libro Artificial Intelligence for Games [2] hay un pseudo c´digo muy ilustrativo del algortimo A*, mostrando sus semajanzas con el algoritmo de Dijkstra y o se hace un an´lisis sobre como implementarlo. Casi todas estas referencias se encuentran en la biblioteca a de la universidad, en la sala de lectura hayalgunas. Tambi´n se publicar´ referencias en la p´gina web e a a del curso en la secci´n de Bibliograf´ o ıa. Se debe implementar cuatro heur´ ısticas o costos estimados a la meta h(.). 1

Figura 2: Arborescencia del 8-Puzzle obtenida con BFS 1. Zero heur´ ıstica: En esta heur´ ıstica todo estado da como resultado zero. Es decir, para cualquier estado n, se tiene que h(n) = 0 2. DistanciaManhattan: Es la suma de las distancias, v´rticales y horizontales, de cada uno de los e bloques, a su posici´n en el estado meta. o 3. N´ mero de cuadros desordenados: Es el n´mero de bloques en posiciones equivocadas, es u u decir, diferentes a las que corresponden al estado meta. Se puede interpretar que mientras m´s a desordenado est´ el tablero, m´s dif´ debe ser ordenarlo. e a ıcil 4. Blanco:Distancia entre la posici´n en el estado meta del blanco y su posici´n actual. o o Por ejemplo, dado los estados inicial y final de la figura 1, se tiene que el c´lculo de las heur´ a ısticas es como sigue: Zero heur´ ıstica: 0 Cuadro Distancia 1 1 2 2 3 0 4 0 5 2 6 2 7 0 8 3

Distancia Manhattan:

total = 1 + 2 + 2 + 2 + 3 = 10 Cuadro Posiciones 1 1 2 1 3 0 4 0 5 1 6 1 7 0 8 1

N´ mero de...