Árboles y Estrategias de Busqueda

PROBLEMA

Descripción del problema o ejercicio (incluyendo salidas esperadas):

Implementar un generador de estados en el lenguaje de programación JAVA, que cree todos los estados posibles a partir de un estado inicial para el problema del “rompecabezas de 3x3” y después explorar el árbol de búsqueda en ese espacio de estados con las 3 estrategias vistas: BFS, DFS y DFS Iterativa.

Descripción de la solución

El software cuenta con tres clases para llevar a cabo la tarea, las cuales son, Puzzle, Solver y Node

Puzzle

Es el main del programa, es donde se establece el estado inicial para el nodo y el estado final al que deseamos llegar, además esta clase es la encargada de invocar al solver para la resolución del problema.

Solver

Esta clase lleva a cabo la función de desarrollar el árbol y explorarlo hasta encontrar la solución buscada.

Node

Es la clase nodo, la cual almacena el estado del nodo así como otros datos relevantes.

Ejecución

Ejemplo 1

Inicial:

120

345

867

Objetivo:

123

456

780

BFS: 54,119 Nodos generados

DFS: 14,042 Nodos generados

DFS Iterativo: 11,155 Nodos generaldos

Ejemplo 2:

Inicial

023

145

786

Objetivo:

123

456

780

BFS: 23 Nodos Generados

DFS: 36 Nodos Generados

DFS Iterativo: 38728 Nodos Generados

Ejemplo 3:

Inicial

123

450

867

Objetivo

123

456

780

BFS: 2,745 Nodos Generados

DFS: 241 Nodos Generados

DFS Iterativo: 11 115 Nodos Generados

Conclusión:

La resolución de este problema nos pareció muy interesante y de mucha ayuda para practicar el desarrollo de árboles y estrategias de búsqueda, lo cual consideramos de mucha importancia para repasar los temas vistos en clase. Llevar a cabo el programa llevo más tiempo del esperado, ya que se deben hacer muchas consideraciones y validaciones, además se unió a la falta de práctica reciente del lenguaje java, esperamos poder mejorar nuestros tiempos para futuras implementaciones.

Por otra parte encontramos estos algoritmos como una inteligencia de busqueda y el principio de lo que estaremos esperando ver en la clase más adelante. Interesante de como podemos usar estos algoritmos para resolución de problemas cotidianos.