En el tema anterior vimos que la búsqueda sistemática es una estrategia exhaustiva para explorar todas las posibilidades dentro de un espacio de estados. En este subtema nos enfocaremos en uno de los algoritmos de exploración: el algoritmo de búsqueda en profundidad o DFS por sus siglas en inglés Depth First Search. Quédate y descubre una aplicación interesante de este algoritmo: los videojuegos.
El algoritmo de Búsqueda en profundidad DFS, explora lo más profundo posible por una ruta del grafo o rama del árbol antes de retroceder y probar otra rama. Para explicar esto con un ejemplo, imaginemos nuevamente un laberinto, y para explorarlo, vamos siguiendo un pasillo hasta encontrar una pared o una bifurcación, y luego retrocediendo para explorar otro pasillo.
En la figura 3.8 podemos observar gráficamente lo que significa la profundidad en un grafo. De esta forma, el algoritmo exploraría primero A, después escogería una primera rama y la exploraría hasta su nodo más profundo. De tal forma que el siguiente nodo a explorar sería B, luego D, seguido de G y H antes de retroceder y explorar la siguiente rama que comienza con C.
Figura 3.9
El algoritmo DFS es muy sencillo y se basa en el uso de una Pila, donde el último en entrar es el primero en salir (LIFO – Last In, First Out). Para profundizar es necesario analizar el algoritmo.
Inicialización:
Proceso de iteración:
A manera de pseudocódigo podemos escribir:
Crear pila S
Agregar origen a pila S
Mientras S no esté vacío:
Sacar nodo V de la cima de S
Si V es Meta, devolver solución
Si V no visitado:
Marcar V como visitado
Para cada hijo de V:
Agregar hijo a la pila
VIDEO Introducción:
Video: Presentación del Pseudocódigo:
Video: Explicación del algoritmo DFS paso a paso:
Aplicar el algoritmo DFS al video juego PacMan de la universidad de Berkeley
En esta práctica, los estudiantes aprenderán a aplicar el algoritmo Depth-First Search (DFS) para resolver un problema de navegación en el clásico juego de Pacman desarrollado por la Universidad de Berkeley.
Objetivo:
Requerimientos: Materiales y herramientas:
Código basé del proyecto Pacman de la universidad de Berkeley, disponible en: https://ai.berkeley.edu/search.html
Introducción:
La capacidad de los agentes inteligentes para tomar decisiones y encontrar soluciones óptimas en entornos complejos es un componente esencial en los proyectos de inteligencia artificial (IA). En esta práctica, exploraremos el algoritmo de búsqueda en profundidad (Depth-First Search, DFS), una técnica clave en la exploración de espacios de estados. Aplicaremos este algoritmo para resolver problemas de navegación en el clásico juego de Pacman, desarrollado por la Universidad de Berkeley, lo que permitirá a los estudiantes comprender cómo se utiliza en escenarios prácticos.
El DFS es un algoritmo fundamental en la IA y se utiliza para explorar árboles o grafos siguiendo una estrategia de profundización. Su simplicidad lo hace aplicable en una variedad de contextos, desde el diseño de videojuegos hasta la resolución de problemas de planificación y lógica. Por ejemplo, DFS es útil en juegos para explorar rutas posibles hacia un objetivo, como en Pacman, donde un agente debe navegar por un laberinto, recoger puntos y evitar fantasmas.
Fuera de los videojuegos, el DFS tiene aplicaciones en campos como la robótica, donde los robots exploran entornos desconocidos; la bioinformática, para analizar estructuras moleculares complejas; y la informática, para tareas como análisis de grafos o búsqueda de rutas en redes de datos. Su capacidad para manejar espacios de estados grandes y complejos lo convierte en una herramienta imprescindible en el desarrollo de sistemas inteligentes.
En esta práctica, los estudiantes no solo implementarán el algoritmo DFS para guiar a Pacman en su navegación, sino que también reflexionarán sobre sus ventajas y limitaciones en comparación con otros algoritmos de búsqueda. Este ejercicio brinda una oportunidad única para conectar la teoría de la búsqueda sistemática con aplicaciones prácticas, mientras se desarrolla una comprensión más profunda de cómo las estrategias de exploración influyen en el desempeño de los agentes inteligentes.
Metodología y descripción de la actividad:
1. Preparar el Entorno
2. Explora los Archivos del Proyecto
3. Objetivo de la Práctica
Implementar el algoritmo DFS en el archivo search.py para que el agente de Pacman, controlado mediante DFS, navegue desde su posición inicial hasta una meta específica en el laberinto.
Mira estos videos para que puedas adentrarte al código del video juego de Pacman:
Video: Lo básico que debes saber de las carpetas del proyecto Pacman de la universidad de Berkeley:
Video: Los archivos importantes para automatizar al agente Pacman:
Video: Comandos básicos para probar la implementación de los algoritmos en Pacman:
Video: Funciones útiles para la solución e implementación de los problemas de búsqueda:
Entregables y Reporte Final:
Al finalizar deberán entregar los siguientes componentes para evaluar su trabajo:
Recursos: 1 Descargable
Duración: 3 Horas
Departamento de Sistemas e Informatica
sistemas@itistmo.edu.mx
“Por una tecnología propia como principio de libertad®️”
