Consider the 8-puzzle problem. Show the resulting search tree from the A* algorithm given the initial and goal states below. Trace only for two steps/actions, i.e. each node in the tree is within two steps from the root. For each node 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 #