How does Manhattan distance valid heuristics?

Question

Is it not true that when calculating moves for 1 tile, it can lead to other tiles falling into the state of the target? And therefore, counting for each tile can give us an account of more than the minimum steps necessary to achieve the goal state?

This question is in the context of the Manhattan distance for 15 puzzles.

Here is the question in different words:

Is it possible to use the Manhattan distance as a valid heuristic for N-Puzzle. To implement the A * search, we need a valid heuristic. Is Manhattan a heuristic candidate? If so, how do you contrast the above argument (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 target. While this heuristic function never overestimates the distance to the target, the algorithm will find the shortest path, probably faster than the width search. A heuristic satisfying this condition is valid.

Answer 1

Acceptable heuristics should not overestimate the number of moves to solve this problem. Since you can only move blocks 1 at a time and in only one of four directions, the optimal scenario for each block is that it has a clear, unhindered path to its target state. This is MD 1.

The remaining states for a pair of blocks are suboptimal, which means that to get the block in the right place will require more movements than MD. Thus, the heuristic is never overestimated and valid.

I will delete when someone posts the correct, official version of this.

Answer 2

Formal proof: By definition, h, h (s *) = 0 if s * is the state of the target. Assume for proof that the contradiction is that C * h (s0) for some initial state s0. Note that since each action can only move one tile performing the action, it can in most cases reduce h by one. Since the goal can be achieved in the actions of C *, we have h (s *) ≥ h (s0) - C *> 0, which leads to a contradiction, since h (s *) must be equal to zero. Therefore, we must have h (s0) ≤ C * forall s0 and h is admissible. ( Source : University of California, Irwin)