Question $25$ pts

Is the heuristic function for this problem always optimistic? $($That is$,$ does it never overestimate the cost

from a node to the nearest goal?$)$

True

False

Graph search treats the state space as a graph. In other words, whenever it encounters a node during a

search it looks to see if the node already exists in the search graph. If so$,$ it may have found a new

shorter path to that node and must adjust the search tree accordingly.

Find the path from the start node $(A)$ to a goal $(G)$ using a breadth$-$first graph search $($shallowest first$).$

Question $310$ pts

What is the sequence of nodes that are explored in the breadth$-$first search?

$A(0),B(1),C(2),E(2),F(3),G(4)$

$A(0),B(1),D(1),C(2),E(2),H(2),F(3),I(3),G(4)$

$A(8),D(8),B(10),H(11),I(10),J(10),F(10),G(10)$

$A(0),B(6),E(4),F(2),G(0)$ Question $45$ pts

What is the path that is found?

$A>DEFG$

$ADH$ I $EFG$

$ADHIJFG$

$ABEFG$

Find the path from the start node $(A)$ to a goal $(G)$ using a depth$-$first graph search $($deepest first$).$

Question $510$ pts

What is the sequence of nodes that are explored in the depth$-$first search?

$A(0),B(6),E(4),F(2),G(0)$

$A(0),B(1),C(2),E(2),F(3),G(4)$

$A(0),B(1),D(1),C(2),E(2),H(2),F(3),I(3),G(4)$

$A(8),D(8),B(10),H(11),I(10),J(10),F(10),G(10)$