Let's say that I have a grid with squares designated as “target” squares. I use A * to navigate this grid, trying to visit every square of the target at least once, using off-diagonal movement. Once the target square has been visited, it is no longer considered the target square. Think Pac Man, moving and trying to eat all the dots.
I am looking for consistent heuristics to give A * navigation help. I decided to try "returning the Manhattan distance to the nearest target", heuristic for any given location. I was told that this is not a consistent heuristic, but I do not understand why.
Moving one square toward the nearest square of the target has a cost of one, and the Manhattan distance should also be reduced by one. Landing on the square of the gate will either increase the value of the heuristic (because now it will search for the nearest nearest target), or complete the search (if the target was the last target not expected)
<p> H (N) c (N, P) + h (P) seems to be always true. What makes this algorithm inconsistent, or is my instructor wrong?
source
share