Uninformed Search Strategies

Uninformed Search Presented by – Shruti kaushik 08mecs118

Definition • Uninformed search uses no information about the likely “direction” of the goal node(s). • It uses only the information available in the problem definition. • • • •

Initial state Search operators Goal Test Path Cost

Measuring Performance • • • •

Completeness Optimality Time Complexity Space Complexity • Branching Factor(b) • Depth (d)



Uninformed Search methods • • • • • •

Breadth First Search (BFS) Depth First Search (DFS) Depth Limited Search Iterative deepening Search(IDS) Bidirectional

Breadth First Search • Breadth-first search goes through the tree level by level, visiting all of the nodes on the top level first, then all the nodes on the second level, and so on. • The fringe is a FIFO QUEUE i.e. new successors go at end. Root node

Level 1 Level 2 Level 3

Breadth-First Search 1

2 5 1 2

6

SI

3 7

4 8

1 0

9

… SG

1 1

S 8

3

1

A 3

D

B 15

7

E

C 20

5

G

Expanded nodes: S A B C D E G Solution found: S A G , cost 18 Number of nodes expanded (including goal node) = 7

Breadth First Search • • Completeness: Yes • Optimality: Yes, for the shortest path • Time complexity:  1 +b + b2 +…..+ b d = O(b d ) • Space complexity: O(bd)

•

Depth First Search • Depth-first search goes through the tree branch by branch, going all the way down to the leaf nodes at the bottom of the tree before trying the next branch. • The fringe is a LIFO queue i.e. new successors go at the beginning. Root node

Level 1 Level 2 Level 3

Depth First Search 1

SI

2 7

3 5

4 6

8

…

SG

S 8

3

1

A 3

D

B 15

7

E

C 20

5

G

Expanded node: S A D E G Solution found: S A G , cost 18 Number of nodes expanded (including goal node) = 5

Depth First Search • • Completeness: No, halts on infinite path • Optimality: No • Time complexity:  1 +b + b2 +…..+ b d = O(b m ) • Space complexity:  O(bm) •

Depth Limited Search • It works exactly like depth-first search • Solves the infinite-path problem • Imposes a maximum limit on the depth of the search. • The choice of the depth parameter is an important factor

Depth Limited Search Limit l = 2 l=0 l=1

l

l=2

Not explored

S

l=0

8

3

l=1

1

A 3

l=2

Limit l = 2

D

B 15

7

E

C 20

5

G

Expanded node: S A D E G Solution found: S A G , cost 18 Number of nodes expanded (including goal node) = 5

Depth Limited Search •

• Completeness: Yes, if depth
iterative deepening Search • Combines the benefit of DFS and BFS with only moderate computational overhead. • Depth-Limited Search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. • On each iteration it visits the nodes in the same order as depth-first search. •

iterative deepening Search Lim it 0 Lim it 1

Lim it 2

S

l=0

8

3

A

l=1 3

l=2

1

D

B 15

7

E

C 20

5

G

Expanded node: S S A B C S A D E G Solution found: S A G , cost 18 Number of nodes expanded (including goal node) = 10

iterative deepening Search • • Completeness: Yes, • Optimality: Yes, for the shortest path • Time complexity:  1 +b + b2 +…..+ bd = O(bd ) • Space complexity:  O(bd) •

Bi-Directional Search • Simultaneously search forward from initial state and backwards from Goal State • Stop when both “meet in the middle” • Cuts the depth of the search tree by half 

Initial State

Goal State

d d/2

d/2

Bi-Directional Search • Merge the solution, if the same state is reached from the other side

Initial State

Goal State Equal?

Bi-Directional Search 1

SI

3

4

8

1 0

9 1 3

…

5

6 2

7 SG

1 1

1 2

Bi-Directional Search •

• Completeness: Yes • Optimality: Yes, for the shortest path • Time complexity:  O(bd/2 ) • Space complexity:  O(bd/2 ) •

Comparison Criterion

BFS

Bi-directional DFS

DLS

IDS

Complete

Yes

Yes

No

Yes, if l  d

Yes

Time

O(bd)

O(bd/2 )

O(bm )

O(bl )

O(bd)

Space

O(bd)

O(bd/2 )

O(bm)

O(bl)

O(bd)

Optimal

Yes

Yes

No

No

Yes

THANK YOU