Pathfinding como computación visual: BFS, Dijkstra y A*

Laberinto en blanco y negro publicado como render digital
Fotografía de A Chosen Soul · Unsplash (licencia gratuita). Referencia de búsqueda de caminos; render de tercero, no fotografía de algoritmo. · Ver imagen original

Cuando una ruta aparece sobre un mapa parece que el algoritmo ha «visto» corredores, paredes y destinos. No es así. El algoritmo ve un grafo: vértices, aristas, costes y, a veces, una estimación de lo que falta por recorrer. La representación visual es una proyección de esas decisiones. Una animación vistosa de búsqueda no prueba que el resultado sea óptimo; una estructura de datos correcta sí permite razonar por qué debería serlo.

Este artículo compara BFS, Dijkstra y A* mediante un mismo problema de búsqueda sobre grillas, pero preservando las condiciones matemáticas que hacen válidas sus garantías. El laboratorio es una especificación de ensayo; las comparaciones de tiempo, memoria y número de expansiones no se han medido. La referencia pedagógica central es Introduction to the A Algorithm*, de Amit Patel, complementada con la teoría de grafos y algoritmos de búsqueda de caminos.

Comparación de BFS, Dijkstra y A estrella según frontera, pesos y heurística.
Diagrama editorial original. Los algoritmos tienen condiciones distintas para obtener caminos óptimos.

1. El mapa no es el grafo

Un grafo G = (V, E) contiene un conjunto de vértices V y aristas E. En una grilla, podemos representar como vértice cada celda transitable (x, y); las aristas conectan celdas entre las que se permite un movimiento. Dibujar las celdas no define las aristas. Dos mapas visualmente iguales pueden inducir grafos diferentes si uno permite diagonales, otro prohíbe cruzar esquinas o asignan costes distintos a terrenos y movimientos.

Consideremos un tablero cuadrado. Con conectividad de cuatro vecinos, desde (x,y) podemos movernos a (x±1,y) o (x,y±1), siempre que el destino sea válido. Si añadimos diagonales, ahora existen otras cuatro aristas por celda. El coste habitual de un paso ortogonal puede ser 1 y el diagonal √2, pero son elecciones de modelado. Si ambas direcciones cuestan 1, cambia el problema óptimo y cambia la heurística admisible.

Un muro puede bloquear vértices, aristas o ambos. En particular, avanzar diagonalmente entre dos celdas ortogonales bloqueadas constituye corner cutting; permitirlo o impedirlo debe ser una política explícita, no un efecto accidental del bucle de vecinos. Para comparar algoritmos, el grafo y las reglas de movimiento tienen que ser idénticos.

Peso de arista y coste de nodo

Dijkstra y A* minimizan la suma de pesos de aristas en una ruta. Un coste asociado a terreno puede convertirse en coste de entrada a la celda o en un promedio de costes de ambas celdas, pero cada transformación cambia la interpretación. Si un terreno peligroso cuesta 5 y uno normal 1, la ruta de menos pasos puede ser más cara que una vuelta más larga.

No confundamos la longitud geométrica (metros), cantidad de pasos y coste agregado (tiempo, energía, riesgo). Si la UI presenta «ruta más corta» debe aclarar en qué métrica.

Ilustración conceptual de búsqueda de caminos en una cuadrícula: inicio, camino y objetivo.
Ilustración conceptual original: síntesis visual del tema del artículo, no captura ni prueba ejecutada.

2. BFS: la distancia por número de aristas

Breadth-First Search explora por capas de profundidad. Comienza con el origen en una cola FIFO y registra cuándo descubre un vecino por primera vez. Todos los vértices a distancia d aristas se descubren antes de cualquier vértice a distancia mayor. Esta propiedad se prueba por inducción sobre las extracciones de la cola.

cola ← [inicio]
visitados ← {inicio}
padre[inicio] ← ninguno

mientras cola no esté vacía:
    actual ← quitar_primero(cola)
    si actual = meta: terminar con éxito
    para vecino de actual, en orden estable:
        si vecino no está bloqueado y vecino no fue visitado:
            visitados.agregar(vecino)
            padre[vecino] ← actual
            agregar_al_final(cola, vecino)

