Universidad Autónoma del Estado de México
Facultad de ingeniería
Profesor: Montes Venegas Héctor Alejandro
Alumno: Mejia Martinez Alejandro
Inteligencia artificial
BFS, DFS, Greedy y A*
¿Como funciona cada una de las implementaciones?
La clase [Link] se encarga de varias funciones importantes que utilizan todos los
algoritmos implementados, como generar nuevos sucesores, eliminar los movimientos
“ilegales” del estado actual, además con cada nodo explorado lo mantienen para revisar si
es el estado objetivo para posteriormente retornarlo como solución. También calcula las
heurísticas para los algoritmos de A* y greedy.
Funciones de [Link]
Test: En esta función se comprueba si el estado que recibe es la solución del puzzle a partir
de la definición de este al inicio de la clase, esta definición se debe hacer siempre que se
quiere cambiar las dimensiones del juego
Manhattan_Distance: Esta es la primera de dos funciones heurísticas que se pueden
implementar en los algoritmos de A* y greedy, en esta se calcula la distancia manhattan de
cada una de las piezas es el estado actual, hasta su posición en el estado objetivo, para
después regresar los valores de heurística para el respectivo algoritmo tomar en cuanta que
para A* se necesita no solo el valor de heurística sino el de costo más heurística
Misplaced_Tiles: Esfa función heurística cuenta el numero de piezas que no están en su
lugar, toma el estado actual y lo compara con el estado objetivo cada que uno de los valores
en el estado es diferente a los del estado objetivo incrementa un contador y este valor es el
que se retorna como valor de heurística
available_moves: Aquí se determinan los movimientos que no puede realizar el espacio
vacío (0) de acuerdo con la posición en la que se encuentra en el estado actual, compara
su posición con la de filas y columnas y dependiendo del resultado de dichas
comparaciones regresa un conjunto de movimientos que pueden ser aplicados al estado
actual
expand: Genera los nuevos estados sucesores del estado actual, aplicando cada uno de
los operadores en el arreglo de movimientos validos de la función anterior con cada iteración
en el conjunto de movimientos disponibles se genera un nuevo estado que representa un
nodo nuevo como sucesor del estado anterior
solution: En esta función se reconstruye la ruta desde el estado objetivo hasta el estado
inicial a través de una función de retroceso que obtiene la dirección del anterior al objetivo
y el anterior a ese, de este modo hasta llega a la raíz, dando como resultado la ruta que se
tiene que seguir
[Link]
Aquí se determina si el estado inicial definido por el usuario es solucionable de acuerdo con
el número de inversiones de este, si cumple con la regla de paridad, para posteriormente
rechazarlo o iniciar a buscar la solución de este llamando a cada una de las funciones que
contienen los algoritmos de búsqueda.
Inv_num: Aquí se cuenta el numero de inversiones que tiene el estado inicial, comparado
las posiciones de este con las del estado objetivo
Solvable: Toma el valor dado por la función anterior y determina si es par o no, para
comenzar con la búsqueda llamando a cada función que contiene los algoritmos o rechazar
la configuración ingresada
Search_Algorithms
Contiene cada una de las funciones que implementan los algoritmos de BFS, DFS, Greedy
y A*
BFS: Este algoritmo utiliza las funciones de la clase state para generar nuevos sucesores
y explorar los nodos, dada su estructura de cola (FIFO) explora todos los nodos de un nivel
antes de pasar al siguiente haciendo un recorrido a lo ancho del árbol de búsqueda
DFS: A diferencia de BFS esta emplea una estructura de pila (LIFO) donde primero explora
todos los niveles del árbol de búsqueda antes de pasar a otra rama para seguir buscando
Greedy: Funciona de una manera similar a BFS usando una estructura de cola, con la
diferencia que emplea una heurística para “optimizar” el método de búsqueda, dando
prioridad a los nodos con la menor heurística que puede ser la distancia manhattan de las
fichas en el estado actual respecto a su posición en el estado objetivo o el numero de fichas
que están en una posición incorrecta
A*: Funciona de manera similar a Greedy con la diferencia de que toma en cuenta el costo
del camino hasta el nodo que se quiere explorar más la heurística, lo que lo hace más
eficiente que greedy al considerar el costo real más el estimado (heurística)
Condición de paridad para determinar si una configuración inicial tiene solución
En la implementación se menciona que para que un juego se pueda resolver el numero de
inversiones debe ser par, ¿a qué se debe esto?
Podemos entender una inversión como un par de fichas que se encuentran en un orden
incorrecto con respecto al de el objetivo, y la configuración objetivo la podemos ver como
una permutación de la inicial, dadas la propiedades de las permutaciones y la estructura de
puzzle donde solo podemos intercambiar dos posiciones la ficha que queremos mover y el
espacio vacío, una permutación con un numero par de inversiones solo puede ser
alcanzado alcanzada haciendo un numero par de otras inversiones, en este caso el juego
8-puzzle en su configuración objetivo no tiene ninguna inversión por lo que se considera
par, dada esta condición entonces se establece que para alcanzar el estado objetivo desde
una configuración dada, el numero de inversiones en esta debe ser par
Implementación de DFS sin límite (cota = 30)
Se elimino el límite de profundidad de DFS, aunque analiza todos lo nodos en una rama
esto no mejora el tiempo de búsqueda en ocasiones extendiéndolo hasta 30min de
búsqueda mientras que con la cota solo toma entre 2 y 5 minutos dependiendo de la
configuración inicial
Implemente la versión iterativa del algoritmo DFS
Para esta esta implementación se agregó una función que en caso de no encontrar la
solución dentro de la cota inicial la incrementa y llama nuevamente a la función del
algoritmo con el nuevo valor de cota para de esta forma buscar en un nivel más profundo
¿Cual algoritmo se desempeña mejor en terminos de memoria, empo y solucion encontrada?
Despues de realizar varias pruebas las cuales por mo vos de empo se realizaron en un puzzle de
3x3 ya que mas alla de este el espacio de busqueda crece muy rapidamente lo que incrementa en
gran medida el empo que le toma a cada algoritmo buscar una posible solucion pues este espacio
es de n!. A con nuacion se muestra un analisis de las pruebas realizadas
Aplicación de heurísticas para A*
Esta implementación cuenta con dos heurísticas para el algoritmo de A*: Distancia
Manhattan y Misplaced Tiles, la primera calcula la distancia manhattan de la posición de las
fichas en el estado actual con respecto a su posición en el estado ideal y la Misplaced tiles
cuenta el numero de fichas que no están en el lugar que le corresponde, de acuerdo con
las pruebas realizadas considero que la distancia manhattan es una mejor heurística pues
proporciona más información de hacia donde podría encontrarse la posible solución
