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 hs) are also given on the graph. Draw the tree expansion from S to G (if possible) if UCS is used, and explain the solution. Which cost function is used?

solve question 1-a.

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 Sto 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? h=1 d G S h=6 h=5 h=2 h=0 b h=7 h=6