Fundamentals of Artificial Intelligence

Uninformed Search Algorithms

Dr. Iman Abu Hashish

Department of Data Science and Artificial Intelligence
e-mail: [Link]@[Link]
Phone Ext.: 5104
Office: SB-G04

Spring Semester
Academic Year 2024/2025
Table of Contents

1. Objectives

2. Uninformed Search Algorithms

Breadth-First Search
Uniform-Cost Search
Depth-First Search

3. References

Uninformed Search Algorithms I. Abu Hashish 2

Objectives
Objectives

“In which we see how an agent can look ahead to find a sequence of
actions that will eventually achieve its goal.”

• Breadth-First Search
• Uniform-Cost Search
• Depth-First Search

Uninformed Search Algorithms I. Abu Hashish 4

Uninformed Search Algorithms
Uninformed Search Algorithms

An uninformed search algorithm is given no clue about how close a

state is to the goal.

• An uninformed agent with no knowledge of Romanian

geography – has no clue whether going to Zerind or Sibiu is a
better first step.
• No additional information about states beyond what is provided
in the problem definition.
• Breadth-First Search, Uniform-Cost Search, and Depth-First
Search are considered uninformed search algorithms.

Uninformed Search Algorithms I. Abu Hashish 6

Breadth-First Search

When all actions have the same cost, an appropriate strategy is

breadth-first search.

• The root node is expanded first.

• Then all the successors of the root node are expanded next –
then their successors, and so on.
• All nodes are expanded at a given depth before any nodes at
the next level are expanded.
• Breadth-First Search implements an early goal test – checking
whether a node is a solution as soon as it is generated.

Uninformed Search Algorithms I. Abu Hashish 7

Breadth-First Search

Note the early goal check.

Uninformed Search Algorithms I. Abu Hashish 8

Breadth-First Search

The evaluation function f(n) is the depth of the node – number of

actions it needs to reach the node.

Uninformed Search Algorithms I. Abu Hashish 9

Breadth-First Search

Consider the state space graph shown below. Assuming that S is the
initial state and G is the goal state. What is the solution path using
the breadth-first search algorithm?

a G
c
b

e
d f

S h
r

p q

Hint: always expand the shallowest node in the frontier first and use
the alphabetical order as a tie-breaker.
Uninformed Search Algorithms I. Abu Hashish 10
Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S

Uninformed Search Algorithms I. Abu Hashish 11

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S

S-d
d e p S-e

S-p

Uninformed Search Algorithms I. Abu Hashish 12

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S

S-d
d e p
S-e

S-p
b c e
S-d-b

S-d-c

S-d-e

Uninformed Search Algorithms I. Abu Hashish 13

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S

S-d
d e p
S-e

S-p
b c e h r
S-d-b

S-d-c

S-d-e

S-e-h

S-e-r

Uninformed Search Algorithms I. Abu Hashish 14

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S

S-d
d e p
S-e

S-p
b c e h r q
S-d-b

S-d-c

S-d-e

S-e-h

S-e-r

S-p-q

Uninformed Search Algorithms I. Abu Hashish 15

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S S-d-b-a

S-d
d e p
S-e

S-p
b c e h r q
S-d-b

a
S-d-c

S-d-e

S-e-h

S-e-r

S-p-q

Uninformed Search Algorithms I. Abu Hashish 16

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S S-d-b-a

S-d S-d-c-a
d e p
S-e

S-p
b c e h r q
S-d-b

a a
S-d-c

S-d-e

S-e-h

S-e-r

S-p-q

Uninformed Search Algorithms I. Abu Hashish 17

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S S-d-b-a

S-d S-d-c-a
d e p
S-e S-d-e-h

S-p S-d-e-r
b c e h r q
S-d-b

a a h r
S-d-c

S-d-e

S-e-h

S-e-r

S-p-q

Uninformed Search Algorithms I. Abu Hashish 18

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S S-d-b-a

S-d S-d-c-a
d e p
S-e S-d-e-h

S-p S-d-e-r
b c e h r q
S-d-b S-e-h-p

a a h r p q
S-d-c S-e-h-q

S-d-e

S-e-h

S-e-r

S-p-q

Uninformed Search Algorithms I. Abu Hashish 19

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S S-d-b-a

S-d S-d-c-a
d e p
S-e S-d-e-h

S-p S-d-e-r
b c e h r q
S-d-b S-e-h-p

a a h r p q f
S-d-c S-e-h-q

S-d-e S-e-r-f

S-e-h

S-e-r

S-p-q

Uninformed Search Algorithms I. Abu Hashish 20

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S S-d-b-a

S-d S-d-c-a
d e p
S-e S-d-e-h

S-p S-d-e-r
b c e h r q
S-d-b S-e-h-p

a a h r p q f
S-d-c S-e-h-q
. . .
. . . S-d-e S-e-r-f
. . .
. . . S-e-h .
.
. . .
. . . S-e-r .
.
. . .
S-p-q .
.
.

