Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics.
Currently, I explored Manhattan and Euclidean distances. Which other heuristics are available? How do we compare them? How do we know whether a heuristic is better than another?
A good heuristic should approximate the actual distance to the goal as closely as possible, without going over it.
If heuristic1 returns a greater or equal value than heuristic2 for every input (while still being valid), then heuristic1 is better. In your case, Manhattan distance is better than Euclidean distance because the value it returns is never smaller than Euclidean distance and is sometimes larger. (Unless you can move diagonally in the maze, in which case Manhattan distance is an invalid heuristic and Euclidean distance might be as well.)
If heuristic1 returns a larger value for some inputs, and heuristic2 returns a larger value for others (and both are valid), then heuristic3(x) = max(heuristic1(x), heuristic2(x)) is better than either of them.
If the heuristics are slow, it's more complicated. Since heuristic3 will be even slower than heuristic1 or heuristic2 alone, it could end up being worse overall if it doesn't improve the estimate by very much. There's no unambiguous way to choose the best heuristic in this case. You basically have to benchmark and decide how much cleverness you can afford.
