Consider the search space below, where S is the start node and G1, G2, and G3 satisfy the goal test. Arcs are labeled with the cost of traversing them and the h functions values are reported beside the graph.

h(S)=100 h(A)=10 h(B)=25 h(C)=1 h(D)=3 h(E)=6

h(G1)=0 h(G2)=0 h(G3)=0

For each of the following search strategies, indicate which goal state is reached (if any) and list, in order, all the states popped off of the OPEN list, and CLOSED. When all else is equal, nodes should be removed from OPEN in alphabetical order.

a) Breadth-First

b) Depth-First

c) Iterative-Deepening

d) Uniform-Cost

e) Best-first (using f = h)

f) A* (using f = g + h)

g) Hill Climbing (using the h function only)

h(s) = 100 h(A) = 10 h(B) = 25 h(C) = 1 h(D) = 3 h(E) = 6 h(G1) = h(62) = 0 h(63) = h(s) = 100 h(A) = 10 h(B) = 25 h(C) = 1 h(D) = 3 h(E) = 6 h(G1) = h(62) = 0 h(63) =