1. Give your reason why in DFS every layer only has b nodes in the frontier, where b is the branching factor?
2. Drawthesearchtreeofthebelowstatespacegraph,whereSisthe start state and G is the goal state.
3. For the above example, give the solution found by the DFS algorithm as well as the order of the states that the algorithm expands. Let us assume the tie is broken alphabetically.
4. FortheexampleinQ2,givethesolutionfoundbytheBFSalgorithm with closed list as well as the order of the states that the algorithm expands. Let us assume the tie is broken alphabetically.
5. For the example in Q2, if the cost of arcs is as follow, give the solution found by the uniform cost search algorithm as well as the order of the states that the algorithm expands. Let us assume the tie is broken alphabetically.
6. For the above problem, if the heuristic of each node is as follows, give the solution found by the greedy search algorithm as well as the order of the states that the algorithm expands. Let us assume the tie is broken alphabetically.
Node
S
D
E
P
Q
B
A
C
H
R
F
G
Heuristic
11
7
6
9
8
4
2
3
5
4
2
0