1. (30 points) UCS, Greedy and A* Search Algorithms The starting (S) and goal states (G) for a search problem are given on the graph given below. The real costs on edges) and heuristics (as h's) are also given on the graph. Draw the tree expansion from S to G (if possible) if: a) UCS is used, and explain the solution. Which cost function is used? b) Greedy search is used, and explain the solution. Which cost function is used? c) A* Search search is used, and explain the solution. Which cost function is used? . ha6 h 5 h22 ho b h7 h=6