Subject AI: Problem: Consider the maze show below, in which thesuccessors of a cell include any adjacent cell in the directionsNorth, South, East, and West of the current cell, except at theboundary of the maze or when a barrier (thick line) exists. Forexample, successors(M) = {D, N, G}. Assume each move has cost 1.Find a path from cell S to cell G. Break ties, if needed, using the alphabetical order of the labels inthe cells, so Breadth-First Search would visit cells in the order: SFHPKQCRATBG.For parts (a-b)below, what is the order of nodes expanded (plus the goal node if it is found) byeach of the following search strategies?

b) 10pts Greedy Best-first Search. Use as the heuristic function h(state) = Manhattan distance fromstate to G assuming there were no barriers. For example, h(K)=2 and h(S)=4.

Toe F S H K M N P Q R T G