patternMinor
Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'?
Viewed 0 times
whynumberthandistancemisplacedbettermanhattantilesheuristicfor
Problem
Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as:
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
- $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
Solution
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$.
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$.
Context
StackExchange Computer Science Q#37795, answer score: 5
Revisions (0)
No revisions yet.