2.3.10.2 A$_{\epsilon }^*$

Cuando se tienen muchas posibilidades más o menos todas del mismo costo, lo que se puede hacer es agruparlas todas en un mismo rango y sólo expander la mejor de acuerdo a cierta heurística de simplicidad de solución, permitiendo errores del orden del rango establecido. Si el rango es igual a cero se regresa al algoritmo original.

Básicamente es como A$^*$, sólo que ahora se tienen dos listas: OPEN (como antes) y FOCAL $\subset$ OPEN, en donde se tienen todos los nodos que no se desvían de la mejor opción en más de $\epsilon$.

A$_{\epsilon }^*$ se comporta como A$^*$ solo que A$_{\epsilon }^*$ selecciona un nodo de FOCAL usando una heurística nueva que estima el esfuerzo computacional de los nodos en FOCAL para llegar a la solución.

Esto puede provocar que se regresen soluciones que no son óptimas con un error a lo más de $\epsilon$ (se llaman también $\epsilon$-admissible)

Algo muy parecido es establecer un rango en donde se permite tener sobre-estimaciones.