Seudcodigo puzzle 8

Implementación del Juego puzzle-n por medio de dos algortimos: Backtracking y A*
Guillermo Rodea Palomares
NIA:10047435

Álvaro Hernández Benedicto
NIA:100047311

ABSTRACT
En este documento trataremos la implementación en java del juego puzzle-n, como generalización del juego puzzle-8, para ello, usaremos dos algoritmos distintos: Un algoritmo de tipo backtracking, del cual podremos verque no resulta del todo eficiente; y uno de tipo A*, que como se verá resulta mucho mejor para abordar el problema planteado.

Categories and Subject Descriptors
Usaremos la distribución de implementación de los algoritmos. Java J2SE para la Figura 1 Grafo dirigido con pesos -Árbol: Se trata de un grafo conexo y sin ciclos. Consta de un nodo raíz del que surgen una serie de nodos hijos, a su vezde cada uno de estos nodos hijo pueden surgir o no una serie de nodos hijos. En la siguiente figura tenemos un ejemplo de árbol:

General Terms
- Algoritmo: Lista de operaciones bien definida, finita y ordenada que permite encontrar la solución a un problema. Un algoritmo está caracterizado por 5 para propiedades: a) b) c) d) e) Carácter finito. Precisión: Cada paso del algoritmo está fijadode manera inequivoca. Entrada: Un algoritmo tiene cero o más entradas. Salida: un algoritmo tiene una o más salidas, que tienen una relación específica con las entradas. Eficacia.

Existen varias formas de expresar un algoritmo: a) Descripción de alto nivel: Se explica el algoritmo verbalmente o ayudado por dibujos. Se omiten detalles. Su objetivo es dar a conocer los fundamentos del algoritmo yel funcionamiento básico del mismo sin entrar en detalles. Pseudocódigo: También se conoce como descriptor formal, describe paso a paso el algoritmo en un lenguaje de tipo pseudocódigo. Implemnetación: Se muestra el algoritmo expresado en un lenguaje de programación específico o en cualquier otro soporte capaz de realizar opecariones. Figura 2 Ejemplo de árbol

b)

c)

- Grafo: Grafo es unconjunto de nodos o vértices unidos por un conjunto de aristas o arcos, que permiten representar relaciones entre los elementos de un conjunto. Cada nodo y cada arista pueden o no tener un peso o coste asociados a su recorrido. En la siguiente figura tenemos un ejemplo de grafo con pesos en las aristas:

- Puzzle-8: Se trata de un juego clásico en inteligencia artificial, su objetivo es, en untablero de 3x3, conseguir alcanzar una colocación específica de las fichas a partir de un estado inicial dado. Para ello el único movimiento posible es “arrastrar” a la casilla vacía una de las fichas adyacentes. En la siguiente figura vemos un ejemplo:

se alcanza una solución y en caso contrario, realiza una marcha atrás (backtracking) para explorar otra posible solución. El algoritmo prosiguepara cada nodo que tiene uno o más hijos sin explorar. Al tratarse de un algoritmo de búsqueda en profundidad, su mayor problema es el tiempo de cómputo. Con este algoritmo tenemos dos posibles condiciones de parada que determinarán la complejidad del algoritmo, tamaño de búsqueda y tiempo de cómputo. Si la condición de parada es la de encontrar simplemente la solución, no está garantizadoencontrar la mejor solución. En caso de investigar todo el árbol completo, está garantizado encontrar la mejor solución, pero el tiempo de cómputo puede dispararse para estructuras muy grandes. En la siguiente figura vemos gráficamente el crecimiento de la complejidad de la solución con el número de pasos que se den, razón de que los tiempos de cómputo sean elevados para este algoritmo. Como puedeapreciarse el algoritmo de backtracking recorre la solución en forma de árbol:

Figura 3 Ej. 8Puzzle

En la siguiente figura mostramos un ejemplo de los posibles movimientos y de cómo el árbol de búsqueda va desarrollándose con cada movimiento que realizamos:

Figura 4 Posibles movimientos de un 8 puzzle, y árbol desarrrollado. Este problema puede generalizarse aumentando las dimensiones del...