BFS es completo en un grafo finito y obtiene una ruta con el mínimo número de aristas; solo minimiza coste total si todas las aristas relevantes tienen el mismo coste positivo. Si los costes varían, la capa más cercana no equivale a la más barata. Su coste temporal es O(V + E) con listas de adyacencia y estructura FIFO; requiere O(V) espacio para visitados, predecesores y cola en el peor caso.

La visualización característica es una onda casi concéntrica: colorear un vértice como «descubierto» cuando entra en cola y como «expandido» cuando sale. Esos dos estados no son equivalentes. La frontera no representa los nodos ya cerrados; es lo que falta por expandir.

3. Dijkstra: elegir el coste confirmado más pequeño

Si las aristas tienen pesos no negativos, BFS ya no dispone de la propiedad correcta de capas. Dijkstra sustituye la FIFO por una cola de prioridad mínima y mantiene una distancia tentativa g(v) para cada vértice. Inicializa g(inicio) = 0 y el resto en infinito. Cada vez que encuentra un camino más barato hacia v, realiza la operación de relajación:

si g(u) + peso(u, v) < g(v):
    g(v) ← g(u) + peso(u, v)
    padre[v] ← u
    insertar_o_actualizar(v, prioridad = g(v))

Cuando extraemos un nodo con la menor distancia tentativa válida y sus aristas son no negativas, esa distancia puede considerarse definitiva. La justificación es sencilla: cualquier ruta alternativa que todavía pase por un vértice pendiente no puede acumular menos coste si todos sus incrementos futuros son no negativos.

En una implementación práctica con heapq o priority_queue, suele insertarse una entrada nueva en lugar de disminuir una clave ya existente. Por tanto, puede haber duplicados obsoletos en el heap. Debemos descartar entradas cuyo coste ya no coincida con el mejor conocido o nodos que hayan sido expandidos de manera definitiva. Un pseudocódigo sin esta comprobación oculta un problema real de implementación.

Con heap binario, la complejidad típica se expresa O((V + E) log V) para una implementación con actualización de prioridades; las cotas precisas cambian cuando hay inserciones duplicadas (log E) y según cómo se representen los vértices y se cuenten operaciones. En grillas dispersas E = O(V), ambas notaciones se simplifican a orden O(V log V).

Contraejemplo a BFS: desde S hay una arista directa a G de coste 10, y otra a A de coste 1, seguida de A → G de coste 1. BFS elige la ruta de una arista; Dijkstra encuentra el coste 2. No es un fallo de BFS: se aplicó a un objetivo diferente del que resuelve.

Dijkstra no es apropiado para aristas negativas en su formulación habitual. Si el grafo contiene costes negativos, primero hay que revisar qué significa la métrica y si existe un ciclo de coste negativo; en los casos generales se necesitan otros algoritmos, como Bellman–Ford. No intentes «arreglarlo» desactivando validaciones de distancia.

4. A*: usar información sin sacrificar correctitud

A* agrega una estimación del coste desde cada nodo hasta la meta, llamada h(n). Ordena la frontera por:

f(n) = g(n) + h(n)

g(n) = coste mínimo encontrado desde el origen hasta n
h(n) = estimación del coste restante de n a la meta

Si h(n) = 0 para todos los nodos, A* se comporta como Dijkstra con diferencias posibles de desempate. Con una estimación útil, busca primero estados prometedores sin ignorar lo que ya costó llegar hasta ellos.

La palabra importante es admisible: para cada nodo, h(n) no debe sobreestimar el coste real mínimo restante h*(n). Así, h(n) ≤ h*(n). Una heurística es consistente si h(u) ≤ w(u,v) + h(v) para cada arista u → v, y h(meta)=0. Consistencia implica admisibilidad en los casos estándar y permite que los valores g de los nodos cerrados se traten como definitivos.

Con una heurística admisible pero inconsistente, A* con búsqueda en grafo puede seguir siendo óptimo si reabre nodos cuando descubre rutas mejores y maneja adecuadamente la terminación. La afirmación «basta con que h sea admisible» es incompleta cuando la implementación prohíbe reabrir estados. Para el ejemplo de este artículo usaremos heurísticas consistentes y costes no negativos.

Qué heurística corresponde a cada grilla

Sean dx = |x_meta − x| y dy = |y_meta − y|, con longitud de celda 1 y coste por distancia unitaria de al menos 1:

Movimiento permitidoCosteHeurística habitual
Solo cuatro direccionesCada paso 1Manhattan: dx + dy
Ocho direccionesDiagonal también 1Chebyshev: max(dx,dy)
Ocho direccionesRecto 1, diagonal √2Octile: dx + dy + (√2 − 2) min(dx,dy)
Distancia geométrica libreCoste al menos distancia euclidianaEuclidiana: sqrt(dx² + dy²)

Cada fórmula supone las reglas y pesos indicados. Con terreno ponderado cuyo coste mínimo por unidad de distancia es c_min > 0, una heurística geométrica puede multiplicarse por c_min para conservar una cota inferior. Con costes cero, multiplicar por un mínimo cero da una heurística trivial pero segura. No utilizar Manhattan sin más en una grilla de ocho vecinos: cuando la diagonal cuesta 1 o √2, Manhattan puede sobreestimar la ruta disponible.

Una heurística multiplicada por w > 1 se conoce en variantes como Weighted A*; puede reducir exploraciones en ciertos escenarios a cambio de abandonar la garantía de optimalidad estricta, salvo garantías adicionales de la variante concreta. No se debería mezclar esa variante con A* admisible en un benchmark sin etiqueta.

5. Un kernel de referencia en Python

El siguiente fragmento implementa búsqueda guiada por prioridad sobre un grafo explícito finito, con pesos no negativos, entradas obsoletas descartadas y reapertura implícita cuando g mejora. Con heuristic = 0 actúa como Dijkstra; con una heuristic admisible adecuada se usa como A*. No genera visualizaciones; devuelve camino, coste y número de expansiones para instrumentación. En un grafo general con heurística inconsistente deben examinarse además las condiciones de terminación de la implementación.

import heapq
import itertools
import math


def shortest_path(graph, start, goal, heuristic=lambda node: 0.0):
    best = {start: 0.0}
    parent = {start: None}
    counter = itertools.count()
    queue = [(heuristic(start), next(counter), 0.0, start)]
    expanded = 0

    while queue:
        _priority, _seq, cost, node = heapq.heappop(queue)
        if cost != best.get(node, math.inf):  # entrada obsoleta
            continue
        expanded += 1
        if node == goal:
            path = [node]
            while parent[node] is not None:
                node = parent[node]
                path.append(node)
            return list(reversed(path)), cost, expanded

        for neighbor, weight in graph.get(node, ()):
            if not math.isfinite(weight) or weight < 0:
                raise ValueError("Se requieren pesos finitos no negativos")
            candidate = cost + weight
            if candidate < best.get(neighbor, math.inf):
                best[neighbor] = candidate
                parent[neighbor] = node
                priority = candidate + heuristic(neighbor)
                heapq.heappush(
                    queue, (priority, next(counter), candidate, neighbor)
                )
    return None, math.inf, expanded

El desempate mediante counter evita depender de que los nodos sean comparables. Usar igualdad exacta para detectar una entrada obsoleta es apropiado aquí porque se almacena el mismo valor candidate calculado al insertarla; no es una prueba general de igualdad numérica entre dos cálculos independientes. Además, el algoritmo no sustituye validaciones del grafo, políticas de finalización bajo heurísticas inconsistentes ni un test unitario de optimalidad. Su contrato de ejemplo es: grafo finito, pesos no negativos, heuristic consistente y heuristic(meta)=0.

En una implementación con capacidades adicionales se puede guardar un evento por transición: discover, decrease, expand, goal. Esas trazas permiten reproducir las imágenes de frontera sin mezclar tiempo de animación con tiempo de búsqueda.

6. La ruta es un árbol de predecesores, no una lista que aparece sola

Tanto BFS como Dijkstra y A* pueden reconstruir el resultado almacenando parent[v] cuando descubren o mejoran una ruta. Desde la meta se recorren los padres hasta el origen y se invierte la secuencia. Si origen y meta son el mismo nodo, la respuesta contiene solo ese nodo con coste cero. Si la meta es inaccesible, el algoritmo devuelve explícitamente «sin ruta»; no una ruta vacía que la UI pueda interpretar como éxito.

