Agenda
Solution to the exercises Q&A
Question 1
Give your reason why in DFS every layer only has nodes at most in the frontier, where is the branching factor?
Depth first search always expands the deepest node in the frontier.
Question 1
Give your reason why in DFS every layer only has nodes at most in the frontier, where is the branching factor?
Depth first search always expands the deepest node in the frontier.
S AAB
S
CG B
BCC CGG
G
Question 1
Give your reason why in DFS every layer only has nodes at most in the frontier, where is the branching factor?
Depth first search always expands the deepest node in the frontier.
Proof by contradiction:
Assume that there are more than nodes in the frontier for a layer, then there are at least two nodes (denoted by left node and right node) in that layer in the frontier coming from different parents.
Since these two nodes in the frontier, their parents should be expanded already. However, according to DFS, we always expand the deepest node in the frontier (say from left to right). It is impossible to expand the right parent node which is in a shallower layer before expanding the left node, thus, a contradiction.
Question 2
Draw the search tree of the below state space graph, where S is the start state and G is the goal state.
S
DEP
BCEHRQ
AAHRPQF
PQFQ CG QCGA
A
Question 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.
Solution: S D E R F G
Nodes to be expanded: S D B A C A E HPQQRFCAG
S
DEP
BCE
AAHR
PQF
QCG A
Question 4
For the example in Q2, give the solution found by the BFS algorithm with closed list as well as the order of the states that the algorithm expands.
Let us assume the tie is broken alphabetically.
S
DEP
BCEHRQ
AA PQF
CG
Solution: S E R F G
Nodes to be expanded: S D E P B C H RQAFG
S
D
E
P
B
C
H
R
Q
A
F
Question 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.
0
4B C11E5 H17 11R 16Q
6
Solution: S D E R F G
Nodes to be expanded: S P D B E A R F E G
S D3E91P
AHR
13 7 8
F
11C G10
Question 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
Solution: S E R F G
Nodes to be expanded: S E R F G
S
DEP
HR F
CG