Considering three heuristics for 8-puzzle:
h1(n) = number of misplaced tiles
h2(n) = total Manhattan distance
h3(n) = max(h1, h2)
In an 8-puzzle, I was performing different puzzles and noticed that the h3 heuristic function (max) seems to provide the same solution as total manhattan distance heuristic. This is using the A star search algorithm.
I was wondering if the heuristic function of total manhattan distance always dominates over number of misplaced tiles?
Yes, because you would get the same value only if all misplaced tiles are just next to their correct place (i.e. manhattan distance = 1). In all other cases the manhattan distance for a misplaced tile is > 1.