Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the heuristic to make it admissible?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Given just two vertices you can't lower-bound the shortest path length between them more tightly than zero, because there could be a two-step route through a point nearly at infinity. It reduces to Dijkstra's algorithm. $\endgroup$– Peter TaylorCommented Aug 3, 2023 at 17:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The essential difference is that improvements to a shortest known connection between start and destination will most likely lead over intermediate points that lie outside a region that is not quite an ellipse as can be seen from the illustration:
answered Aug 3, 2023 at 17:25
-
$\begingroup$ Thank you for the response. Does this prove that there is no heuristic for this? $\endgroup$ Commented Aug 4, 2023 at 7:52
-
$\begingroup$ @user2512443 that observation doesn't disprove the existence of a heuristic, but keep in mind that for metric distances as edge weights the weight of the edge connecting start and end of a path is always a lower bound for the pathlength. For reciprocal metrics as edgeweights that is no longer the case, Paths that run outside the depicted region could consist of many segments with short euclidean length and thus with arbirary high sum of reciprocal lengths sum, demonstrating that no reliable means for bouding path lengths from above exist. $\endgroup$ Commented Aug 4, 2023 at 14:04