En la clase anterior, estudiamos la búsqueda en profundidad (DFS), y siguiendo con los algoritmos de búsqueda ahora cambiaremos el enfoque para introducir un algoritmo complementario: la búsqueda en anchura o BFS por sus siglas en inglés Breadth-First Search. A diferencia de DFS, BFS explora todos los nodos a un mismo nivel antes de pasar al siguiente, lo que lo convierte en una herramienta muy efectiva para encontrar la solución más corta en términos del número de pasos en un espacio de estados. Este algoritmo es particularmente útil en problemas donde cada acción tiene el mismo costo o cuando estamos interesados en la solución óptima más cercana al estado inicial.
Durante esta clase, analizaremos en detalle cómo funciona BFS, compararemos sus características con DFS y veremos en qué tipos de problemas resulta más ventajosa esta técnica. También discutiremos los requerimientos de memoria y las implicaciones de aplicar BFS a problemas con grandes espacios de estados.
Al final de la clase, tendrás una comprensión clara de cuándo usar BFS en lugar de DFS y cómo aplicar esta estrategia en problemas como la búsqueda de caminos cortos en grafos, la resolución de laberintos y otros desafíos comunes en inteligencia artificial.
En la figura 3.8 se puede apreciar lo que gráficamente significa la anchura de un grafo. Esta representación puede ayudarnos a visualizar la forma en la que el algoritmo BFS explora el espacio de estados.
Figura 3.10
Para el espacio de estados representado en la figura 3.10 el algoritmo BFS exploraría el grafo por niveles y en el siguiente orden: primero A, después B y C luego D,E,F y al final el último nivel G,H,I,J,K,L. De lo anterior podemos concluir el principio fundamental del algoritmo: Explora primero todos los vecinos de un nodo antes de profundizar en otros niveles. Lo que lo vuelve ideal para encontrar la solución más corta en problemas donde el costo de cada paso es igual.
El funcionamiento del algoritmo BFS para organizar los nodos que debe visitar,
se basa en la estructura de colas, donde el primero en entrar es el primero en salir (FIFO first in, First out).
Ejemplos:
Para explicar a profundidad mira estos videos:
Video: Introducción al algoritmo BFS:
Video: BFS paso a paso:
| Criterio | BFS (Búsqueda en Anchura) | DFS (Búsqueda en Profundidad) |
|---|---|---|
| Estrategia de búsqueda | Explora nivel por nivel. | Explora cada rama hasta el fondo antes de retroceder. |
| Uso de memoria | Requiere más memoria, ya que almacena todos los nodos en cada nivel. | Usa menos memoria, ya que sólo necesita almacenar una rama a la vez. |
| Encontrar la solución más corta | Garantiza encontrar la solución más corta si el costo es uniforme. | No garantiza la solución más corta, sólo una solución. |
| Eficiencia en grafos profundos | Menos eficiente en grafos muy profundos o infinitos. | Más eficiente en grafos donde la solución está en ramas profundas. |
| Aplicaciones | Problemas donde la solución más corta es importante, como rutas mínimas. | Exploración exhaustiva o problemas donde cualquier solución es suficiente. |
Aplicar el algoritmo BFS al agente Pacman
En esta práctica, los estudiantes aprenderán a aplicar el algoritmo Breadth-First Search (BFS) para resolver un problema de navegación en el clásico juego de Pacman desarrollado por la Universidad de Berkeley. Utilizaremos el entorno de Python que proporciona el código base de Pacman en el proyecto de IA de Berkeley para buscar una solución que permita a Pacman llegar a una meta específica utilizando el enfoque de búsqueda en anchura.
Objetivos, Saberes y Habilidades por desarrollar:
Requisitos:
Código base del proyecto Pacman de Berkeley disponible en Pacman AI Projects https://ai.berkeley.edu/search.html
Introducción:
En esta práctica, exploraremos cómo la inteligencia artificial puede resolver problemas complejos mediante la aplicación de algoritmos de búsqueda. Nos centraremos en el algoritmo de búsqueda en anchura, una técnica fundamental en la resolución de problemas que consiste en explorar todos los nodos a un nivel de profundidad antes de pasar al siguiente nivel.
Para ilustrar este concepto, utilizaremos el clásico juego de Pacman. Nuestro objetivo será desarrollar una inteligencia artificial para que Pacman pueda encontrar el camino más corto hasta una meta específica, evitando a los fantasmas. Pacman es un entorno ideal para explorar conceptos fundamentales de IA, ya que presenta una serie de obstáculos y metas que requieren una toma de decisiones precisa y eficiente.
A través de esta práctica, no solo aprenderemos a implementar y utilizar BFS, sino que también comprenderemos su aplicabilidad en escenarios más amplios como la robótica, la planificación de rutas y la optimización de sistemas en tiempo real.
Mediante la simulación del algoritmo en un entorno como Pacman, podemos visualizar cómo los agentes toman decisiones sobre cómo moverse de un punto a otro de manera óptima, lo que refleja aplicaciones reales en la navegación autónoma, la resolución de problemas logísticos y la búsqueda de información en grandes bases de datos.
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 BFS en el archivo search.py para que el agente de Pacman, controlado mediante BFS, navegue desde su posición inicial hasta una meta específica en el laberinto.
Implementar el algoritmo BFS en el archivo search.py para que el agente de Pacman, controlado mediante BFS, navegue desde su posición inicial hasta una meta específica en el laberinto.
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: 2 Horas
Departamento de Sistemas e Informatica
sistemas@itistmo.edu.mx
“Por una tecnología propia como principio de libertad®️”
