2.3.10 Extensiones

En la práctica se ha visto que a veces A$^*$ se pasa mucho tiempo explorando caminos cuyos costos no varían demasiado.

En estos casos, la propiedad de admisibilidad empieza a ser más un problema que una virtud, ya que evita encontrar rápidamente soluciones que a pesar de no ser óptimas se pueden acercar bastante al óptimo.

Posibilidades:

La fórmula: $f = g + h$ viene de dos principios: (i) lo más corto es lo más rápido ($g$) y (ii) para asegurarnos que es la mejor opción hay que agregar subestimaciones ($h$).

El efecto de $g$ es para añadir la componente de breadth-first a la búsqueda, mientras $h$ es ideal cuando se tienen muchas soluciones y se puede confiar en la estimación.

Se han propuestos funciones pesadas para compensar cada parte:

$$f(n) = (1 - w)g(n) + w h(n)$$

$w = o \Rightarrow$ búsqueda de costo uniforme
$w = 1/2 \Rightarrow$ A$^*$
$w = 1 \Rightarrow$ BF

Si $0 \leq w \leq 1/2$ es fácil garantizar la admisibilidad, pero se puede perder para $w > 1/2$, dependiendo de que tal alejada está $h$ de $h^*$.

Una estrategia $\epsilon$-admisible se obtiene con un peso dinámico: En lugar de mantener a $w$ constante durante la búsqueda, mejor usar un peso dinámico que se ajusta con la profundidad. Una posibilidad es:

$$f(n) = g(n) + h(n) + \epsilon [ 1 - \frac{d(n)}{N} ] h(n)$$

donde $d(n)$ es la profundidad del nodo $n$ y $N$ la profundidad anticipada del nodo meta. A profunidades bajas, $h$ tiene un soporte de $1 + \epsilon$ lo que favorece escursiones tipo depth-first, mientras que a grandes profundidades asume un peso igual.

También se han desarrollado medidas para estimar el riesgo asociado con dejar algun nodo sin explorar.

Se pueden usar otras posibles medidas no aditivas para $h$ y $g$: e.g., multiplicativa.