algorithm - laberinto - que es el algoritmo estrella

Correcta formulación del algoritmo A*

Question

Estoy mirando las definiciones del algoritmo de búsqueda de ruta A *, y parece estar definido de manera algo diferente en diferentes lugares.

La diferencia radica en la acción que se realiza al pasar por los sucesores de un nodo y en encontrar que un sucesor está en la lista cerrada.

• Un enfoque (sugerido por Wikipedia y este artículo ) dice: si el sucesor está en la lista cerrada, simplemente ignóralo
• Otro enfoque (sugerido aquí y aquí , por ejemplo) dice: si el sucesor está en la lista cerrada, examine su costo. Si es más alto que el puntaje calculado actualmente, elimine el elemento de la lista cerrada para un examen futuro.

Estoy confundido, ¿qué método es el correcto? Intuitivamente, el primero tiene más sentido para mí, pero me pregunto acerca de la diferencia en la definición. ¿Está una de las definiciones incorrecta, o son de alguna manera isomórficas?

Answer 1

El primer enfoque es óptimo solo si la ruta óptima para cualquier estado repetido es siempre la primera a seguir. Esta propiedad se cumple si la función heurística tiene la propiedad de consistencia (también llamada monoticidad ). Una función heurística es consistente si, para cada nodo n cada sucesor n'' de n , el costo estimado de alcanzar la meta desde n no es mayor que el costo de paso de llegar a n'' desde n más el costo estimado de alcanzar la meta de n .

El segundo enfoque es óptimo si la función heurística es meramente admisible, es decir, nunca sobreestima el costo para alcanzar la meta.

Toda función heurística coherente también es admisible. Aunque la consistencia es un requisito más estricto que la admisibilidad, uno tiene que trabajar bastante duro para elaborar funciones heurísticas que son admisibles pero no consistentes.

Por lo tanto, aunque el segundo enfoque es más general, ya que funciona con un subconjunto estrictamente más grande de funciones heurísticas, el primer enfoque suele ser suficiente en la práctica.

Referencia: la subsección A * búsqueda: Minimizar el costo total estimado de la solución en la sección 4.1 Estrategias de búsqueda informadas (heurísticas) del libro Inteligencia artificial: un enfoque moderno .