Suppose you have the following search space:

State	Next	Cost
A	B	4
A	C	1
B	D	3
B	E	8
C	D	2
C	F	6
D	C	2
D	E	4
E	G	2
F	G	8

(a) Draw the state space for this problem.

(b) Assume that the initial state is A and the goal state is G. List the order of the nodes visited by each of the following search strategies to find a path from the initial state to the goal state. Breadth-first Search: Depth-first Search: Uniform Cost Search:

(c) What is the path cost to the goal state under each of these search strategies? Breadth-first Search: Depth-first Search: Uniform Cost Search: