Rutas Paso a Paso
Elige un algoritmo y míralo trabajar sobre un mapa de 15 cruces. Cada paso resalta la línea de código que se está ejecutando, explica qué hace y muestra cómo cambian la cola, las distancias y los padres de cada nodo.
Lienzo
Grafo
Clic en un nodo fija:
Sin descubrir
En la frontera
Nodo actual
Explorado
Camino final
Origen
Destino
0 / 0
Qué está pasando
Código en Python
clic en una línea = explicación
bfs()
Línea
Estructura de datos
Cola (FIFO)
Bitácora
Historial de pasos
Memoria del algoritmo
La fila naranja cambió en este pasoTabla de nodos
Mismo mapa, mismo origen y destino
Comparativa de los cuatro
Corremos los cuatro algoritmos sobre el grafo actual. Fíjate en cuántos nodos tuvo que explorar cada uno y si el camino que encontró es el más barato. Cambia el origen, el destino o genera otro grafo y la tabla se recalcula.
Para estudiar
Cómo piensa cada algoritmo
Vocabulario
Conceptos clave
GrafoConjunto de nodos (vértices) unidos por aristas. Un mapa de calles es un grafo: los cruces son nodos y las calles son aristas.
PesoCosto de recorrer una arista: distancia, tiempo o dinero. Aquí es el número en la etiqueta de cada calle.
FronteraNodos ya descubiertos que todavía no se exploran. Vive en la cola, pila o cola de prioridad.
PadreDesde qué nodo llegamos a otro. Siguiendo los padres hacia atrás desde el destino se reconstruye el camino.
Relajar una aristaPreguntar si pasar por el nodo actual mejora la distancia conocida al vecino; si sí, se actualiza.
Heurística h(n)Estimación de cuánto falta para llegar a la meta. A* usa la distancia en línea recta, que nunca sobreestima.
AdmisibleUna heurística que nunca dice que falta más de lo que realmente falta. Con ella, A* garantiza encontrar el camino óptimo.
ÓptimoEl camino de menor costo total posible entre origen y destino.