Uninformed Search Algorithms I. Abu Hashish 21

Breadth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S S S-d-b-a

S-d S-d-c-a
d e p
S-e S-d-e-h

S-p S-d-e-r
b c e h r q
S-d-b S-e-h-p

a a h r p q f
S-d-c S-e-h-q
.
. . .
S-d-e .
. . . c G .
. . .
S-e-h
. . . S-e-r-f
. . .
S-e-r
. . . S-e-r-f-c
. . .
S-p-q
S-e-r-f-G

Uninformed Search Algorithms I. Abu Hashish 22

Breadth-First Search Performance Evaluation

1 node
S
b
b nodes

b2 nodes
m d

bd nodes
G

bm nodes

Where d is the depth, i.e., the number of actions in an optimal path, m is the
maximum number of actions in any path, while b is the branching factor, i.e.,
the number of successors of a node that need to be considered.
Uninformed Search Algorithms I. Abu Hashish 23
Breadth-First Search Performance Evaluation

Is it complete?

• Yes.

Does it return an optimal path?

• Yes, assuming all actions have the same cost – always finds a
solution with a minimal number of actions, because when it is
generating nodes at depth d, it has already generated all the
nodes at depth d − 1.

How much time does it take?

• O(bd ), assuming a depth of d tiers and a b branching factor.

How much space it needs?

• O(bd ), assuming a depth of d tiers and a b branching factor.

Uninformed Search Algorithms I. Abu Hashish 24
Uniform-Cost Search

When actions have different costs, an obvious choice is to use

uniform-cost search.

• The evaluation function g(n) is the cumulative cost of the path

from the root to the current node.
• The algorithm can be implemented as a call to
Best-First-Search with Path-Cost as the evaluation function.
• Uniform-cost search implements a late goal test – tests for goals
only when it expands a node, not when it generates a node.

Uninformed Search Algorithms I. Abu Hashish 25

Uniform-Cost Search

Assuming that Sibiu is the initial state, and Bucharest is the goal
state, what is the solution path using uniform-cost algorithm?

Uninformed Search Algorithms I. Abu Hashish 26

Uniform-Cost Search

Consider the state space graph shown below. Assumin that S is the
initial state and G is the goal state. What is the solution path using
the uniform-cost search algorithm?

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Hint: always expand the cheapest nodes in the frontier first and use
the alphabetical order as a tie-breaker.

Uninformed Search Algorithms I. Abu Hashish 27

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S

Uninformed Search Algorithms I. Abu Hashish 28

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S
3 9 1
S-d
d e p
S-e

S-p

Uninformed Search Algorithms I. Abu Hashish 29

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S
3 9 1
S-d
d e p
S-e
16
S-p
p
S-p-q

Uninformed Search Algorithms I. Abu Hashish 30

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S
3 9 1
S-d
d e p
S-e
4 11 5 16
S-p
b c e p
S-p-q

S-d-b

S-d-c

S-d-e

Uninformed Search Algorithms I. Abu Hashish 31

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S
3 9 1
S-d
d e p
S-e
4 11 5 16
S-p
b c e p
S-p-q
6
S-d-b
a
S-d-c

S-d-e

S-d-b-a

Uninformed Search Algorithms I. Abu Hashish 32

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S S-d-e-h
3 9 1
S-d S-d-e-r
d e p
S-e
4 11 5 16
S-p
b c e p
S-p-q
6 13 7
S-d-b
a h r
S-d-c

S-d-e

S-d-b-a

Uninformed Search Algorithms I. Abu Hashish 33

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S S-d-e-h
3 9 1
S-d S-d-e-r
d e p
S-e S-d-e-r-f
4 11 5 16
S-p
b c e p
S-p-q
6 13 7
S-d-b
a h r
8 S-d-c
f
S-d-e

S-d-b-a

Uninformed Search Algorithms I. Abu Hashish 34

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S S-d-e-h
3 9 1
S-d S-d-e-r
d e p
S-e S-d-e-r-f
4 11 5 16
S-p S-d-e-r-f-c
b c e p
S-p-q S-d-e-r-f-G
6 13 7
S-d-b
a h r
8 S-d-c
f
S-d-e
11 10
S-d-b-a
c G

Uninformed Search Algorithms I. Abu Hashish 35

Uniform-Cost Search

2
a 2 3
G
c
b 2
8
1
2 e
d f
3 9 8
2
1
S h
4
1 4 r
p 15 q

Search Tree Frontier

S
S S-d-e-h
3 9 1
S-d S-d-e-r
d e p
S-e S-d-e-r-f
4 11 5 17 11 16
S-p S-d-e-r-f-c
b c e h r p
S-p-q S-d-e-r-f-G
6 13 7
S-d-b S-e-h
a h r
8 S-d-c S-e-r
f
S-d-e
11 10
S-d-b-a
c G

