How is Manhattan distance an admissible heuristic?
Isn't it true that while counting the moves for 1 tile can lead to other tiles getting to their goal state? And hence counting for each tile can give us a count more than the minimum moves required to reach the goal state? What is Manhattan distance heuristic?
This question is in the context of Manhattan distance for 15-Puzzle.
Here is the Question in different words:
Can we use Manhattan distance as an admissible heuristic for N-Puzzle? To implement A* search we need an admissible heuristic. Is Manhattan heuristic a candidate? If yes, how do you counter the above argument (the first 3 sentences in the question)?
Definitions: A* is a kind of search algorithm. It uses a heuristic function to determine the estimated distance to the goal. As long as this heuristic function never overestimates the distance to the goal, the algorithm will find the shortest path, probably faster than a breadth-first search would. A heuristic that satisfies that condition is admissible.
In Artificial Intelligence, the algorithms which are related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal means that the cost which is calculated to reach to its goal is not higher than the lowest possible cost from the current point in the path.
Admissible heuristics must not overestimate the number of moves to solve this problem. Here you can only move the block 1 at a time and in only one of the 4 directions, the optimal scenario for each block is that it has a clear, unobstructed path to its goal state. This is an M.D.(Manhattan Distance) of 1.
The rest of the states for a pair of blocks is sub-optimal, meaning it will take more moves than the M.D. to get the block in the right place. Thus, the heuristic never overestimates and is admissible.
Manhattan distance#
In the absence of obstacles, and on terrain that has the minimum movement cost D, moving one step closer to the goal should increase g by D and decrease h by D. When you add the two, f (which is set to g + h ) will stay the same; that's a sign that the heuristic and cost function scales match.