Questions
3–4 questions per semester exam
Difficulty
Medium
Importance
High yield for University end-semester theory exams
Overview
Search algorithms are fundamental procedures in Artificial Intelligence used to traverse state spaces to find a path from an initial state to a goal state. Mastering these is critical for university exams as they form the backbone of pathfinding, game theory, and problem-solving modules. Candidates must grasp the distinction between blind searching and heuristic-guided searching to secure full marks.
Uninformed Search (BFS and DFS)
Uninformed search, or blind search, uses no information about the distance to the goal, relying solely on the structure of the search tree. BFS explores the graph layer by layer using a queue, while DFS explores deeper using a stack, each serving different memory and time complexity profiles.
- BFS is complete and optimal if step costs are uniform.
- BFS space complexity is O(b^d) where b is the branching factor.
- DFS is not optimal and can get stuck in infinite loops in infinite spaces.
- DFS uses O(bm) space where m is the maximum depth.
- BFS finds the shallowest goal first.
Informed Search (Greedy and A*)
Informed search utilizes domain-specific heuristics to guide the search towards the goal more efficiently. A* is the most significant algorithm here, combining path cost and heuristic estimate to guarantee optimality under specific conditions.
- Greedy Best-First search expands nodes with lowest h(n).
- A* formula: f(n) = g(n) + h(n).
- Admissibility: h(n) must never overestimate the cost to reach the goal.
- A* is both complete and optimal given an admissible heuristic.
- Consistency is a stronger condition than admissibility for A*.
Adversarial Search (Minimax)
Adversarial search applies to two-player zero-sum games where players have conflicting goals. The Minimax algorithm systematically explores the game tree to select moves that maximize the player's minimum possible gain, assuming the opponent plays optimally.
- MAX seeks the highest value, MIN seeks the lowest value.
- Minimax explores the full tree to find the optimal move.
- Alpha-Beta pruning reduces the number of nodes evaluated by cutting off branches.
- Alpha represents the best explored path for MAX; Beta for MIN.
- Minimax is used for deterministic, perfect-information games like Chess.
Formula Sheet
f(n) = g(n) + h(n)
Max(Min(n))
O(b^d) time complexity for BFS
Exam Tip
Always draw the state-space tree step-by-step; examiners award significant partial marks for demonstrating the correct expansion order even if the final result is miscalculated.
Common Mistakes
- Confusing the order of evaluation in BFS (FIFO) versus DFS (LIFO).
- Failing to check the admissibility condition of the heuristic when claiming A* optimality.
- Neglecting to prune branches correctly in Alpha-Beta pruning exercises.
More Revision Notes
Ready to test yourself?
Play topic-wise Search Algorithms questions in Aspirant Arcade — gamified MCQ practice.
Download Free