Tree Search: BFS, DFS, Best-First, and A* Search

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

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.