This example is from MIT OCW Artificial Intelligence.
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.
Breadth
First
Setep
1:
Visited:
A
Queue:
B, C, D
Step
2:
Visited:
A, B
Queue:
C, D, E, F G
Step
3:
Visited:
A, B, C
Queue:
D, E, F G, H
Step
4:
Visited:
A, B, C, D
Queue:
E, F, G, H, I, J
Step
5:
Visited:
A, B, C, D, E
Queue:
F, G, H, I, J
Step
6:
Visited:
A, B, C, D, E, F
Queue:
G, H, I, J
Step
7:
Visited:
A, B, C, D, E, F, G
Queue:
H, I, J
Step
8:
Visited:
A, B, C, D, E, F, G, H
Queue:
I, J
Step
9:
Visited:
A, B, C, D, E, F, G, H, I
Queue:
J
Step
10:
Visited:
A, B, C, D, E, F, G, H, I, J
Queue:
Path
for BFS: A, B, C, D, E, F, G, H, I, J
Depth
First
Step
1:
Visited:
A
Stack:
B, C, D
Step
2:
Visited:
A, B
Stack:
E, F, G, C, D
Step
3:
Visited:
A, B, E
Stack:
F, G, C, D
Step
4:
Visited:
A, B, E, F
Stack:
G, C, D
Step
5:
Visited:
A, B, E, F, G
Stack:
C, D
Step
6:
Visited:
A, B, E, F, G, C
Stack:
H, D
Step
7:
Visited:
A, B, E, F, G, C, H
Stack:
D
Step
8:
Visited:
A, B, E, F, G, C, H, D
Stack:
I, J
Step
9:
Visited:
A, B, E, F, G, C, H, D, I
Stack:
J
Step
10:
Visited:
A, B, E, F, G, C, H, D, I, J
Stack:
Path
for DFS: A, B, E, F, G, C, H, D, I, J
Best-First
Node
|
h(n)
|
A
|
0
|
B
|
1
|
C
|
6
|
D
|
3
|
E
|
0
|
F
|
0
|
G
|
0
|
H
|
0
|
I
|
0
|
J
|
0
|
Step
1:
Open:
A
Close:
Step
2:
Open:
B, C, D
Close:
A
h(B)
= 1 ==> the lowest
h(C)
= 6
h(D)
= 3
Step
3:
Open:
C, D, E, F, G
Close:
A, B
h(C)
= 6
h(D)
= 3
h(E)
= 0 ==> the lowest
h(F)
= 0
h(G)
= 0
Step
4:
Open:
C, D, F, G
Close:
A, B, E
h(C)
= 6
h(D)
= 3
h(F)
= 0 ==> the lowest
h(G)
= 0
Step
5:
Open:
C, D, G
Close:
A, B, E, F
h(C)
= 6
h(D)
= 3
h(G)
= 0 ==> the lowest
Step
6:
Open:
C, D,
Close:
A, B, E, F, G
h(C)
= 6
h(D)
= 3 ==> the lowest
Step
7:
Open:
C, I, J
Close:
A, B, E, F, G, D
h(C)
= 6
h(I)
= 0 ==> the lowest
h(J)
= 0
Step
8:
Open:
C, J
Close:
A, B, E, F, G, D, I
h(C)
= 6
h(J)
= 0 ==> the lowest
Step
9:
Open:
C
Close:
A, B, E, F, G, D, I, J
Reach
the Goal J
Path
for Best-First: A, B, E, F, G, D, I, J
A*-Search
Node
|
h(n)
|
A
|
0
|
B
|
1
|
C
|
6
|
D
|
3
|
E
|
0
|
F
|
0
|
G
|
0
|
H
|
0
|
I
|
0
|
J
|
0
|
Step
1:
Open:
A
Close:
Step
2:
Open:
B, C, D
Close:
A
f(A->B)
= h(B) + g(A->B) = 1 + 5 = 6 ==> the lowest
f(A->C)
= h(C) + g(A->C) = 6 + 2 = 8
f(A->D)
= h(D) + g(A->D) = 3 + 4 = 7
Step
3:
Open:
C, D, E, F, G
Close:
A, B
f(A->B->E)
= f(A->B) + h(E) + g(B->E) = 6 + 0 + 6 = 12
f(A->B->F)
= f(A->B) + h(F) + g(B->F) = 6 + 0 + 3 = 9
f(A->B->G)
= f(A->B) + h(G) + g(B->G) = 6 + 0 + 4 = 10
f(A->C)
= h(C) + g(A->C) = 6 + 2 = 8
f(A->D)
= h(D) + g(A->D) = 3 + 4 = 7 ==> the lowest
Step
4:
Open:
C, E, F, G, I, J
Close:
A, B, D
f(A->D->I)
= f(A->D) + h(I) + g(D->I) = 7 + 0 + 6 = 13
f(A->D->J)
= f(A->D) + h(J) + g(D->J) = 7 + 0 + 3 = 10 ==> the lowest
Step
5:
Open:
C, E, F, G, J
Close:
A, B, D, J
Reach
the Goal J
Path
for A*:
A, B, D, J
