SESSION 4

UNINFOMED SEARCH
STRATEGIES
 Session Outcomes

•Student will learn several general-purpose

search algorithms that can be used to solve these
problems.
 UNINFORMED SEARCH STRATEGIES

In this session we discuss several search strategies that come under

the heading of uninformed search, also called blind search.

• No Domain Knowledge: Blind search algorithms operate without

any domain-specific knowledge, heuristics, or guidance about the
problem.
• Systematic Exploration: They systematically explore the search
space by applying predefined rules to generate successor states
until the goal is found or the search is exhausted.
• Brute-Force Approach: Essentially, they employ a brute-force
approach, trying out different possibilities without any preference
or prioritization.
 UNINFORMED SEARCH STRATEGIES

When are blind searches useful?

• When the search space is relatively small or well-structured.
• When no heuristic information or domain knowledge is available
to guide the search.
• As a foundation for more advanced search techniques.
Limitations:
• Can be inefficient, especially in large or complex search spaces, as
they explore the entire search space without guidance.
• May not always find the optimal solution if one exists.
Various types of uninformed search algorithms are:

1. Breadth-first Search

2. Depth-first Search

3. Depth-limited Search

4. Iterative deepening depth-first search

5. Uniform cost search

6. Bidirectional Search
 1. Breadth-first Search:

•Breadth-first search is the most common search strategy for

traversing a tree or graph.

•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.

•Breadth-first search implemented using FIFO queue data structure

for Frontier.

• Goal test is applied to each node when it is generated.

•The algorithm is shown in the following slide.

 Breadth First Search (continued..)

Algorithm:
1. Create a variable called NODE-LIST and set it to initial state.

2. Until a goal state is found or NODE-LIST is empty do

a. Remove the first element from NODE-LIST and call it E.
If NODE-LIST was empty, quit
b. For each way that each rule can match the state described
in E do:
i. Apply the rule to generate a new state
ii. If the new state is a goal state, quit and return this state
iii. Otherwise, add the new state to the end of NODE-
LIST.

Example for BFS is shown in the next slide.

 Breadth First Search (continued..)
Example:

S---> A--->B---->C--->D---->G--->H--->E---->F----> I---->K

 Breadth First Search (continued..)

Time Complexity:

• Time Complexity of BFS algorithm can be obtained by the number of

nodes traversed in BFS until the shallowest Node.

• Suppose d= depth of shallowest solution and b = branching factor

T (b) = b+b2+b3+.......+ bd= O (bd)

Space Complexity:

• Every node generated remains in memory. There will be 0(b d-1) nodes
in the explored set and O(bd) nodes in the frontier.

• So the space complexity is O(bd), i.e., it is dominated by the size of

the frontier.
 Breadth First Search (continued..)

• Completeness:

• BFS is complete, which means if the shallowest goal node is at

some finite depth, then BFS will find a solution.

Optimality:

• BFS is optimal if path cost is a non-decreasing function of the

depth of the node.
 Breadth First Search (continued..)
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:

•It requires lots of memory since each level of the tree must be
saved into memory to expand the next level.

•BFS needs lots of time if the solution is far away from the root
node.
 Water Jug Problem

The state space for this problem can be described as the set of
ordered pairs of integers (x,y) such that
x = 0, 1,2, 3 or 4
y = 0,1,2 or 3;

• x represents the number of gallons of water in the 4-gallon jug.

• y represents the quantity of water in 3-gallon jug.

• The start state is (0,0).

• The goal state is (2,y).

12
A Search Tree for the Water jug Problem
 Production rules for Water Jug Problem
The operators to be used to solve the problem can be described as follows:

Sl No Current state Next State Descritpion

1 (x,y) if x < 4 (4,y) Fill the 4 gallon jug

2 (x,y) if y <3 (x,3) Fill the 3 gallon jug

3 (x,y) if x > 0 (x-d, y) Pour some water out of

the 4 gallon jug
4 (x,y) if y > 0 (x, y-d) Pour some water out of
the 3-gallon jug
5 (x,y) if x>0 (0, y) Empty the 4 gallon jug

6 (x,y) if y >0 (x,0) Empty the 3 gallon jug on

the ground

14
7 (x,y) if x+y >= 4 and (4, y-(4-x)) Pour water from the
y >0 3 –gallon jug into the
4 –gallon jug until
the 4-gallon jug is
full
8 (x, y) if x+y >= 3 (x-(3-y), 3) Pour water from the
and x>0 4-gallon jug into the
3-gallon jug until the
3-gallon jug is full
9 (x, y) if x+y <=4 and (x+y, 0) Pour all the water
y>0 from the 3-gallon jug
into the 4-gallon jug
10 (x, y) if x+y <= 3 (0, x+y) Pour all the water
and x>0 from the 4-gallon jug
into the 3-gallon jug

15
Solution to the water jug problem:

Gallons in the Gallons in the Rule applied

4-gallon jug 3-gallon jug

0 0 2

0 3 9

3 0 2

3 3 7

4 2 5

0 2 9

2 0

16
 Depth First Search

•Depth-first search is a Backtracking technique for finding all

possible solutions using recursion 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 LIFO queue for its implementation.

 Depth First Search(continued….)

Algorithm:

1. If the initial state is a goal state, quit and return success.

2. Otherwise, do the following until success or failure is signaled:

a. Generate a successor, E, of initial state. If there are no more

successors, signal failure.

b. Call Depth-First Search, with E as the initial state

c. If success is returned, signal success. Otherwise continue in

this loop.

18
 Depth First Search(continued….)
Example:
 Depth First Search(continued….)

Completeness: DFS search algorithm is complete within finite state

space as it will expand every node within a limited search tree.

Time Complexity: Time complexity of DFS will be equivalent to the

node traversed by the algorithm. It is given by:
T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
Where, m= maximum depth of any node and this can be much larger
than d (Shallowest solution depth)

Space Complexity: DFS algorithm needs to store only single path from
the root node, hence space complexity of DFS is equivalent to the size of
the fringe set, which is O(bm).

Optimality: DFS search algorithm is non-optimal, as it may generate a

large number of steps or high cost to reach to the goal node.
 Depth First Search(continued….)
Advantages:
•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).

Disadvantages:
•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.
 Depth-Limited Search

•A depth-limited search algorithm is similar to depth-first search

with a predetermined limit.

•Depth-limited search can solve the drawback of the infinite path in

the Depth-first search.

•In this algorithm, the node at the depth limit will treat as it has no
successor nodes further.
 Depth Limited Search(continued…)

Example:
 Depth Limited Search(continued…)

•Completeness: DLS search algorithm is complete if the solution

is above the depth-limit.

•Time Complexity: Time complexity of DLS algorithm is O(bℓ).

(where ℓ is the depth limit of the search).

•Space Complexity: Space complexity of DLS algorithm is

O(b×ℓ).

•Optimal: Depth-limited search can be viewed as a special case of

DFS, and it is also not optimal even if ℓ>d.
 Depth Limited Search(continued…)

Advantages:

•Depth-limited search is Memory efficient.

Disadvantages:

•Depth-limited search also has a disadvantage of

incompleteness.

•It may not be optimal if the problem has more than one
solution.
 Iterative deepening depth-first Search (IDDFS)

•The iterative deepening algorithm is a combination of DFS and

BFS algorithms.

•This search algorithm finds out the best depth limit and does it by
gradually increasing the limit until a goal is found.
 Iterative deepening depth-first Search(continued….)

Example:

•1'st Iteration-----> A

•2'nd Iteration----> A, B, C

•3'rd Iteration------>A, B, D, E, C, F, G

•In thrid iteration the algorithm will find the gold node i.e., G.
 Iterative deepening depth-first Search(continued….)

•Completeness: This algorithm is complete is if the branching

factor is finite.

•Time Complexity: Let's suppose b is the branching factor and

depth is d then the worst-case time complexity is O(bd).

•Space Complexity: The space complexity of IDDFS will

be O(bd).

•Optimality: IDDFS algorithm is optimal if path cost is a non-

decreasing function of the depth of the node.
 Iterative deepening depth-first Search(continued….)

Advantages:

•It combines the benefits of BFS and DFS search algorithm in terms
of fast search and memory efficiency.

Disadvantages:

•The main drawback of IDDFS is that it repeats all the work of the
previous phase.