🌸 3.8.2 BÚSQUEDA EN ANCHURA (BFS)

 

   Fundamento teórico

La búsqueda en anchura (Breadth First Search, BFS) es un algoritmo que explora todos los nodos vecinos de un nivel antes de pasar al siguiente nivel.

Utiliza una estructura de cola (queue), lo que garantiza que los nodos se procesen en el orden en que fueron descubiertos.

BFS es especialmente útil cuando se busca la ruta más corta en términos de número de pasos.

Ejemplo:
Encontrar la ruta más corta en un mapa o red de conexiones.

$f(x)=\text{nivel del nodo explorado en BFS}$

Características principales

• 📌 Explora por niveles.
• 📌 Usa estructura de cola.
• 📌 Garantiza solución más corta (si todas las aristas pesan igual).
• 📌 Consume más memoria que DFS.
• 📌 Completo y óptimo en muchos casos.

 Importancia

• Permite encontrar rutas óptimas.
• Base de sistemas de navegación.
• Fundamental en inteligencia artificial.

 Ventajas

• Encuentra la solución más corta.
• Es completo.
• Ordenado y sistemático.

Limitaciones

• Alto consumo de memoria.
• Puede ser lento en grafos grandes.

Aplicaciones

• GPS
• Redes sociales
• IA en juegos
• Análisis de redes

Video explicativo:

Práctica:

Actividad: Simulación BFS

Dibuja un árbol de 6 nodos y muestra cómo BFS lo recorre nivel por nivel.

📄 Ver práctica en PDF

Evaluación:

1. ¿Qué es BFS?
2. ¿Qué estructura utiliza?
3. ¿Qué ventaja tiene sobre DFS?
4. ¿En qué casos se usa?
5. Da un ejemplo real.

 Conclusión:

La búsqueda en anchura permite explorar sistemas de forma ordenada por niveles, garantizando soluciones óptimas en muchos problemas de inteligencia artificial.

 Referencias APA 7

• Russell, S., & Norvig, P. (2021). Artificial intelligence: A modern approach.
• Cormen, T. et al. (2009). Introduction to algorithms.