Section B $(42$ Marks$)$

Graph Search

Construct the search tree for the graph above, indicating the path length to each node. The

numbers shown above are link lengths. Pay careful attention to the arrows; some are bi$-$

directional $($shown thick$)$ while some are unidirectional.

$(8$ marks$)$

Consider the tree shown below. The numbers on the arcs are the arc lengths; the numbers

near states $B,C,$ and $D$ are the heuristic estimates; all other states have a heuristic estimate

of $0.$

Assume that the children of a node are expanded in alphabetical order when no other order

is specified by the search, and that the goal is state J$.$ No visited or expanded lists are used.

What order would the states be expanded by each type of search. Write only the sequence

of states expanded by each search.