Consider the search space below, where S is the start node and G1 and G2 are the goal nodes. Arcs are labelled with the value of a cost function; the number gives the real cost of traversing the arc. ;odes are labelled with the value of a heuristic function; the number gives the estimate of the distance to the goal. Assume ties resolve in such a way that states with earlier alphabetical order are expanded first. For each of the following search strategies: a) Draw the search tree, b) Write the path returned, and c) Indicate which goal state is reached first (if any). 1. Depth first search ( 2 marks) 2. Breadth-first search ( 2 marks) 3. A-star search ( 3 marks) 4. Local beam search (w=2) ( 1 mark)