Heurística de landmarks para optimizar búsqueda de caminos con A*
- A* usa heurística para guiar la búsqueda de caminos más cortos, pero falla cuando la heurística apunta en dirección incorrecta si desconoce la estructura del mapa.
- Se puede reutilizar una heurística 'perfecta' precomputada hacia un punto landmark (L) para otros destinos aplicando la desigualdad del triángulo: cost(B, X) ≥ cost(B, L) - cost(X, L).
- Un solo landmark solo es útil cuando está 'después' del destino en el camino B→X→L; se requieren múltiples landmarks para cubrir diferentes pares de inicio-destino.
- La implementación requiere: ejecutar Dijkstra desde cada landmark, almacenar costos en array cost[nodeId][landmarkId], y modificar la función heurística para tomar el máximo entre la heurística base y los límites inferiores de cada landmark.
- Las demostraciones en mapas de Dragon Age, Cogmind y laberintos muestran reducciones significativas en nodos explorados, especialmente en laberintos donde A* tradicional funciona mal; la ubicación óptima de landmarks depende del patrón de inicio-destino del proyecto.
pathfinding · heuristica · algoritmo astar · grafos · optimizacion
Más en Programación
- Refactoring Python Code With an AI Agent
- Quiz interactivo sobre análisis de archivos CSV en Python
- Anchor positioning en CSS: posicionamiento relativo sin JavaScript
- Técnicas de combinación de datos en pandas: merge(), join() y concat()
- Almacenamiento de datos con archivos planos, SQLite y SQLAlchemy en Python