Un grafo puede tener varias rutas óptimas. El orden de vecinos, el orden de inserción y la regla de desempate pueden cambiar cuál se devuelve, aunque el coste sea idéntico. En una animación, dos ejecuciones con rutas diferentes no implican que una sea incorrecta. Para reproducibilidad visual, fijar orden de vecinos y desempates.

7. Qué significa «más rápido» en una visualización

Hay al menos cuatro mediciones distintas:

  1. Nodos expandidos: cuántos estados salieron válidamente de la frontera y fueron procesados.
  2. Máximo de frontera: tamaño máximo de la cola lógica o del heap físico, incluyendo si se cuentan entradas obsoletas.
  3. Tiempo de búsqueda: sin pintar celdas, animación ni latencia de eventos del navegador.
  4. Coste del camino: suma exacta de los pesos de arista de la ruta reconstruida.

A* no expande siempre menos nodos que Dijkstra en cualquier grafo o implementación; la heurística, el desempate, los obstáculos y los costes influyen. Una heurística mal escalada puede dar un resultado incorrecto si se pierde la admisibilidad. Tampoco podemos comparar tiempos a partir de una animación con un paso visual artificial por nodo.

La complejidad asintótica no es una predicción de segundos. BFS tiene el límite O(V+E) y es apropiado cuando los costes son uniformes. Dijkstra usa un heap para orden de coste. A* usa la misma maquinaria con una estimación y su uso de memoria puede seguir siendo grande; una heurística perfecta no vuelve trivial la generación de vecinos ni el coste de la frontera en todos los problemas.

8. Diseñar un laboratorio comparable

Propondría un conjunto de tableros con semilla y obstáculos fijados, tamaños de 50×50 a 500×500, tres reglas de movimiento y dos distribuciones de costes. Cada ejecución registraría hash del tablero, origen/meta, versión del algoritmo, política de desempate, tipo de heap, hardware, warm-up y repeticiones. Los siguientes escenarios separan preguntas diferentes:

EscenarioComparación válidaInvariante esperado
Grilla de cuatro vecinos y coste 1BFS / Dijkstra / A* ManhattanMismo coste óptimo, no necesariamente mismo camino
Terreno con costes positivos variablesDijkstra / A* con heurística admisibleMismo coste óptimo
Ocho vecinos, diagonal √2Dijkstra / A* octileSin sobreestimación heurística
h = 0Dijkstra / A*Coste igual y exploración equivalente salvo desempates
Meta inaccesibleLos tres, bajo reglas válidasResultado «sin ruta»
Origen = metaLos tresCoste 0, un nodo

Es crucial comparar coste y no solo longitud de ruta. En un mapa ponderado, una ruta óptima puede visitar más nodos que una ruta cara. Para la evaluación visual, conservaríamos tres capas: obstáculo/transitabilidad; descubierto/frontera/expandido; y ruta final. La UI debería distinguir tiempo real de cálculo y tiempo artificial de la animación, y permitir pausar sin alterar el orden del algoritmo.

Un test adicional de propiedades generaría grafos pequeños aleatorios con pesos no negativos. Dijkstra sería el oráculo para verificar el coste producido por A* con heurísticas consistentes; en grafos con pesos unitarios BFS serviría como otro oráculo. Esto detecta errores que una demo de un único laberinto jamás revelaría.

9. Dónde termina este modelo

Las grillas son convenientes para enseñar, pero un mundo real puede representarse con navigation meshes, regiones jerárquicas, grafos de carreteras, costes que cambian con el tiempo y cuerpos con tamaños o radios de giro diferentes. A* sobre el grafo que le damos no resuelve automáticamente colisiones continuas ni movimientos cooperativos. Un personaje puede seguir un camino topológicamente válido y chocar físicamente si no se modelan sus dimensiones.

Los tres algoritmos responden preguntas precisas. BFS minimiza aristas con costes uniformes; Dijkstra minimiza pesos no negativos sin necesitar una meta heurística; A* combina coste observado con una cota inferior para dirigirse a la meta. Visualizarlos sirve para comprender su búsqueda, siempre que la visualización respete el grafo y los invariantes.

Lecturas y fuentes

Ampliaciones visuales futuras: comparativas animadas de las fronteras, nodos g/h/f, reconstrucción del camino y casos diagonales. La portada y el diagrama comparativo ya están disponibles; aún no se ha desarrollado un visualizador interactivo.