Lecture Notes: Search Strategies, Algorithms, and Techniques in AI
1. Introduction to Search in AI
AI systems often solve problems by searching through possible solutions.
The search space (or state space) consists of all possible states the problem can be
in.
Each state can be connected to others via operators (actions).
The objective: find a path from an initial state to a goal state.
🔍 2. Search Strategies Overview
Search strategies define how we navigate the search space.
They are generally divided into:
Uninformed Search (Blind Search): No domain-specific knowledge except the
problem definition.
Informed Search (Heuristic Search): Uses problem-specific knowledge to guide the
search.
📌 3. Uninformed Search Techniques
3.1 Breadth-First Search (BFS)
Explores the search tree level by level.
Completeness: Guaranteed to find a solution if one exists.
Optimality: Finds the shallowest solution.
Time & Space Complexity: O(b^d), where:
o b = branching factor
o d = depth of the solution
3.2 Depth-First Search (DFS)
Explores as deep as possible before backtracking.
Completeness: Not guaranteed (can get stuck in infinite depth).
Optimality: Not guaranteed.
Time Complexity: O(b^m), where m = maximum depth.
Space Complexity: O(bm) → more space-efficient than BFS.
3.3 Depth-Limited Search
DFS with a predefined depth limit.
Avoids infinite paths but may miss solutions deeper than the limit.
3.4 Iterative Deepening Search (IDS)
Repeatedly applies depth-limited search with increasing limits.
Combines benefits of BFS and DFS.
Completeness & Optimality: Same as BFS.
Space Complexity: Same as DFS.
3.5 Uniform Cost Search (UCS)
Expands the node with the lowest path cost g(n).
Suitable when path costs vary.
Finds optimal solution (minimum cost).
Time Complexity: Depends on cost structure.
🧠 4. Informed (Heuristic) Search Techniques
4.1 Heuristic Function (h(n))
Estimates cost from node n to goal.
Should be admissible (never overestimates).
Helps guide the search intelligently.
Video link for reference : Hill Climbing Algorithm with Solved Numerical Example in
Artificial Intelligence by Mahesh Huddaar
4.2 Best-First Search
Selects the node with the lowest estimated cost h(n).
Can get stuck in loops if heuristic isn’t perfect.
4.3 Greedy Best-First Search
Always chooses the node with the lowest h(n).
Fast but not guaranteed to find the optimal solution.
4.4 A* Search
Combines actual cost and heuristic: f(n) = g(n) + h(n)
g(n): cost so far; h(n): estimated cost to goal.
Completeness: Yes.
Optimality: Yes, if heuristic is admissible.
Widely used in real-world applications.
🧩 5. Other Techniques
Bidirectional Search: Simultaneous search from start and goal, meeting in the
middle.
Local Search: Works with single current state, e.g., Hill Climbing, Simulated
Annealing.
Genetic Algorithms: Inspired by evolution, used for optimization.
✅ 6. Comparing Techniques
Technique Completeness Optimality Space Complexity Informed?
BFS Yes Yes High (O(b^d)) No
DFS No No Low (O(bm)) No
UCS Yes Yes High No
Greedy No No Low/Medium Yes
Technique Completeness Optimality Space Complexity Informed?
A* Yes Yes High Yes
📚 7. Applications
Game playing (e.g., chess)
Robot navigation
Route finding (e.g., Google Maps)
Problem-solving in scheduling and planning
✏ 8. Key Terms
State Space: All possible configurations.
Operators: Actions to change states.
Path Cost: Sum of costs along the path.
Heuristic: Rule of thumb to estimate future cost.
