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?

a) 10pts Depth-First Search. Assume cycles are detected and eliminated by never expanding a nodecontaining a state that is repeated on the path back to the root.

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