Question $5(60$ points$)$

Consider the following maze. The successors of each cell are the adjacent cells in the directions North $($up$),$

East $($right$),$ South $($down$),$ and West $($left$).$ No diagonal moves are permitted. You may not move from one

cell to an adjacent cell when a wall $($thick line$)$ exists. For example, successors $(T)=\{O,Y,G\}$ and

successors $(M)=\{S,$I,$N\}.$ You cannot move from cell M to cell $R,$ or anywhere else a wall exists. Each

move has cost $1.$

Find a path from cell $S$ to cell $G.$ You are to write the order in which the nodes are EXPANDED, and the

SOLUTION that is found. If no solution is found, say so$.$ This is exactly the same as we did for the examples

in class and in the notes. If the search method needs to break ties, expand the nodes in alphabetical order

$($choosing first the node corresponding to the letter closest to the front of the alphabet.$)$ For example, if nodes

$D$ and $U$ have the same value, node $D$ would be expanded before node $U.$

$($a$)$ Depth$-$first search. $($Assume that cycles are eliminated, so that no cells are expanded twice.$)$

$($b$)$ Hill$-$climbing search. Use the heuristic function h$($state$)=$ Manhattan Distance to goal. This is the same

heuristic used in class for the $8-$puzzle. Minimize this function. For example, $h(D)=3$ and $h(A)=6($so

the thick wall does not count in computing this heuristic$).$

$($c$)$ Algorithm A$*.$ Use the heuristic function h$($state$)=$ Manhattan Distance to goal. This is the same heuristic

used in class for the $8-$puzzle. Minimize this function. For example, $h(D)=3$ and $h(A)=6($so the thick

wall does not count in computing this heuristic$).$