Algoritmo $A^*$ para encontrar el camino más corto cuando los pesos en mi grafo son el inverso de la distancia

Question

Dado un grafo G=(V,E) donde los pesos en mis aristas son inversos de la distancia euclidiana entre nodos, quiero saber si puedo usar el algoritmo A* para encontrar el camino más corto. ¿Cómo debo modificar la heurística para que sea admisible?

Answer 1

La diferencia esencial es que las mejoras en una conexión conocida más corta entre el inicio y el destino probablemente conducirán a través de puntos intermedios que se encuentran fuera de una región que no es exactamente una elipse como se puede ver en la ilustración: