Show the first four steps of each of the following algorithms. I.e., start drawing the corresponding search tree showing the first four nodes expanded after the root node. Do not draw the whole search tree; just the first four steps.

(a) Breadth-first search.

(b) Depth-first search.

(c) A* search using the number of tiles misplaced heuristic.

(d) A* search using the total Manhattan distance heuristic.

Fully annotate each search tree, and along with your drawing write a couple sentences explaining the way the algorithm functions. Limiting your search to only four steps makes it tractable for you to work on the problem without requiring writing a program, but how does it limit our ability to see the details of these search strategies working in practice?

Consider the following 8-puzzle, with the start state illustrated on the left, and the final goal state illustrated on the right