Admissible Heuristic Manhattan Distance

Question

I recently started an introductory course to Artificial Intelligence and I have been given an assignment to implement an admissible heuristic function in Python that solves the 15-Puzzle with A* search.

I implemented the Manhattan Distance along with some other heuristics. The Python code worked just fine and the algorithm actually solves the problem but I have some doubts as to whether the Manhattan distance heuristic is an admissible for this particular problem.

According to theory a heuristic is admissible if it never overestimates the cost to reach the goal. That means that the heuristic is optimistic and the cost it returns is never greater than the actual one.

When the initial state is the following (0 signifies the 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 sum of the Manhattan Distances of every misplaced tile is equal to 10 which is double the value of the actual cost. So the real cost is much less than the estimated one. Does this mean that the heuristic is not admissible or is there something wrong with my logic?

I thought about counting just the empty block's Manhattan distance but that would lead to states with zero estimated costs when the empty block is in its correct place but other tiles are misplaced.

Answer 1

The Manhattan Distance heuristic is admissible since it considers each tile independently (while in fact tiles interfere with each other). So it's optimistic.

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