Navegación y Búsqueda Ciega en Grafos: BFS vs DFS en Python
¿Qué es la Búsqueda Ciega?
En la Inteligencia Artificial, la búsqueda ciega (o búsqueda no informada) se refiere a algoritmos que exploran el espacio de estados sin poseer ningún conocimiento adicional sobre la ubicación del objetivo o de cuán lejos se encuentra la meta. Su única capacidad radica en distinguir si un nodo actual es la solución y en generar los estados sucesores permitidos. Aunque son computacionalmente costosos por su fuerza bruta, garantizan una exploración rigurosa y son la base teórica de algoritmos más avanzados.
Para esta práctica, modelamos un mapa con 7 ciudades conectadas, donde probaremos los dos paradigmas principales: BFS (Búsqueda en Amplitud) y DFS (Búsqueda en Profundidad).
Desarrollo Práctico: Completando los Algoritmos
1. Búsqueda en Amplitud (BFS — Cola)
El algoritmo BFS se basa en la premisa de “primero en entrar, primero en salir” (FIFO). Para implementarlo, utilizamos una lista en Python a la que extraemos siempre el primer elemento utilizando cola.pop(0). Esto fuerza al código a evaluar a todos los vecinos inmediatos de la ciudad actual antes de avanzar a ciudades más lejanas.
# Fragmento del código implementado (BFS)
while cola:
camino_actual = cola.pop(0) # Extraer usando lógica FIFO
nodo_actual = camino_actual[-1]
if nodo_actual not in visitados:
if nodo_actual == nodo_objetivo:
return camino_actual
visitados.add(nodo_actual) # Control de ciclos
for vecino in grafo.get(nodo_actual, []):
if vecino not in visitados:
nuevo_camino = list(camino_actual)
nuevo_camino.append(vecino)
cola.append(nuevo_camino)
2. Búsqueda en Profundidad (DFS — Pila)
El algoritmo DFS opera bajo el principio “último en entrar, primero en salir” (LIFO). Para lograr este comportamiento en Python, extrajimos siempre el último elemento agregado a la lista utilizando pila.pop(-1). Esto obliga al algoritmo a sumergirse hasta el final de una rama de ciudades antes de retroceder a explorar otras alternativas.
Get Christophervengador’s stories in your inbox
Join Medium for free to get updates from this writer.
# Fragmento del código implementado (DFS)
while pila:
camino_actual = pila.pop(-1) # Extraer usando lógica LIFO
nodo_actual = camino_actual[-1]
if nodo_actual not in visitados:
if nodo_actual == nodo_objetivo:
return camino_actual
visitados.add(nodo_actual) # Control de ciclos
for vecino in grafo.get(nodo_actual, []):
if vecino not in visitados:
nuevo_camino = list(camino_actual)
nuevo_camino.append(vecino)
pila.append(nuevo_camino)
Ejecución y Trazabilidad
Al ejecutar ambos algoritmos solicitando una ruta desde Aris hasta Galo, observamos cómo gestionan la memoria y el descubrimiento:
- El recorrido BFS descubrió primero las ciudades vecinas (Bora, Cali), luego las de segundo nivel (Dora, Elio, Faro) y finalmente encontró Galo, devolviendo la ruta:
['Aris', 'Bora', 'Elio', 'Galo']. - El recorrido DFS se adentró inmediatamente por la última ruta agregada a su pila (Cali), y profundizó hacia Faro y finalmente Galo, encontrando la solución muy rápido y devolviendo la ruta:
['Aris', 'Cali', 'Faro', 'Galo'].
¿Por qué BFS y DFS arrojaron resultados o rutas diferentes?
Aunque en este mapa específico ambos algoritmos entregaron rutas de igual longitud (3 saltos), lo hicieron por arquitecturas distintas. BFS (al usar una cola) buscó horizontalmente de manera concéntrica, garantizando el hallazgo del camino más corto. DFS (al usar una pila) ignoró la primera rama apenas vio la segunda y profundizó verticalmente; si la rama de “Cali” hubiera tenido 50 ciudades conectadas sin salida, DFS se habría quedado atrapado procesando todo ese camino antes de volver al inicio.
¿En qué escenario de la vida real usaría cada uno?
- Utilizaría BFS (Amplitud) en escenarios donde encontrar el camino más corto o superficial es crítico, como redes de telecomunicaciones (enrutamiento de paquetes), o para buscar la conexión de amigos más cercana en redes sociales.
- Emplearía DFS (Profundidad) en problemas donde las soluciones son abundantes y profundas, o cuando hay estrictas limitaciones de memoria (RAM), como al resolver laberintos acotados, validar sintaxis de código (árboles de sintaxis abstracta) o simulaciones de decisiones secuenciales finitas como rompecabezas.
