Consider the following graph. Arcs are labeled

with action costs and states are labeled with

heuristic values. Assume that ties are broken

alphabetically $($so a partial plan S$->$X$->$A

would be expanded before S$->$X$->$B and S$->$A$-$

$>$Z would be expanded before S$->$B$->$A$.$ and

the goal is to search from node S to node G$.$

We apply search $($graph$)$ algorithms discussed

in the class: DFS$,$ BFS$,$ UCS, A$*.$ For each search algorithm, answer the following questions:

a$)$ Write the nodes that are expanded in order in each search algorithm.

b$)$ What is the path from Start to Goal?

c$)$ What is the cost associated with each path?

d$)$ Which algorithm finds the optimal path $($minimum cost$)?$

e$)$ Is the heuristic function admissible? Why?

S

A

C

B G

$2$

f$)$ Is the heuristic function consistent? Why?