Breadth First Search

• Create a variable called NODE-LIST and set it to the initial state.
• Until a goal state is found, or NODE-LIST is empty:
1. Remove the first element from NODE-LIST and call it E. If NODE-LIST was empty, then quit.
2. For element E do the following:
1. Apply the rule to generate a new state,
2. If the new state is a goal state. quit and return this state.
3. Otherwise, add the new state to the end of NODE-LIST

Breadth First Search

Step 1: Initially NODE-LIST contains only one node corresponding to the source state A.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

A

Node-List:

Breadth First Search

Step 2: A is removed from NODE-LIST. The node is expanded, and its children B

and C are generated. They are placed at the back of NODE-LIST.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

BC

Node-List:

Breadth First Search

Step 3: Node B is removed from NODE-LIST and is expanded. Its children D, E are

generated and put at the back of NODE-LIST.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

CDE

Node-List:

Breadth First Search

Step 4: Node C is removed from NODE-LIST and is expanded. Its children D and

G are added to the back of NODE-LIST.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

DEDG

Node-List:

Breadth First Search

Step 5: Node D is removed from NODE-LIST. Its children C and F are generated

and added to the back of NODE-LIST.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

EDGCF

Node-List:

Breadth First Search

Step 6: Node E is removed from NODE-LIST. It has no children.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

DGCF

Node-List:

Breadth First Search

Step 7: D is expanded; B and F are put in OPEN.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

GCFBF

Node-List:

Breadth First Search

Step 8: G is selected for expansion. It is found to be a goal node.

Hence the algorithm returns the path A - C - G by following the parent pointers of the node corresponding to G.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

Goal Reached!!

Breadth First Search

Advantages of Breadth first search are:

• One of the simplest search strategies
• BFS is Complete. If there is a solution, BFS is guaranteed to find it.
• If there are multiple solutions, then a minimal solution will be found

Disadvantages of Breadth first search are :

• The breadth first search algorithm cannot be effectively used unless the search space is quite small.

Depth First Search

• If the initial state is a goal state, quit and return success.
• Otherwise, do the following until success or failure is signaled:
1. Generate a successor, E, of the initial state. If there are no more successors, signal failure.
2. Call Depth-First Search with E as the initial state.
3. If success is returned, signal success. Otherwise continue in this loop.

Depth First Search

Step 1: Initially NODE-LIST contains only one node corresponding to the source state A.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

A

Node-List:

Depth First Search

Step 2: A is removed from NODE-LIST. A is expanded, and its children B

and C are inserted at the front of NODE-LIST.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

BC

Node-List:

Depth First Search

Step 3: Node B is removed from NODE-LIST and its children D and E are pushed in front of NODE-LIST.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

DEC

Node-List:

Depth First Search

Step 4: Node D is removed from NODE-LIST and its children C and F are pushed in front of NODE-LIST.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

CFEC

Node-List:

Depth First Search

Step 5: Node C is removed from NODE-LIST and its children G is pushed in front of NODE-LIST.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

GFEC

Node-List:

Depth First Search

Step 6: Node G is expanded and found to be a goal.

Hence the algorithm returns the path A – B – D - C - G and terminates.

A

B

C

D

E

D

G

C

F

B

F

G

H

G

H

G

E

GFEC

Node-List:

Goal Reached!!

Depth First Search

Advantages of Depth-first search are:

• Depth-first search requires less memory since only the nodes on the current path are stored.
• The depth-first search may find a solution without examining much of the search space at all.

Disadvantages of Depth-first search are:

• May find a sub-optimal solution (one that is deeper or more costly than the best solution)
• Incomplete: without a depth bound, one may not find a solution even if one exists