The start and goal state are S and G,respectively. For each of the following graph search strategies, work out the order in which statesare expanded, as well as the path returned by graph search. In all cases, assume ties resolve in sucha way that states with earlier alphabetical order are expanded first.

e) 8pts A* search

h=6 S 1 2 6 h=5 c 3 h=6 b h = 8 a 3 6 6 20 h = 20e d)h = 4 Gh=0 2 4 5 1 f h = 1