Unit 2: Advanced search techniques
Artificial Intelligence notes · PTU syllabus (UGCC2521)
On this page
Unit summary
Search is at the heart of AI problem solving. This unit covers uninformed search (DFS, BFS, iterative deepening), informed (heuristic) search (best-first, A, AO), adversarial search for games (Minimax, alpha-beta pruning), constraint satisfaction problems with backtracking, and genetic algorithms.
After this unit you can
- Compare uninformed search strategies
- Apply best-first, A* and AO* using heuristics
- Use Minimax and alpha-beta pruning for game playing
- Solve constraint satisfaction problems and explain genetic algorithms
PTU syllabus topics
- Uninformed search (DFS, BFS, iterative deepening)
- informed search (Best First Search, A*, AO*)
- adversarial search (Minimax, Alpha-Beta pruning)
- constraint satisfaction problems and backtracking search
- evolutionary search techniques and genetic algorithms
Uninformed
BFS, DFS, iterative deepening
Informed
Best-first, A*, AO*
Adversarial
Minimax, alpha-beta pruning
Constraint satisfaction
Backtracking
Evolutionary
Genetic algorithms
Topic 1
Uninformed (blind) search
BFS
Level by level using a queue
Yes; optimal for equal step costs
DFS
Deepest node first using a stack
No (may loop); not optimal
Iterative deepening
DFS with depth limits 0, 1, 2 …
Yes; optimal for equal step costs
Iterative deepening combines BFS's completeness with DFS's low memory use.
Topic 2
Informed (heuristic) search
A heuristic h(n) estimates the cost from node n to the goal.
- Greedy best-first search expands the node with the smallest h(n) — fast but not optimal.
- *A search expands the node with the smallest f(n) = g(n) + h(n)*, where g(n) is the cost so far. A is optimal if h is admissible (never overestimates).
- *AO search works on AND-OR graphs**, where solving a node may require solving all of several subproblems (AND) or any one of them (OR).
Example
In route finding, h(n) = straight-line distance to the destination is admissible because the road distance is never shorter.
Topic 3
Adversarial search: Minimax and alpha-beta
In two-player games, Minimax assumes both players play optimally: MAX chooses the highest-valued move and MIN the lowest, with values backed up from the leaves of the game tree. Alpha-beta pruning skips branches that cannot affect the final decision. α is the best value MAX can guarantee; β is the best for MIN; prune when α ≥ β. With good move ordering it halves the effective depth cost, from O(bᵈ) to about O(b^(d/2)).
Topic 4
Constraint satisfaction problems
A CSP has variables, domains of possible values and constraints between variables. Examples: map colouring, Sudoku, N-Queens and timetabling. Backtracking search assigns values one variable at a time and backs up when a constraint is violated. Improvements: minimum remaining values (choose the most constrained variable), forward checking and constraint propagation (arc consistency).
Topic 5
Evolutionary search: genetic algorithms
- 1. Initial population: Random candidate solutions
- 2. Fitness evaluation:
- 3. Selection: Fitter individuals chosen
- 4. Crossover: Combine parents
- 5. Mutation: Small random changes
Genetic algorithms are used for optimisation problems where the search space is huge — scheduling, design and feature selection.
Key terms
- Heuristic
- An estimate of the cost to reach the goal
- Admissible heuristic
- A heuristic that never overestimates
- Minimax
- A game-playing algorithm assuming optimal opponents
- Alpha-beta pruning
- Skipping branches that cannot change the decision
- Constraint satisfaction problem
- Finding values that satisfy all constraints
Quick revision
- BFS queue, DFS stack, IDDFS = depth-limited DFS repeated.
- A*: f = g + h; optimal if h is admissible.
- Minimax backs up values; alpha-beta prunes when α ≥ β.
- CSP: variables, domains, constraints; backtracking + forward checking.
- GA: selection, crossover, mutation.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Differentiate between informed and uninformed search.
- Q2.What is an admissible heuristic?
- Q3.Write the evaluation function of A*.
- Q4.What is alpha-beta pruning?
- Q5.Define a constraint satisfaction problem.
- Q6.Name the operators of a genetic algorithm.
Long-answer questions
- Q1.Compare BFS, DFS and iterative deepening search.
- Q2.Explain A* search with an example and state when it is optimal.
- Q3.Explain the Minimax algorithm and alpha-beta pruning with a game tree.
- Q4.Solve the 4-Queens problem as a CSP using backtracking.
Stuck on this unit?
Message SBS on WhatsApp for help with Artificial Intelligence, or to ask about studying BCA at Synetic.