Heuristic for A* algorithm
Hi
I was reading into the A* algorithm. One of the key elements of the algorithm is that it uses a heuristic to approximate the distance to the target.
As I understand it, the heuristic function can vary but it is common to use something like a "Manhattan distance" or "Euclidean distance" which is something like moving through blocks on a chessboard.
What I don't understand is how you can calculate a heuristic function for a graph. I understand how you can do this for something like a grid where you can calculate the horizontal and vertical difference but you can't do this for a vertex (because a graph doesn't have this rigid structure).
I note that the Wiki on shortest path (https://en.wikipedia.org/wiki/Shortest_path_problem) doesn't really refer to A* for graphs.
What am I missing here?
Thanks
I was reading into the A* algorithm. One of the key elements of the algorithm is that it uses a heuristic to approximate the distance to the target.
As I understand it, the heuristic function can vary but it is common to use something like a "Manhattan distance" or "Euclidean distance" which is something like moving through blocks on a chessboard.
What I don't understand is how you can calculate a heuristic function for a graph. I understand how you can do this for something like a grid where you can calculate the horizontal and vertical difference but you can't do this for a vertex (because a graph doesn't have this rigid structure).
I note that the Wiki on shortest path (https://en.wikipedia.org/wiki/Shortest_path_problem) doesn't really refer to A* for graphs.
What am I missing here?
Thanks
If each node in the graph has an x and y coordinate then you could use those to calculate the euclidean distance to the goal.
But if you don't have any such information that allows you to come up with a meaningful heuristic function then A* is not going to help and you probably should use Dijkstra's algorithm instead.
But if you don't have any such information that allows you to come up with a meaningful heuristic function then A* is not going to help and you probably should use Dijkstra's algorithm instead.
Last edited on
Topic archived. No new replies allowed.