Figure $2$ DFS

$\begin{array}{cc}\text{F}\text{r}\text{i}\text{n}\text{g}\text{e}\text{:}& \text{N}\text{o}\text{d}\text{e}\text{v}\text{i}\text{s}\text{i}\text{t}\text{e}\frac{d}{e}\text{x}\text{p}\text{a}\text{n}\text{d}\text{e}\text{d}\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\end{array}$ BFS

$\begin{array}{cc}\text{F}\text{r}\text{i}\text{n}\text{g}\text{e}\text{:}& \text{N}\text{o}\text{d}\text{e}\text{v}\text{i}\text{s}\text{i}\text{t}\text{e}\frac{d}{e}\text{x}\text{p}\text{a}\text{n}\text{d}\text{e}\text{d}\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\end{array}$ Best First Search

$\begin{array}{cc}\text{F}\text{r}\text{i}\text{n}\text{g}\text{e}\text{:}f(N)& \text{N}\text{o}\text{d}\text{e}\text{v}\text{i}\text{s}\text{i}\text{t}\text{e}\frac{d}{e}\text{x}\text{p}\text{a}\text{n}\text{d}\text{e}\text{d}\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\end{array}=h(N)$A$*$ Search

Question $2[6$ pts$]$ Figure $2$ shows a robot navigation field, where the green square $($b$7)$ is the robot, and red square $($d$2)$ is the goal. The shad squares $($such as c$2,$ d$3$ etc.$)$ are obstacles. The robot is not allowed to move in diagonal line. Nodes are coded using an alphabet letter followed by a digit $($such as b$1,$ b$2$ etc.$).$ When two sibling nodes are inserted into fringe $($queue$),$ use deque order to favor node with a lower alphabet and a lower digit. For example, if d$1$ and e$2$ are sibling nodes, d$1$ will be dequeued first $($because $$d$$ has a lower alphabetic order than $$e$).$ If e$1$ and e$2$ are sibling nodes, e$1$ will be dequeued first $($because $1$ has a lower digit than $2).$ Node expanded$/$visited does not need to be revisited.

$$ Use Depth First Search to find path from b$7$ to d$2.$

o Report nodes in the fringe in the orders they are included in the fringe. $[0\mathrm{.}5$ pt$]$

o Report the order of the nodes being expanded. $[0\mathrm{.}5$ pt$]$

o Report the final path from b$7$ to d$2.[0\mathrm{.}5$ pt$]$

DFS

Fringe: Node visited$/$expanded

$$ Use Breadth First Search to find path from b$7$ to d$2.$

o Report nodes in the fringe in the orders they are included in the fringe. $[0\mathrm{.}5$ pt$]$

o Report the order of the nodes being expanded. $[0\mathrm{.}5$ pt$]$

o Report the final path from b$7$ to d$2.[0\mathrm{.}5$ pt$]$

BFS

Fringe: Node visited$/$expanded

$$ Use Best First Search to find path from b$7$ to d$2.($Using Manhattan distance as the heuristic function$)$

o Report nodes in the fringe $($including their f$($N$)$ values$)$ in the orders they are included in the fringe. $[0\mathrm{.}5$ pt$]$

o Report the order of the nodes being expanded. $[0\mathrm{.}5$ pt$]$

o Report the final path from b$7$ to d$2.[0\mathrm{.}5$ pt$]$

Best First Search

Fringe: f$($N$)=$h$($N$)$ Node visited$/$expanded

$$ Use A$*$ to find path from b$7$ to d$2.($Using Manhattan distance as the heuristic function$).$

o Report nodes in the fringe $($including their f$($N$)$ values$)$ in the orders they are included in the fringe. $[0\mathrm{.}5$ pt$]$

o Report the order of the nodes being expanded. $[0\mathrm{.}5$ pt$]$

o Report the final path from b$7$ to d$2.[0\mathrm{.}5$ pt$]$

A$*$ Search$\backslash$table$[[$e$1,$e$2,$e$3,$e$4,$e$5,$e$6,$e$7,$e$8,$e$9],[$d$1,$d$2,$d$3,$d$4,$d$5,$U$6,$d$7,$d$8,$d$9],[$c$1,$C$2,$C$3,$c$4,$c$5,$c$6,$c$7,$c$8,$cg$],[$b$1,$b$2,$b$3,$b$4,$b$5,66,$b$7,$b$8,$b$9]]$

Figure $2$

Fringe: f$($N$)=$g$($N$)+$h$($N$)$ Node visited$/$expanded