ARTIFICIAL INTELLIGENCE
Uninformed Search Strategies
1
ARTIFICIAL INTELLIGENCE
Search Process : UNINFORMED SEARCH STRATEGIES
• Breadth-First Search (BFS)
• Uniform-Cost Search (UCS)
• Depth-First Search (DFS)
• Depth-Limited Search
• Iterative Deepening Depth First Search
Definitions
• Branching Factor (b) : The maximum number of successors to a node.
• Depth (d) : The depth of the shallowest goal node.
• Maximum path length (m) : The maximum length of any path in the state space.
• Time : The number of nodes generated in the search process.
• Space : The maximum number of nodes stored in memory during the search process.
2
ARTIFICIAL INTELLIGENCE
Search Process :
Start node
B C
D E F
G H I J K L
Goal node
3
ARTIFICIAL INTELLIGENCE
Search Process : BREADTH-FIRST SEARCH (BFS)
• All nodes at a given depth are expanded before any nodes at a lower level are
expanded. Added queue
Removed queue
Expanded
A 1 Start node
Level 1 B 2 C 3
Level 2 D 4 E 5 F 6
G H I J K L
7 8 9
Level 3
A
K,
F,
C, G,
Queue : I,B,C
D,
C
G, LE,
FD
J, J,K,
H,
E,
D F, LJ,H JJ,I, LK,
FI,LK,H
I,H,K,G,
H, J L Queuing: FIFO
4
ARTIFICIAL INTELLIGENCE
Search Process : BREADTH-FIRST SEARCH (BFS)
• BFS will always find a solution, but it may not be the most efficient one.
• Time Complexity –
• Space Complexity –
• Is it Complete?
• Is it Optimal?
Key :
b – branching factor.
d – depth of shallowest goal node.
m – maximum depth of search tree.
l – depth limit.
5
ARTIFICIAL INTELLIGENCE
Breadth First Search Process (right to left) :
Start node
B C
D E F
G H I J K L
Goal node
6
ARTIFICIAL INTELLIGENCE
Search Process : UNIFORM-COST SEARCH
• The node with the least cost is expanded first.
• Here the total path cost is considered. Added queue
Removed queue
Expanded
A 1
10 5
B 3 C 2
7
1 PC: 5 + 7 = 12 10 PC: 5 + 10 = 15
PC: 10 + 1 = 11
D 4 E 5 F
3 9 4 1
PC: 11 + 3 = 14 PC: 12 + 4 = 16 PC: 12 + 1 = 13
PC: 11 + 9 = 20
G H J NOTE: Node F is never
I
expanded, therefore, nodes
K & L from our BFS tree are
A
B,
C,G,
D,
G,
B
Queue : J,
E, E,
FG, I,FF,H
BF, F,
H I,HH never seen in this tree. 7
ARTIFICIAL INTELLIGENCE
Search Process : UNIFORM-COST SEARCH (UCS)
• UCS is only concerned about the total path cost.
• Time Complexity –
• Space Complexity –
• Is it Complete?
• Is it Optimal?
• How does the worst case time
and space complexity compare
to breadth-first search?
Key :
b – branching factor.
d – depth of shallowest goal node.
m – maximum depth of search tree.
l – depth limit.
c* - cost of optimal solution; ε – step cost. 8
ARTIFICIAL INTELLIGENCE
Search Process : DEPTH-FIRST SEARCH (DFS)
• Follows each path to the greatest depth before moving to the next path.
Added queue
Removed queue
Expanded
A 1 Start node
Level 1 B 2 C 6
Level 2 D 3 E 7 F
11
G 4 H 5 I 8 J
Level 3
FJ,
I,
A
D,
Queue : G,
B,C
C
H, FFC
E,J, H,F C Queuing: LIFO
9
ARTIFICIAL INTELLIGENCE
Search Process : DEPTH-FIRST SEARCH (DFS)
• Time Complexity –
• Space Complexity –
• Is it Complete?
• Is it Optimal?
• What is the disadvantage of
DFS?
• How is its space complexity
compared to that of BFS?
Key :
b – branching factor.
d – depth of shallowest goal node.
m – maximum depth of search tree.
l – depth limit. 10
ARTIFICIAL INTELLIGENCE
Depth First Search Process (right to left) :
Start node
B C
D E F
G H I J K L
Goal node
11
ARTIFICIAL INTELLIGENCE
Search Process : DEPTH-LIMITED SEARCH
• Depth-Limited Search is DFS with predefined depth limit. We have a cut-
off preset at a depth limit of l. Added queue
Removed queue
Expanded
A 1 Start node
Level 1 B 2 C 4
Level 2 D 3 E 5 F
Is this result the same
G H I J
as DFS?
Level 3
FJ,
I,
A
D,
Queue : G,
B,C
C
H, FFC
E,J, H,F C What changes if l = 2?
12
ARTIFICIAL INTELLIGENCE
Search Process : DEPTH-LIMITED SEARCH
• Time Complexity –
• Space Complexity –
• Is it Complete?
• Is it Optimal?
• What is the disadvantage
of Depth Limited Search?
• What is the advantage of
Depth Limited Search?
• What is the Diameter?
Key :
b – branching factor.
d – depth of shallowest goal node.
m – maximum depth of search tree.
l – depth limit. 13
ARTIFICIAL INTELLIGENCE
Search Process : ITERATIVE DEEPENING DEPTH-FIRST SEARCH (IDS)
• IDS is DFS which gradually increases its depth limit until the goal node is
reached. Added queue
Removed queue
Expanded
Limit = 13
0
2 A 1 2 5
B 36 C 4 8
D 7 E 9 F
G H I J
Queue : D,
B,
G,
C J,FFCH,
A
FI,
E,
J,
H, CF C 14
ARTIFICIAL INTELLIGENCE
Search Process : ITERATIVE DEEPENING DEPTH-FIRST SEARCH (IDS)
• IDS combines the benefits of DFS and BFS. IDS has modest memory requirements,
like DFS. IDS is complete if the branching factor is finite, like BFS.
• Time Complexity -
• Space Complexity -
• Is it Complete?
• Is it Optimal?
• Is IDS wasteful?
• Is IDS preferred?
Key :
b – branching factor.
d – depth of shallowest goal node.
m – maximum depth of search tree.
l – depth limit. 15
ARTIFICIAL INTELLIGENCE
Search Process : Define problem formulation for Missionaries and Cannibals.
Three missionaries and three cannibals must cross a river using a boat which can
carry at most two people, under the constraint that, for both banks, if there are
missionaries present on the bank, they cannot be outnumbered by cannibals (if
they were, the cannibals would eat the missionaries). The boat cannot cross the
river by itself with no people on board.
State – 3 numbers (I, j, k)
Initial State –
Operators –
Goal Test –
Path Cost –
16
ARTIFICIAL INTELLIGENCE
Search Process : Define problem formulation for Missionaries and Cannibals.
Provide the optimal solution to this problem (consisting of 3 missionaries, and 3
cannibals trying to cross a river on a boat, so that the number of cannibals do not
exceed the number of missionaries.
Let Missionaries be represented by ‘M’; Cannibals by ‘C’; Boat by ‘B’.
Left Bank of River Right Bank of River Left Bank of River Right Bank of River
Start (M3, C3, B1) (M1, C1, B1) (M2, C2, B1) (M1, C1)
Node (M2, B1)
(M2, C2) (M1, C1, B1)
(M1, B1) (M3, C1, B1)
(C2) (C1, B1)
(M3, C2, B1) (C1)
(C2, B1) (M3)
(C3, B1)
(C2, B1)
(M3) (C3, B1)
(C1, B1) (M3, C2, B1)
(C1)
(C1, B1)
(M3, C1, B1) (C2)
(M2, B1)
(C2, B1) (M3, C1)
(C2, B1)
(M1, C1) (M2, C2, B1)
(M1, C1, B1) Goal
(M3, C3, B1)
Node
17
