Uninformed Search Algorithms
• Two categories of search algorithms are
available:
– Uninformed search algorithms
– Informed search algorithms
• Uninformed Search Algorithms
– Uninformed (blind) strategies use only the
information available in the problem definition
۳٤
Uninformed Search Algorithms
• There are many uniformed search algorithms:
– Breadth-first search
– Uniform-cost search
– Depth-first search
– Depth-limited search
– Iterative deepening
۳٥
Breadth-First Search (BFS)
• Strategy: expands the shallowest node
• Implementation: put successors nodes at
the end of the queue (FIFO queue)
۳٦
Breadth-First Search
A B C
D E G
۳۷
Breadth-First Search
S
A B C
D E G G G
Nodes are visited as follows: Path:
SABCDEG SAG
۳۸
Breadth-First Search: Properties
• Complete: Yes if b (maximum number of children of a
node) is finite
• Time: 1 + b + b2 + ... + bd = (bd+1 - 1)/(b-1) nodes =
O(bd) (exponential in d (depth) of least-cost
solution)
• Space: O(bd), keeps every node in memory
(serious problem: use of lots of space)
• Optimal: Not optimal in general
۳۹
Uniform-Cost Search
• Strategy: expands the least-cost
unexpanded node
• Implementation: Queue ordered by path
cost
• Note: Also Called “Dijkstra's Algorithm” in the
algorithms literature and similar to “Branch and Bound
Algorithm” in operations research literature
٤۰
Uniform-Cost Search
S
1 5 8
A B C
3 9
7 4 5
D E G
٤۱
Uniform-Cost Search
S
8 1
5
A B C
3 9
7 4 5
D E G G G
Nodes are visited as follows: Path:
SCBAGDE SCG
٤۲
Uniform-Cost Search: Properties
• Complete: Yes
• Time: O(bd)
• Space: O(bd)
• Optimal: Yes
٤۳
Depth-First Search (DFS)
• Strategy: expands the deepest node
• Implementation: put successors nodes at
the front of the queue (LIFO: stack)
44
Depth-First Search
A B C
D E G
45
Depth-First Search
S
A B C
D E G G G
Nodes are visited as follows: Path:
SADEGBC SAG
46
Depth-First Search
• Nodes are numbered in the order of their
exploration
47
Depth-First Search: Properties
• Complete:
– No: fails in infinite-depth spaces, spaces with loops
– Modify to avoid repeated states along path by marking
visited nodes => complete in finite spaces
• Time: O(bm): exponential in m (maximum depth) of
state space (horrible if m >> d (depth) of least-cost
solution)
• Space: O(b * m), i.e.; linear space
• Optimal: No
48
Depth-Limited Search
• Strategy:
– Depth-first search with depth limit L
• Implementation:
– Nodes at given depth L considered as having no
successors
49
Depth-Limited Search
50
Depth-Limited Search: Properties
• Completeness:
– Yes, if L >= d
• Time complexity:
– O(bL)
• Space complexity:
– O(b * L)
• Optimality:
– No
51
Iterative Deepening Search
• The problem with search in limited depth is to
fix the good value of L, because the goal may
be at deeper level
• Iterative deepening has to try all values
possible of L starting at L = 0
52
Iterative Deepening Search
• Advantages of BFS and DFS are combined to
get:
– optimal and complete (as BFS)
– saves memory space (as DFS)
• Iterative deepening search is recommended
when the space of search is large and the
solution depth is unknown
53
Iterative Deepening Search
• Iterative deepening search can work as
follows:
– First apply DFS to depth 0 (i.e., start node has no
successors), then, if no solution reached, apply
DFS to depth 1, etc.
– Repeat this process until solution is found
54
Iterative Deepening Search: The Algorithm
function IDS (problem)
for depth 0 to ∞ do
result Depth-Limited-Search (problem,
depth)
if result ≠ cutoff then
return result
end
55
Iterative Deepening Search
• L=0
S
S
A B C
D E G
56
Iterative Deepening Search
• L=1
A B C
57
Iterative Deepening Search
• L=2
A B C
D E G
58
Iterative Deepening Search:
Properties
• Complete:
– Yes
• Time:
– ( d+1) b0 + db + (d-1)b2 + … + bd = O( bd)
• Space:
– O(b * d)
• Optimal:
– yes, if step cost = 1
59
Comparing Uninformed Strategies
Criterion BFS Uniform DFS Depth- Iterative
-Cost Limited Deepening
Complete Yes Yes No No Yes
Time O( bd) bd bm bl bd
Space O( bd) bd b*m b*l b*d
Optimal Yes Yes No Yes, if Yes
l >= d
60
Comparing Uninformed strategies
What strategy to use and When
• Breadth-First Search:
– Solutions are expected to be shallow
• Uniform-Cost Search:
– Tree search is costly
– It is used to get least cost solution
61
Comparing Uninformed strategies
What strategy to use and When
• Depth-First Search:
– Solutions are expected to be in depth
• Iterative-Deepening Search:
– Space is limited and the shortest solution path is
needed
62
Limitation of Uninformed Strategies
• Uninformed search strategies can find
solutions to problems by systematically
expanding the nodes till finding the goal
• The number of nodes to be explored is so high
that the problem of complexity becomes
critical. This leads to what is called
combinatorial explosion
63
Limitation of Uninformed Strategies
• Thus such strategies are inefficient in most
cases
• Informed search strategies can find solution
more efficiently
64
