¿Cómo implementarías A* en una cuadrícula ponderada?

1. Problema

Implementa aStar(grid, start, goal). Una celda está bloqueada o tiene un costo de tránsito positivo. Los movimientos son en cuatro direcciones; entrar en una celda vecina suma el costo de dicha celda. Devuelve la ruta y el costo total, o NO_PATH cuando el objetivo sea inalcanzable.

2. Restricciones y aclaraciones

• Las coordenadas son pares de enteros (row, column) dentro de la cuadrícula; el punto de inicio y el objetivo deben ser transitables.
• Una heurística nunca debe sobreestimar el costo restante si el resultado debe ser óptimo. Con movimiento en cuatro direcciones y un costo mínimo de celda de m, la distancia de Manhattan multiplicada por m es admisible.
• Utiliza un min-heap ordenado por f, seguido de un criterio de desempate determinista por coordenadas. El heap puede contener entradas obsoletas después de que se encuentre un mejor valor de g.
• Los costos de celda negativos no son válidos. Una implementación de un solo hilo es suficiente; las actualizaciones concurrentes de la cuadrícula requieren una instantánea (snapshot) o una verificación de versión.

3. Enfoque principal

Mantén gScore para registrar el costo conocido más bajo hacia cada celda y cameFrom para la reconstrucción. Inserta (f, g, cell) cada vez que una relajación mejore gScore. Al extraer un elemento (pop), descarta el nodo si su valor almacenado de g es mayor que el valor actual de gScore; este enfoque perezoso (lazy) evita la necesidad de una operación arbitraria de disminución de clave (decrease-key) en el heap.

Para una heurística consistente, la primera extracción no obsoleta del objetivo es óptima. Si la heurística es únicamente admisible, permite que un nodo cerrado se vuelva a abrir cuando se descubra un g más bajo. Red Blob Games describe este patrón de cola de prioridad y el efecto de la calidad de la heurística en el trabajo realizado.

4. Implementación de referencia

aStar(grid, start, goal):
  require traversable(start) and traversable(goal)
  gScore = map(default=INFINITY)
  cameFrom = map()
  gScore[start] = 0
  open = minHeap((heuristic(start, goal), 0, start))

  while open is not empty:
    (f, queuedG, current) = open.pop()
    if queuedG != gScore[current]: continue   // stale entry
    if current == goal:
      return reconstruct(cameFrom, goal), gScore[goal]

    for next in traversableNeighbors(current):
      tentative = gScore[current] + grid[next].cost
      if tentative < gScore[next]:
        gScore[next] = tentative
        cameFrom[next] = current
        open.push((tentative + h(next, goal), tentative, next))

  return NO_PATH

reconstruct sigue cameFrom desde el objetivo hasta el inicio e invierte las celdas recolectadas. La cola de prioridad solo programa los candidatos; gScore sigue siendo la fuente de la verdad.

5. Complejidad y compensaciones

Con V celdas alcanzables y E aristas hacia vecinos, un binary heap proporciona un tiempo de O((V + E) log V) y un espacio de O(V) en la implementación con entradas perezosas. En una cuadrícula con cuatro vecinos, E es O(V). Una heurística consistente más fuerte suele reducir las celdas expandidas sin cambiar el límite del peor caso. Un heap con operación exacta de decrease-key puede reducir las entradas duplicadas, pero añade complejidad a la implementación.

6. Verificación y observabilidad

• Prueba casos donde el inicio es igual al objetivo, puntos extremos bloqueados, una cuadrícula vacía, una pared con una abertura, desvíos con diferentes pesos y un objetivo inalcanzable.
• Compara el costo obtenido con Dijkstra utilizando h=0 en cuadrículas aleatorias no negativas.
• Verifica con aserciones que cada paso devuelto sea adyacente y transitable, y recalcula el costo de la ruta de forma independiente.
• Monitorea las celdas expandidas, las extracciones obsoletas, el tamaño máximo del heap y las violaciones heurísticas; un pico en las extracciones obsoletas puede indicar una programación duplicada o un límite deficiente en la estructura de datos.

7. Errores comunes

• Marcar un nodo como permanentemente cerrado al descubrirlo por primera vez en lugar de hacerlo en una extracción válida.
• Usar la distancia euclidiana para movimientos de cuatro direcciones con costo unitario sin escalarla o sin verificar su admisibilidad.
• Sumar el costo de la celda actual en lugar del costo de ingresar a la celda vecina.
• Devolver una ruta cuando el objetivo fue extraído de un registro obsoleto del heap.
• Olvidar manejar start == goal o permitir puntos extremos bloqueados.

8. Preguntas de seguimiento

¿Cuándo es admisible la distancia de Manhattan?

Para movimientos en cuatro direcciones con costos no negativos y un costo mínimo de tránsito de m, cada paso horizontal o vertical requerido cuesta al menos m; por lo tanto, la distancia de Manhattan multiplicada por m no puede exceder el costo restante real.

¿Cómo cambian la heurística los movimientos diagonales?

Utiliza un límite inferior de tipo octil o Chebyshev que coincida con los costos de movimiento diagonal y recto. La fórmula debe reflejar la combinación legal de menor costo y mantenerse como un límite inferior.

¿Qué sucede si la cuadrícula cambia durante la búsqueda?

Realiza la búsqueda sobre una instantánea con versión y valida la ruta antes de usarla, o reinicia la búsqueda cuando cambie la versión de la cuadrícula. Mezclar costos de diferentes versiones puede invalidar tanto la optimalidad como la seguridad.