Formulación correcta del algoritmo A *

Question

Estoy viendo definiciones del algoritmo de búsqueda de rutas A *, y parece que se define de manera algo diferente en diferentes lugares.

La diferencia está en la acción que se realiza al pasar por los sucesores de un nodo y al 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órelo
• Otro enfoque (se sugiere aquí y aquí , por ejemplo) dice: si el sucesor está en la lista cerrada, examine su costo. Si es más alto que la puntuación calculada actualmente, elimine el elemento de la lista cerrada para futuros exámenes.

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

Answer 1

El primer enfoque es óptimo solo si la ruta óptima a cualquier estado repetido es siempre la primera que se debe seguir. Esta propiedad se mantiene si la función heurística tiene la propiedad de consistencia (también llamada monoticity ). Una función heurística es consistente si, para cada nodo n y cada sucesor n ' de n , el costo estimado de alcanzar la meta de n no es mayor que el costo del 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 simplemente admisible, es decir, nunca sobreestima el costo para alcanzar la meta.

Toda función heurística consistente también es admisible. Aunque la consistencia es un requisito más estricto que la admisibilidad, uno tiene que esforzarse mucho para inventar funciones heurísticas que sean admisibles pero no consistentes.

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

Referencia: la subsección Una * búsqueda: minimizando 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: A Enfoque moderno .