I am going through the CS 188 available to the public at edx.org. Right now I have to develop a heuristic for an A* search to eat all the pellets as shown here:
The heuristic that I was sure would work, (as both admissible and consistent) went like this:
I also cache the previously computed distances so the astar search to find the nearest pellet isn't done if it has already been done before in another computation of a state. It is able to solve the problem very quickly, and the outcome is optimal.
When I use this algorithm in the autograder, it fails the admissibility test.
Don't worry, I am not asking for a solution to the problem, only why my current solution is not admissible? When I go through the example in the picture in my head the heuristic is never overestimating the cost.
So if anyone was able to understand this, and has any ideas your input is greatly appreciated!