Recall that we came up with two different heuristics for the 8-puzzle by relaxing problem constraints....

Transcribed Image Text:

Recall that we came up with two different heuristics for the 8-puzzle by relaxing problem constraints. In an 8-puzzle, the set of valid actions are described by the following statement: A tile can move from square A to square B if A is adjacent to B and B is blank. We can generate three relaxed problems (leading to three admissible heuristic functions) by removing one or both of the above conditions: . A tile can move from square A to square B if A is adjacent to B • A tile can move from square A to square B if B is blank . A tile can move from square A to square B Recall that the first relaxation gives us the sum-of-Manhattan-distances heuristic, and the third relaxation gives us the number-of-misplaced-tiles heuristic. The second relaxation leads to a relaxed problem, whose (optimal) solution is known as Gaschnig's heuristic (Gaschnig, 1979). (a) Explain why Gaschnig's heuristic is at least as accurate as the number-of-misplaced-tiles heuristic. Hint: Observe that since both are admissible heuristics, it is equivalent to showing that: 0 ≤ Number of misplaced tiles Gaschnig's heuristic <h* In the above, h* is the true cost-to-go function. In particular, explain why the number of misplaced tiles is always an underestimate of Gaschnig's heuristic. (b) For Gaschnig's heuristic and the sum-of-Manhattan-distances heuristic, show that neither is strictly better than the other. To show this, find an 8-puzzle instance where the sum-of-Manhattan-distances heuristic is more accurate than Gaschnig's heuristic, and find an 8-puzzle instance where the opposite is true. Hint: The latter case may be harder to find. Consider an instance that is very close to the goal state. (c) Describe a method to calculate Gaschnig's heuristic efficiently. You do not have to prove its correctness, but you should convince yourself that your method is correct. Recall that we came up with two different heuristics for the 8-puzzle by relaxing problem constraints. In an 8-puzzle, the set of valid actions are described by the following statement: A tile can move from square A to square B if A is adjacent to B and B is blank. We can generate three relaxed problems (leading to three admissible heuristic functions) by removing one or both of the above conditions: . A tile can move from square A to square B if A is adjacent to B • A tile can move from square A to square B if B is blank . A tile can move from square A to square B Recall that the first relaxation gives us the sum-of-Manhattan-distances heuristic, and the third relaxation gives us the number-of-misplaced-tiles heuristic. The second relaxation leads to a relaxed problem, whose (optimal) solution is known as Gaschnig's heuristic (Gaschnig, 1979). (a) Explain why Gaschnig's heuristic is at least as accurate as the number-of-misplaced-tiles heuristic. Hint: Observe that since both are admissible heuristics, it is equivalent to showing that: 0 ≤ Number of misplaced tiles Gaschnig's heuristic <h* In the above, h* is the true cost-to-go function. In particular, explain why the number of misplaced tiles is always an underestimate of Gaschnig's heuristic. (b) For Gaschnig's heuristic and the sum-of-Manhattan-distances heuristic, show that neither is strictly better than the other. To show this, find an 8-puzzle instance where the sum-of-Manhattan-distances heuristic is more accurate than Gaschnig's heuristic, and find an 8-puzzle instance where the opposite is true. Hint: The latter case may be harder to find. Consider an instance that is very close to the goal state. (c) Describe a method to calculate Gaschnig's heuristic efficiently. You do not have to prove its correctness, but you should convince yourself that your method is correct.

Answer rating: 100% (QA)

a Gaschnigs Heuristic vs NumberofMisplacedTiles Heuristic Gaschnigs heuristic is at least as accurate as the numberofmisplacedtiles heuristic because ... View the full answer