Heurística de landmarks para optimizar búsqueda de caminos con A*

· Programación

  1. 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.
  2. 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).
  3. 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.
  4. 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.
  5. 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

Leer el original

Más en Programación