You are given the initial state (a) and the goal state (b) of an 8-puzzle as...

Transcribed Image Text:

You are given the initial state (a) and the goal state (b) of an 8-puzzle as shown below. 2 8 3 164 7 5 (a) 1 2 3 8 4 7 6 5 (b) a) Apply A* search using Manhattan distance heuristic function. Draw the search tree including possible expanded states during the algorithm procedure (The 8-puzzle search tree look like as below). Compute the triple (g. h. f) for each state. Mark the optimal strategy found. b) Prove that the Manhattan distance heuristic is admissible. 23 1 2 3 2. 1 2 2 3 1 026145 3 426 1 2 3 7 58 You are given the initial state (a) and the goal state (b) of an 8-puzzle as shown below. 2 8 3 164 7 5 (a) 1 2 3 8 4 7 6 5 (b) a) Apply A* search using Manhattan distance heuristic function. Draw the search tree including possible expanded states during the algorithm procedure (The 8-puzzle search tree look like as below). Compute the triple (g. h. f) for each state. Mark the optimal strategy found. b) Prove that the Manhattan distance heuristic is admissible. 23 1 2 3 2. 1 2 2 3 1 026145 3 426 1 2 3 7 58