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.
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.
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 permitido | Coste | Heurística habitual |
|---|---|---|
| Solo cuatro direcciones | Cada paso 1 | Manhattan: dx + dy |
| Ocho direcciones | Diagonal también 1 | Chebyshev: max(dx,dy) |
| Ocho direcciones | Recto 1, diagonal √2 | Octile: dx + dy + (√2 − 2) min(dx,dy) |
| Distancia geométrica libre | Coste al menos distancia euclidiana | Euclidiana: 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:
- Nodos expandidos: cuántos estados salieron válidamente de la frontera y fueron procesados.
- Máximo de frontera: tamaño máximo de la cola lógica o del heap físico, incluyendo si se cuentan entradas obsoletas.
- Tiempo de búsqueda: sin pintar celdas, animación ni latencia de eventos del navegador.
- 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:
| Escenario | Comparación válida | Invariante esperado |
|---|---|---|
Grilla de cuatro vecinos y coste 1 | BFS / Dijkstra / A* Manhattan | Mismo coste óptimo, no necesariamente mismo camino |
| Terreno con costes positivos variables | Dijkstra / A* con heurística admisible | Mismo coste óptimo |
Ocho vecinos, diagonal √2 | Dijkstra / A* octile | Sin sobreestimación heurística |
h = 0 | Dijkstra / A* | Coste igual y exploración equivalente salvo desempates |
| Meta inaccesible | Los tres, bajo reglas válidas | Resultado «sin ruta» |
| Origen = meta | Los tres | Coste 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
- Amit Patel — Introduction to the A Algorithm*. Modelo de grafos, fronteras, reconstrucción y comparación interactiva.
- Amit Patel — Implementation of A. Estructuras de datos y decisiones de implementación.
- Amit Patel — Heuristics. Distancias Manhattan, octile y garantías.
- MIT OpenCourseWare — Introduction to Algorithms. Base formal para búsqueda, grafos y prioridades.
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.