Uninformed Search Algorithms I. Abu Hashish 36

Uniform-Cost Performance Evaluation

Is it complete?

• Yes – it considers all paths systematically in order of increasing

cost.

Does it return an optimal path?

• Yes – the first solution it finds will have a cost that is at least as
low as the cost of any other node in the frontier.

How much time does it take?

∗
• O(bC /ϵ ) where C∗ is the cost of the optimal solution, and ϵ is a
lower bound on the cost of each action, with ϵ > 0

How much space it needs?

∗
• O(bC /ϵ
)
Uninformed Search Algorithms I. Abu Hashish 37
Depth-First Search

Depth-first search always expands the deepest node in the frontier

first.

• Search proceeds immediately to the deepest level of the search

tree, where the nodes have no successors.
• The search then backs up to the next deepest node that still
has unexpanded successors.
• Depth-First Search implements a late goal test.

Uninformed Search Algorithms I. Abu Hashish 38

Depth-First Search

Consider the state space graph shown below. Assuming S is the

initial state and G is the goal state. What is the solution path using
the depth-first search algorithm?

a G
c
b

e
d f

S h
r

p q

Hint: always expand the deepest node in the frontier first and use
the alphabetical order as a tie-breaker.
Uninformed Search Algorithms I. Abu Hashish 39
Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S

Uninformed Search Algorithms I. Abu Hashish 40

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S

S-d
d e p
S-e

S-p

Uninformed Search Algorithms I. Abu Hashish 41

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S

S-d
d e p
S-e

S-p
b c e
S-d-b

S-d-c

S-d-e

Uninformed Search Algorithms I. Abu Hashish 42

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S

S-d
d e p
S-e

S-p
b c e
S-d-b

a S-d-c

S-d-e

S-d-b-a

Uninformed Search Algorithms I. Abu Hashish 43

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S

S-d
d e p
S-e

S-p
b c e
S-d-b

a a S-d-c

S-d-e

S-d-b-a

S-d-c-a

Uninformed Search Algorithms I. Abu Hashish 44

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S S-d-e-h

S-d S-d-e-r
d e p
S-e

S-p
b c e
S-d-b

a a h r S-d-c

S-d-e

S-d-b-a

S-d-c-a

Uninformed Search Algorithms I. Abu Hashish 45

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S S-d-e-h

S-d S-d-e-r
d e p
S-e S-d-e-h-p

S-p S-d-e-h-q
b c e
S-d-b

a a h r S-d-c

S-d-e
p q
S-d-b-a

S-d-c-a

Uninformed Search Algorithms I. Abu Hashish 46

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S S-d-e-h

S-d S-d-e-r
d e p
S-e S-d-e-h-p

S-p S-d-e-h-q
b c e
S-d-b S-d-e-h-p-q

a a h r S-d-c

S-d-e
p q
S-d-b-a

S-d-c-a
q

Uninformed Search Algorithms I. Abu Hashish 47

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S S-d-e-h

S-d S-d-e-r
d e p
S-e S-d-e-h-p

S-p S-d-e-h-q
b c e
S-d-b S-d-e-h-p-q

a a h r S-d-c S-d-e-r-f

S-d-e
p q f
S-d-b-a

S-d-c-a
q

Uninformed Search Algorithms I. Abu Hashish 48

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S S-d-e-h

S-d S-d-e-r
d e p
S-e S-d-e-h-p

S-p S-d-e-h-q
b c e
S-d-b S-d-e-h-p-q

a a h r S-d-c S-d-e-r-f

S-d-e S-d-e-r-f-c
p q f
S-d-b-a S-d-e-r-f-G

S-d-c-a
q c G

Uninformed Search Algorithms I. Abu Hashish 49

Depth-First Search

a G
c
b
e
d f

S h
r
p q

Search Tree Frontier

S
S S-d-e-h

S-d S-d-e-r
d e p
S-e S-d-e-h-p

S-p S-d-e-h-q
b c e
S-d-b S-d-e-h-p-q

a a h r S-d-c S-d-e-r-f

S-d-e S-d-e-r-f-c
p q f
S-d-b-a S-d-e-r-f-G

S-d-c-a S-d-e-r-f-c-a
q c G

Uninformed Search Algorithms I. Abu Hashish 50

Depth-First Search Performance Evaluation

Is it complete?

• No – m could be infinite and, thus, it can get stuck in an infinite

loop.

Does it return an optimal path?

• No – it returns the first path it finds even if it is not the cheapest.

How much time does it take?

• O(bm ), assuming a depth of m tiers and a b branching factor.

How much space it needs?

• O(bm), assuming a depth of m tiers and a b branching factor.

Uninformed Search Algorithms I. Abu Hashish 51

References
References

• Stuart Russel and Peter Norvig. 2021. Artificial Intelligence: A

Modern Approach (4th .ed.). Pearson.

Uninformed Search Algorithms I. Abu Hashish 53