Uninformed Search Strategies

  • Uploaded by: skaushik2410
  • 0
  • 0
  • June 2020
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Uninformed Search Strategies as PDF for free.

More details

  • Words: 811
  • Pages: 26
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

Related Documents


More Documents from "Pascal Van Hecke"