Consider the 8-puzzle problem. Trace out the A* algorithm given the initial and goal states below. You are supposed to show the generated search tree until the search generates the goal state. For...

Consider the 8-puzzle problem. Trace out the A* algorithm given the initial and goal states below. You are supposed to show the generated search tree until the search generates the goal state. For each state show the value of the evaluation function f(n) = g(n) + h(n). Recall that g(n) gives the path cost from the initial state to node n. Moreover, for this problem the step cost is 1 for any action (moving the empty tile). As a heuristic let h(n) be the number of misplaced tiles. Hence f(initial-state) = 0 + 3 = 3. The # symbol denotes the empty tile.

Initial State Goal State 1 2 3 1 2 3 # 4 6 4 5 6 7 5 8 7 8 #