Búsqueda Heurística y A*

La búsqueda heurística utiliza una estimación específica del problema del costo restante para alcanzar un objetivo, con el fin de guiar qué estados explorar primero; A* es su algoritmo canónico, que expande estados en orden de la suma del costo hasta el momento y el costo estimado restante.

Definition

La búsqueda heurística es una búsqueda informada que ordena la frontera utilizando una función de evaluación que combina el costo conocido desde el inicio con una estimación heurística del costo restante; A* utiliza f(n) = g(n) + h(n) y es óptimo cuando h es admisible.

Scope

Este tema cubre las estrategias de búsqueda informada (heurística), centrándose en la búsqueda primero el mejor y el algoritmo A*, incluyendo el diseño y las propiedades de las funciones heurísticas (admisibilidad, consistencia/monotonicidad), las garantías de optimalidad y eficiencia que confieren estas propiedades, y las variantes con memoria limitada como A* de profundización iterativa (IDA*). Aborda cómo se construyen las heurísticas (problemas relajados, bases de datos de patrones) y cómo equilibran la precisión con el cálculo. El aprendizaje de heurísticas a partir de datos pertenece al subcampo del aprendizaje automático.

Core questions

• ¿Qué hace que una heurística sea admisible y por qué la admisibilidad garantiza la optimalidad de A*?
• ¿Cómo la consistencia (monotonicidad) refuerza las garantías y evita la reexpansión de nodos?
• ¿Cómo se diseñan buenas heurísticas, por ejemplo, a partir de versiones relajadas del problema?
• ¿Cómo las variantes con memoria limitada, como IDA*, preservan la optimalidad con espacio limitado?

Key concepts

• función de evaluación f = g + h
• heurística admisible
• heurística consistente (monótona)
• búsqueda primero el mejor codiciosa
• búsqueda A*
• A* de profundización iterativa (IDA*)
• dominancia heurística
• problema relajado y bases de datos de patrones

Key theories

Optimalidad de A* bajo heurísticas admisibles

Cuando la heurística h nunca sobreestima el verdadero costo restante, A* expande los nodos aumentando f = g + h y se garantiza que devuelve una ruta de menor costo; entre los algoritmos que utilizan la misma información heurística, A* es óptimamente eficiente.

Diseño heurístico mediante relajación

Las heurísticas admisibles se pueden derivar sistemáticamente resolviendo una versión relajada del problema (una con menos restricciones en las acciones), ya que el costo exacto de un problema más fácil es un límite inferior del original; las heurísticas dominantes (más informadas) expanden menos nodos.

Búsqueda heurística con memoria limitada

A* de profundización iterativa realiza búsquedas en profundidad sucesivas limitadas por un umbral de costo f creciente, logrando una optimalidad similar a A* con una memoria lineal en la profundidad de la solución.

Clinical relevance

La búsqueda heurística impulsa la búsqueda de rutas en mapas y juegos, la planificación de movimientos en robótica y los motores de búsqueda dentro de planificadores automatizados y solucionadores de rompecabezas; el arte práctico del diseño heurístico determina directamente si los problemas grandes son resolubles en un tiempo aceptable.

History

El algoritmo A* fue introducido por Hart, Nilsson y Raphael (1968), dando a la búsqueda heurística una base formal de optimalidad. La monografía de Pearl de 1984, Heuristics, proporcionó el tratamiento teórico definitivo, y el IDA* de Korf de 1985 abordó el costo de memoria de A*. Estos resultados siguen siendo material central en la educación de IA.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

¿Qué es una heurística admisible?

Una heurística es admisible si nunca sobreestima el costo real de alcanzar el objetivo desde cualquier estado. La admisibilidad es la condición bajo la cual se garantiza que A* encontrará una solución óptima (de menor costo).

¿Cuál es la diferencia entre la búsqueda primero el mejor codiciosa y A*?

La búsqueda primero el mejor codiciosa expande el estado que parece más cercano al objetivo según la heurística solamente (h), lo cual es rápido pero puede estar lejos de ser óptimo. A* añade el costo real incurrido hasta el momento (g), expandiendo por f = g + h, lo que preserva la optimalidad cuando la heurística es admisible.