Mejorando las heurísticas de A* para una búsqueda de caminos más rápida
Improving Heuristics for A* Pathfinding
Red Blob Games explica cómo mejorar la heurística de A* para acelerar la búsqueda de caminos. La idea clave es usar puntos de referencia (landmarks) y la desigualdad del triángulo para obtener mejores límites inferiores del costo real, reduciendo así los nodos explorados. El artículo incluye demostraciones interactivas, consejos para la colocación de landmarks y ejemplos de implementación.
La idea clave aquí es que es poco práctico precalcular todos los costos a todas las ubicaciones, pero si hemos precalculado los costos a una ubicación específica, podemos usar eso para estimar el costo a una ubicación diferente.
- simonw
> Aprendí sobre esta técnica en 2007, y luego intenté escribir sobre ella en 2015. Me di cuenta de que no la entendía lo suficiente como para poder explicarla. La estudié de forma intermitente en 2016, 2018, 2019, 2022, 2024 y 2026. Abandoné y reinicié esta página muchas veces. Y para 2026 creo que la entiendo lo bastante bien como para escribir esta página.
Excelente.
- mpmisko
Vaya, ¿no es A* divertido e intuitivo?
Sería interesante profundizar en los límites y las buenas propiedades para conjuntos de landmarks.
Imagino que si,
- Cada nodo está al menos a X coste/distancia de un landmark
- Los landmarks no están a menos de Y coste/distancia entre sí
Se puede empezar a prometer mucho sobre el tamaño de tu conjunto abierto en cualquier ejecución.
A* con h* (heurística perfecta) toma O(l) donde l es la longitud de la solución (podría expandir exactamente l nodos, pero resolver/adivinar empates incorrectamente podría elevarlo a un múltiplo alrededor del promedio de aristas por vértice).
Imagino que tener buenos límites significa que no tardarás más de cierta cantidad de expansiones/profundidad antes de engancharte al raíl que proporciona h* (y necesitas algo de trabajo extra para salirte también).
- Groxx
Red Blob Games tiene bastantes posts de nivel S, recomiendo encarecidamente explorar más si esto te resulta interesante.