Uniformed Search Strategies

1
Ms. Richa Singh
CSE(AI)
CONTENTS
 Basic
 Brute-Force Search Strategies

 Breadth-First Search

 Depth-First Search

 Bidirectional Search

 Uniform Cost Search

 Comparison of Various Algorithms

Complexities

2
BASIC
 The search algorithms in this section have
no additional information on the goal
node other than the one provided in the
problem definition.
 The plans to reach the goal state from the

start state differ only by the order and/or

length of actions.
 Uninformed search is also called Blind

search.
3
CONTI…
Each of these algorithms will have:
A problem graph, containing the start node S and

the goal node G.

A strategy, describing the manner in which the

graph will be traversed to get to G .

A fringe, which is a data structure used to store

all the possible states (nodes) that you can go

from the current states.
A tree, that results while traversing to the goal

node.
A solution plan, which the sequence of nodes
4
from S to G.
BRUTE-FORCE SEARCH STRATEGIES
 They are most simple, as they do not need any
domain-specific knowledge. They work fine with
small number of possible states.

 Requirements −
 State description

 A set of valid operators

 Initial state

 Goal state description

5
BREADTH-FIRST SEARCH
 Starts from the root node, explores the
neighboring nodes first and moves towards the
next level neighbors.
 Generates one tree at a time until the solution is

found.
 Can be implemented using FIFO queue data

structure.
 Provides shortest path to the solution.

 If branching factor

b = Average number of child nodes for a given

node
d = depth 6

Then, number of nodes at level d = bd

CONTI…
 Total no of nodes created in worst case is b +
b2 + b 3 + … + b d .

 Breadth-first search is the most common search

strategy for traversing a tree or graph. This
algorithm searches breadth-wise in a tree or
graph, so it is called breadth-first search.

 BFS algorithm starts searching from the root

node of the tree and expands all successor node
at the current level before moving to nodes of
next level. 7
CONTI…
 Its complexity depends on the number of nodes.
It can check duplicate nodes.

8
CONTI…
 Traversing of the tree using BFS algorithm from
the root node S to goal node K.
 BFS search algorithm traverse in layers, so it will

follow the path which is shown by the dotted

arrow, and the traversed path will be:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K

9
CONTI…
Advantages
BFS will provide a solution if any solution exists.

If there are more than one solutions for a given

problem, then BFS will provide the minimal
solution which requires the least number of steps.

Disadvantages
Since each level of nodes is saved for creating

next one, it consumes a lot of memory space.

Space requirement to store nodes is exponential.
BFS 10
needs lots of time if the solution is far away
from the root node.
DEPTH-FIRST SEARCH
 It is implemented in recursion with LIFO stack
data structure.

 It creates the same set of nodes as Breadth-First

method, only in the different order.

 As the nodes on the single path are stored in

each iteration from root to leaf node, the space
requirement to store nodes is linear.

 With branching factor b and depth as m, the

11
storage space is bm.
CONTI…
 The solution to this issue is to choose a cut-off
depth.

 If the ideal cut-off is d, and if chosen cut-off is

lesser than d, then this algorithm may fail.

 If chosen cut-off is more than d, then execution

time increases.

12
CONTI…
 Depth-first search is a recursive algorithm for
traversing a tree or graph data structure.

 It is called the depth-first search because it starts

from the root node and follows each path to its
greatest depth node before moving to the next
path.

 DFS uses a stack data structure for its

implementation.

 The process of the DFS algorithm is similar to the

13

BFS algorithm.
CONTI…
 Its
complexity depends on the number of
paths. It cannot check duplicate nodes.

14
CONTI…
Advantage
DFS requires very less memory as it only needs to

store a stack of the nodes on the path from root node to

the current node.
It takes less time to reach to the goal node than BFS

algorithm (if it traverses in the right path).

Disadvantage
There is the possibility that many states keep re-

occurring, and there is no guarantee of finding the

solution.
DFS algorithm goes for deep down searching and

sometime it may go to the infinite loop. 15

CONTI…
 Root node--->Left node ----> right node.
 It will start searching from root node S, and

traverse A, then B, then D and E, after traversing

E, it will backtrack the tree as E has no other
successor and still goal node is not found. After
backtracking it will traverse node C and then G,
and here it will terminate as it found goal node.

16
BIDIRECTIONAL SEARCH
 It searches forward from initial state and backward
from goal state till both meet to identify a
common state.

 The path from initial state is concatenated with

the inverse path from the goal state. Each search
is done only up to half of the total path.

 Bidirectional search algorithm runs two

simultaneous searches, one form initial state
called as forward-search and other from goal node
called as backward-search, to find the goal node. 17
CONTI…
 Bidirectional search replaces one single search
graph with two small subgraphs in which one
starts the search from an initial vertex and other
starts from goal vertex.

 The search stops when these two graphs

intersect each other.

18
CONTI…
Advantages
Bidirectional search is fast.

Bidirectional search requires less memory

Disadvantages
Implementation of the bidirectional search tree is

difficult.

In bidirectional search, one should know the goal

state in advance. 19
CONTI…

20
UNIFORM COST SEARCH
 Sorting is done in increasing cost of the path to a
node. It always expands the least cost node.

 It is identical to Breadth First search if each

transition has the same cost.

 It explores paths in the increasing order of cost.

 Uniform-cost search is a searching algorithm

used for traversing a weighted tree or graph.
This algorithm comes into play when a different
21
cost is available for each edge.
CONTI…
 The primary goal of the uniform-cost search is to find
a path to the goal node which has the lowest
cumulative cost.

 Uniform-cost search expands nodes according to their

path costs form the root node.

 It can be used to solve any graph/tree where the

optimal cost is in demand. A uniform-cost search
algorithm is implemented by the priority queue.

 It gives maximum priority to the lowest cumulative

cost. Uniform cost search is equivalent to BFS
algorithm if the path cost of all edges is the same. 22
CONTI…

23
CONTI…
Advantages
Uniform cost search is optimal because at every

state the path with the least cost is chosen.

Disadvantages
It does not care about the number of steps

involve in searching and only concerned about

path cost.

Due to which this algorithm may be stuck in an

infinite loop. 24
 COMPARISON OF VARIOUS SEARCH
ALGORITHMS COMPLEXITIES

Breadth Depth Uniform

Criterion First First Bidirectional Cost

Time bd bm bd/2 bd

Space bd bm bd/2 bd

Optimality Yes No Yes Yes

Completenes Yes No Yes Yes

s 25
THANKS

26