What is Searching in AI?
Searching in Artificial Intelligence is the process of exploring possible states of a problem to find a path from a
start state to a goal state.
We represent problems as a State Space, where:
•Each state is a possible configuration of the problem.
•Actions move the agent from one state to another.
•A search algorithm decides which state to explore next.
Why is Searching Needed?
Searching helps an AI agent:
•Make decisions
•Plan sequences of actions
•Solve puzzles, mazes, routes, and optimization tasks
Examples:
•Finding the shortest route between two cities
•Solving puzzles (8-Puzzle, Sudoku)
•Path planning for robots / games
Types of Searching in AI
Searching methods in AI are broadly classified into two categories based on the information they use during
the search.
Uses Additional
Type of Search Also Called Example Algorithms
Information?
No heuristic / No knowledge
Uninformed Search Blind Search BFS, DFS, UCS
of goal distance
Uses heuristic to estimate
Informed Search Heuristic Search Best First Search, A* Search
closeness to goal
Uninformed Search
Only knows start state, goal test, and possible actions.
Does not know how far or how close it is to the goal.
Informed Search
Uses heuristic function (h(n)) → an estimate of how close a state is to the goal.
Searches more intelligently and efficiently.
Uninformed Search (Blind Search)
Uninformed Search strategies do not use any extra information about how close a state is to the
goal.
They only use:
The start state
The goal test
The possible actions (state transitions)
These algorithms explore the search space blindly, without guidance.
Key Characteristics
• No heuristic (no estimate of distance-to-goal)
• Systematically explore the search space
• May explore unnecessary or irrelevant paths
• Guarantee to find the goal only if search space is finite and strategy is complete
How Uninformed Search Works
[Link] from the initial (start) state.
[Link] successor states.
[Link] exploring states according to the strategy
(Queue, Stack, or Cost Priority).
[Link] when the goal is found.
Common Uninformed Search Algorithms
Algorithm Data Structure Used Strategy
BFS Queue (FIFO) Explore level-by-level
DFS Stack (LIFO) Explore deep path first
UCS Priority Queue Expand lowest-cost path first
Why Learn Uninformed Search First?
Because these methods form the foundation for more advanced searches (like A*) and help us understand:
•State exploration
•Node expansion order
•Cost accumulation (g(n))
Breadth-First Search (BFS)
What is BFS?
Breadth-First Search is an uninformed search algorithm that explores the search
space level-by-level.
It always expands the shallowest / closest nodes first.
How BFS Works
Start from the root (start state).
Visit all neighbors first (same level).
Then move to the next level of neighbors.
Repeat until the goal is found.
Data Structure Used
Queue (FIFO)
→ First In, First Out ensures level-by-level exploration.
Key Properties
Property BFS Behavior
Exploration Order By levels (breadth-first)
Completeness Yes — If goal exists, BFS will find it
Optimality Yes — If edge/step costs are equal
Memory Requirement High (stores entire frontier)
Where BFS is Used
•Finding shortest path in unweighted graphs
•Social network “people you may know”
•Web crawling and indexing
•Network broadcast routing
Level 0
Level 1
Level 2
Level 3
BFS Step-by-Step Execution
(With Enqueue & Dequeue Operations)
Dequeued Enqueued (New Queue (Front →
Step Visited Set Notes
(Expand) Children) Back)
0 — — A {} Initialize
1 A B, C B, C {A} Expand A
2 B D, E C, D, E {A,B} Expand B
3 C F, G D, E, F, G {A,B,C} Expand C
4 D H, I E, F, G, H, I {A,B,C,D} Expand D
5 E (none) F, G, H, I {A,B,C,D,E} Leaf node
6 F (none) G, H, I {A,B,C,D,E,F} Leaf node
7 G (none) H, I {A,B,C,D,E,F,G} Leaf node
8 H (none) I {A,B,C,D,E,F,G,H} Leaf node
{A,B,C,D,E,F,G,H,I
9 I (none) (empty) GOAL FOUND!
}
Summary Table
Measure BFS Result
Completeness Yes
Optimality Yes
Time Complexity O(b^d) = O(2³) = O(8)
Space Complexity O(b^d) = O(2³) = O(8)
b = branching factor ≈ 2
d = goal depth = 3
Depth-First Search (DFS)
What is DFS?
Depth-First Search is an uninformed search algorithm that explores the search space by going as deep as
possible along a path, before backtracking.
How DFS Works
Start at the root node.
Select a path and go deeper until:
You reach the goal, or
You reach a dead end.
If dead end → Backtrack and explore another branch.
Continue until the goal is found.
Data Structure Used
Stack (LIFO)
→ Last In, First Out ensures “go deep first” behavior.
Key Properties
Property DFS Behavior
Exploration Order Deepest path first
Completeness Not guaranteed (may get stuck)
Optimality Not guaranteed (may find longer path first)
Memory Usage Low (stores only current path)
Where DFS is Used
Solving mazes or puzzles
Detecting cycles in graphs
Topological sorting
Searching deep decision trees
Summary Table
Measure DFS Result (Your Example) Explanation
May get stuck in deep or infinite
Completeness No
paths
Optimality No May return deeper or longer path
Time Complexity O(b^m) = O(2³) = O(8) Worst-case explores full depth
Only stores active recursion/stack
Space Complexity O(b × m) = O(6)
path
b = branching factor ≈ 2
m = maximum depth = 3
DFS Step-by-Step Execution
(With Push & Pop Operations - Using Stack)
Pushed (New
Stack (Top →
Step Popped (Expand) Children, Right- Visited Set Notes
Bottom)
first)
0 — — A {} Initialize
C, B (push right-
1 A C, B {A} Expand A
first)
2 B E, D C, E, D {A,B} Expand B
3 D I, H C, E, I, H {A,B,D} Expand D
4 H (none) C, E, I {A,B,D,H} Leaf
5 I (none) C, E {A,B,D,H,I} GOAL FOUND!
6 E (none) C {A,B,D,H,I,E} Leaf
7 C G, F G, F {A,B,D,H,I,E,C} Expand C
8 F (none) G {A,B,D,H,I,E,C,F} Leaf
9 G (none) (empty) {A,B,D,H,I,E,C,F,G} Leaf
Uniform Cost Search (UCS)
What is UCS?
Uniform Cost Search is an uninformed search algorithm that expands the node with the lowest total path cost
(g(n)) first.
It is similar to BFS, but instead of exploring by levels, UCS explores by cost.
How UCS Works
Start at the initial state.
Maintain a priority queue ordered by g(n) (cost from start to node).
Always expand the node with the smallest accumulated cost.
Continue until the goal is removed from the priority queue.
Cost Function
g(n) = Total cost from Start → n
UCS chooses the node with the minimum g(n) at every step.
Data Structure Used
Priority Queue (Min-Heap)
→ Node with lowest cost is always expanded first
Key Properties
Property UCS Behavior
Exploration Order Increasing path cost (cheapest path first)
Completeness Yes (if all step costs > 0)
Optimality Yes (always finds the least-cost path)
Memory Usage High (stores many nodes in the queue)
Where UCS is Used
GPS / Google Maps shortest route
Network routing
Cheapest travel planning
Optimal pathfinding in AI / games
UCS Step-by-Step Execution
(Priority Queue by g(n) = Total Distance from Sibiu)
From To Cost (km)
S F 99
S R 80
RV P 97
F B 211
P B 101
Step Dequeued g(n) Enqueued / Updated Priority Queue (Lowest g first) Visited Notes
0 — — S(0) Sibiu(0) {} Start
1 S 0 RV(80), F(99) RV(80), F(99) {S}
2 RV 80 P(80+97=177) F(99), P(177) {S,RV}
3 F 99 B(99+211=310) P(177), B(310) {S,RV,F}
B(310), B(278) → Update B to Cheaper path
4 P 177 B(177+101=278) {S,RV,F,P}
278 to B!
5 B 278 (none) B(310) GOAL! Stop
Summary Table
Measure UCS Result
Completeness Yes
Optimality Yes
Time Complexity O(b^(1 + C/ε))* → Expanded 5 nodes here
Space Complexity O(b^(1 + C/ε))* → Queue held ~4 nodes here