Manhattan Allowable Heuristic Distance

Question

I recently started an introductory Artificial Intelligence course, and I was tasked with implementing a valid heuristic function in Python that solves 15-Puzzle with A * search.

I implemented Manhattan distance along with some other heuristics. Python code worked very well, and the algorithm actually solves the problem, but I have some doubts as to whether the Manhattan distance heuristic is acceptable for this particular problem.

According to the theory, heuristic is acceptable if it never overestimates the cost of achieving a goal. This means that the heuristic is optimistic, and the value that it returns never exceeds the actual value.

When the initial state is as follows (0 means empty slot):

1 2 3 4 0 6 7 8 5 9 10 12 13 14 11 15 

my program solves the problem with 5 moves, but the Manhattan sum of the Distances of each inappropriate tile is 10, which is double the cost of the actual cost. Thus, the real value is much less than expected. Does this mean that heuristic is unacceptable or something is wrong with my logic?

I was thinking of calculating only the empty distance in Manhattan, but this would lead to states with zero estimated costs when the empty block is in the right place, but other tiles are inappropriate.

Answer 1

The Manhattan distance heuristic is valid, as it examines each plate independently (while in fact the tiles interfere with each other). Therefore, he is optimistic.

In your example, the sum of the distance from the target position of all tiles is 5 (for each tile 5, 9, 10, 11, 15, one move is required).