Definitivo
En la cola
Aristas revisadas

  • Actual
  • En la cola
  • Definitivo
  • Camino
  • Estimación en línea recta
Un clic en un nodo fija

Más sobre la búsqueda A*

Búsqueda A*

La búsqueda A* encuentra un camino más corto de un origen a un destino, como el algoritmo de Dijkstra, pero sabe más o menos dónde está el destino. Cada nodo recibe una estimación de la distancia restante, la línea recta hasta el destino, y la búsqueda sigue siempre desde el nodo con la menor distancia hasta ahora más esa estimación. Haz clic en un nodo para empezar desde él, elige un destino y avanza paso a paso para ver cómo la búsqueda se dirige al destino y deja intactas esquinas enteras del grafo. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Haz clic en un nodo para que sea el origen; cambia el clic a Destino y haz clic en otro nodo para que sea el destino. El número de cada arista es su longitud, el de cada nodo su distancia hasta ahora, y la línea discontinua la estimación en línea recta de la distancia restante. La fila bajo el grafo es la cola, primero la puntuación más baja, con la puntuación de cada uno: la distancia hasta ahora más la estimación. Nuevo grafo crea otro grafo; elige cuántos nodos y aristas tiene. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Haz clic en un nodo para que sea el origen. Cambia el clic a Destino y haz clic en otro nodo para que sea el destino.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
  3. Observa las puntuaciones de la cola y la estimación en línea recta discontinua. Al final, compara los nodos que necesitó A* con los del algoritmo de Dijkstra.

Cómo funciona la búsqueda A*

Da al origen distancia 0 y ponlo en una cola. Cada nodo de la cola tiene una puntuación: su distancia hasta ahora más una estimación de la distancia restante. Repite: toma el nodo con la puntuación más baja y marca su distancia como definitiva. Si es el destino, para. Si no, para cada vecino que no sea definitivo, suma la longitud de la arista a la distancia del nodo; si es menor que la distancia hasta ahora del vecino, bájala, recuerda el nodo como el camino hasta él y pon al vecino en la cola con su nueva puntuación.

Por qué la estimación nunca debe ser demasiado larga

A* encuentra un camino más corto siempre que la estimación nunca diga que el destino está más lejos de lo que está en realidad: una estimación admisible. La línea recta lo es, porque ninguna carretera entre dos lugares es más corta que la línea recta. Una estimación demasiado larga puede hacer que A* se salte la mejor ruta; una estimación de 0 en todas partes convierte A* en el algoritmo de Dijkstra, que es seguro pero busca en todas las direcciones. Cuanto mejor es la estimación, menos nodos necesita A*. En la app, cada arista mide lo que mide su dibujo, redondeado hacia arriba, así que la línea recta es una estimación segura.

Preguntas frecuentes

¿Qué es la búsqueda A*?

Un algoritmo de búsqueda de caminos que encuentra un camino más corto de un origen a un destino. Funciona como el algoritmo de Dijkstra, pero ordena su cola por la distancia hasta ahora más una estimación de la distancia restante, así que se dirige al destino en lugar de extenderse en todas las direcciones.

¿Qué es una heurística admisible?

Una estimación de la distancia al destino que nunca es mayor que la distancia más corta real. Con una estimación admisible, A* siempre encuentra un camino más corto. La distancia en línea recta en un mapa es el ejemplo clásico.

¿Es A* más rápido que el algoritmo de Dijkstra?

Normalmente sí, cuando necesitas el camino a un solo destino y tienes una buena estimación: A* hace definitivos menos nodos, porque los nodos alejados del destino reciben puntuaciones altas. Con una estimación de 0 hace exactamente lo mismo que el algoritmo de Dijkstra. El algoritmo de Dijkstra es mejor opción cuando necesitas las distancias a todos los nodos.

¿Dónde se usa A*?

En videojuegos para mover personajes esquivando obstáculos, en planificadores de rutas, en la planificación de movimientos de robots y en solucionadores de rompecabezas como el 15-puzzle, donde la estimación cuenta lo lejos que están las fichas de su sitio.

¿Se envía mi grafo a algún sitio?

No. El grafo se crea y se recorre en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor