28. Diseño de funciones heurísticas

Diseñar una función heurística significa crear una función h(n)h(n)h(n) que estime qué tan lejos está un estado nnn del estado objetivo, sin calcular el camino completo.

Propiedades importantes de una buena heurística

1. Admisible

Nunca sobreestima el costo real al objetivo.

$h(n)≤h∗(n)h(n) \leq h^*(n)h(n)≤h∗(n)$

✔ Garantiza optimalidad en A*

2. Consistente (monótona)

Cumple: $h(n)≤c(n,n′)+h(n′)h(n) \leq c(n,n') + h(n)≤c(n,n′)+h(n′)$

Evita re-expansiones de nodos
Más eficiente

3. No admisible

Sobreestima el costo → más rápida, pero puede fallar

Características de las Heurísticas

Las heurísticas determinan la calidad de la solución y el rendimiento del algoritmo en términos de recursos computacionales.
Se pueden proponer heurísticas al relajar las restricciones del problema original, como considerar distancias en línea recta en lugar de restricciones de movimiento.

Ejemplos de Heurísticas

En la búsqueda de rutas, la distancia en línea recta es una buena heurística, ya que es fácilmente computable y no sobrestima el costo real.
En el rompecabezas del ocho, se puede usar la distancia de Manhattan, que cuenta los movimientos necesarios para alcanzar la meta, como una heurística admisible.

Combinación de Heurísticas

Se pueden combinar varias heurísticas utilizando el máximo de los valores resultantes de cada una, pero es importante elegir la más informativa y computacionalmente eficiente.
La heurística de distancia de Manhattan es más cercana al costo real en comparación con contar fichas fuera de lugar.

Uso de Bases de Datos de Patrones

Se pueden almacenar patrones descubiertos en una base de datos para estimar costos mínimos de un conjunto de estados, lo que mejora la eficiencia de la búsqueda.
Técnicas de aprendizaje automático pueden ser incorporadas para proponer heurísticas automáticamente.
relatedInteligencia Artificial