Diferencias de A* con Lazy A*

[ExRage2000]

Hola, me surgió una duda respecto a Lazy A*, ya que la instrucción dice:

a diferencia de A* permite que existan dos copias de un mismo estado en la cola de prioridades Open. Así, si un estado s recién ha sido generado, en vez de preguntarse si s ya está en la Open para comparar el valor g nuevo con el anterior, esta implementación simplemente agrega un nuevo nodo con el nuevo g a Open.

De esto entiendo que el A* original debe tener también incluir algún tipo de registro de los estados vistos para no tener nodos con estados iguales ¿correcto? Pregunto porque originalmente pensaba que el mismo BinaryHeap se encargaba de ignorar los nodos repetidos por si solo

[dfloreaa]

Hola, no. BinaryHeap es solo una estructura de datos y si permite tener duplicados en su interior (si los ingresas manualmente). Es por esto que debes actualizar los nodos directamente si encuentras un camino más corto hacia ellos (que en esencia, siempre será encontrado antes de expandirlo si la búsqueda es óptima).

Por tanto, si, A* debe tener un registro de estados visitados para no añadirlos nuevamente a Open (si no ha sido visitado, se debe revisar si tiene menor F y de ser así, actualizarlo).

Un saludo