Q:

Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'?

Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as:

$h_1(n)$ = number of misplaced tiles
$h_2(n)$ = total Manhatten distance

Could anyone tell why $h_2$ is a better heuristic than $h_1$? I would like to know why the number of nodes generated for $h_1$ is greater than that for $h2$. Also why going deeper into the state space the number of nodes increase drastically for both heuristics.
Source: Informed Search

A:

There probably will be no formal proof; probably the only way to tell which is better is through experiments.
But some intuition seems possible.  $h_1$ only takes into account whether a tile is misplaced or not, but it doesn't take into account how far away that tile is from being correct: a tile that is 1 square away from its ultimate destination is treated the same as a tile that is far away from where it belongs.
In contrast, $h_2$ does take this information into account.  Instead of treating each tile as either "correct" or "incorrect" (a binary decision), $h_2$ introduces shades of grey that take into account how far the tile is from where it belongs.  It seems plausible that this might possibly yield some improvement.
Of course, the only way to find out which one actually works better is to try the experiment.  But this might give some intuition about why one might reasonably hope that $h2$ could be potentially be better than $h_1$.

A:

The current answers are good, but I think I have a simpler way to understand it. 
The Manhattan Distance heuristic approximates the actual distance better than the misplaced tiles heuristic. So, you can think of the actual number of moves it would take as the perfect heuristic (at that point it stops being a heuristic). Like Daniil Agashiyev said, the lowest the Manhattan distance huristic can possibly be is equal to the misplaced tile heuristic. Since both are admissible, that means they both underestimate the true distance. So, the estimations are closer to the actual for Manhattan distance heuristic since it is grater then $H_1$ and less than the actual (let’s call it $H^*$). This is the better heuristic definitively, and it can be formally proven. 
$$H_1 \leq H_2 \leq H^*.$$
The reason it will generate less nodes in the search tree is because it will be able to approximate which nodes to explore next better than the misplaced tile heuristic. This is related to $H_1\leq H_2\leq H^*$. Of all the nodes unexplored, the one to select next is decided by the cost estimated by the heuristic. Therefore, the $H_2$ heuristic will provide you a better selection criterion on what to move next. At $H_2$’s worst case, it’ll be equal to $H_1$. For example, beginning at the start state, all the next moves possible will have equal cost with $H_1$. This is because no tile can be placed in the right location in one move. For $H_2$ there will be an order to the next moves, so you can still look one by one, but in an order that can only help. 

Also why going deeper into the state space the number of nodes increase drastically for both heuristics.

I think you mean going deeper down the search tree? This is because A* is based off Breadth first search, the number of nodes expand exponentially as you explore more nodes.

