CODEWITHSUNDEEP
algorithma-starheuristicssearch-tree
user11576265
user11576265

Reputation:

A star Search: Does Manhattan Distance dominate over Number of Missing Tiles for 8-Puzzle?

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?

Upvotes: 0

Views: 1548

Answers (1)

Henry
Henry

Reputation: 43738

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.

Upvotes: 2

Related Questions