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
沒有留言:
張貼留言