1. (30 marks) Consider the graph in the following The heuristic estimate of the distance to G are: h(A,2),h(B,3),h(C,4),h(D,3),h(E,2),h(F,1),h(G,0)h(H,4),h(I,5),h(J,6),h(K,5),h(L,6),h(S,4). (4 marks) Draw the corresponding search tree for the graph. The tree is rooted at S, and the goal node is G. Find a path from S to G using each of the following search strategies, from (a) to (e). For each one of the strategies, report whether the returned solution path is an optimal one. Give your explanation and remarks on "why-optimal" or "why-non-optimal". For A * search in particular, your discussion will have to check with the admissibility properties of the heuristics. (a) (4 marks) depth-first search (b) (4 marks) breadth-first search (c) (4 marks) least-cost first search (d) (4 marks) best-first search (e) (10 marks) A* search