Exercise 6.1.
For the tiled puzzle problem shown below, we can define two different admissible heuristics: Hamming distance and Manhanttan distance. The Hamming distance is the total number of misplaced tiles. The Manhattan distance is the sum of the distance of each tile from its desired position. Answer the questions below assuming that in the goal state, the bottom right corner will be empty.
1
2
3
6
5
7
4
8
a.
What is the Manhattan distance for the configuration shown above?
b.
What is the Hamming distance for the configuration shown above?
c.
If your algorithm was using the Manhattan distance as a heuristic, what would be its next move?
d.
If your algorithm was using the Hamming distance as a heuristic, what would be its next move?