2.3.10.5 Mejoras Dinámicas

Las evaluaciones en las heurísticas son básicamente estáticas e involucran cierto error (e.g., subestimaciones).

Una forma de mejorar las funciones de evaluación es actualizarlas dinámicamente conforme se obtiene más informacón.

Algunas variantes incluyen:

• Add method: (i) Se calcula alrededor de la meta rutas a varios puntos ($B_i$s), (ii) Se estima el error entre el valor real de todos estos puntos ($g*(B_i)$) y el estimador inicial a estos puntos ( $Diff(B_i)=g*(B_i)-h(B_i)$, (iii) se toma el error mínimo ( $minDiff = min_i(Diff(B_i)$ y se usa para mejorar el estimador de los nodos ($A$s) haciendo búsqueda hacia adelante ( $newh(A)=h(A)+minDiff$).

  Figura 2.12: Esquema ilustrando el método Add

  

• Max method: (i) Se calcula alrededor de la meta rutas a varios puntos ($B_i$s), (ii) Se estima la distancia entre el estado inicial y los puntos cercanos a la meta y se estima el mínimo de la distancia total ( $fmin2 = min_i (g*(B_i) + h(B_i)$), (iii) se usa para mejorar el estimador de los nodos ($A$s) haciendo búsqueda hacia adelante, tomando en cuenta el estimador inicial hacia $A, h_1(A)$ ( $h'(A)=fmin2 - h_1(A)$), (iv) como no siempre es mejor estimador que el que se tenía, se hace la combinación max de ambos ( $newh(A)=max(h(A),fmin2 - h_1(A)$).

  Figura 2.13: Esquema ilustrando el método Max

  

• Back-up method: (i) Se toman los sucesores de un nodo $A$ ($B$s), (ii) Se estima el costo de $A$ a cada uno de los $B$s ($k_i(A,B_i)$) y la estimación de cada $B$ a la meta ($h(B_i)$). (iii) Se usa como estimador de $A$ a la meta, el mínimo de estos ( $newh(A) = min_i(k_i(A,B_i)+h(B_i))$). Si el evaluador no es consistente, entonces se toma: $newh(A)=max(h(A),min_i(k_i(A,B_i)+h(B_i)))$.

  Figura 2.14: Esquema ilustrando el método Back-up

  

• Front-to-front method: (i) Se calcula alrededor de la meta rutas a varios puntos ($B_i$s), (ii) Se toma como nuevo estimador de un nodo $A$, el mínimo entre las estimaciones de $A$ a cada $B_i$ ($h(A,B_i)$) junto con el costo de cada $B_i$ a la meta ($k_i(B_i,Meta)$), osea: $newh(A)=min_i(k_i(B_i,Meta)+h(A,B_i))$). De nuevo, si el evaluador no es consistente, entonces se toma: $newh(A)=max(h(A),min_i(k_i(B_i,Meta)+h(A,B_i)))$.

  Figura 2.15: Esquema ilustrando el método Front-to-front

  

Existen muchas otras variantes que se ido proponiendo en la literatura.