Compare the three 8-puzzle heuristics of Figure 4.14 with the heuristic of adding the sum of distances out of place to 2 times the number of direct reversals. Compare them in terms of:

Figure 4.14

a. Accuracy in estimating distance to a goal. This requires that you first derive the shortest path solution and use it as a standard.

b. Informedness. Which heuristic most effectively prunes the state space?

c. Are any of these three 8-puzzle heuristics monotonic?

d. Admissibility. Which of these heuristics are bounded from above by the actual cost of a path to the goal? Either prove your conclusions for the general case or give a counterexample.

Transcribed Image Text:

28 3 1 6 4 7 5 2 8 3 1. 4 7 6 5 2 1 7 8 3 6 4 5 5 3 5 Tiles out of place 6 st 4 6 Sum of distances out of place 0 0 0 2 x the number of direct tile reversals 1 2 3 8 4 765 Goal