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
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
*Greedy best-first vs A: from start S, node A costs g = 5 with h(A) = 2, and node B costs g = 1 with h(B) = 3. Greedy looks only at h and expands A (2 < 3). A* compares f = g + h: f(A) = 7 and f(B) = 4, so it expands B** first — it accounts for the cost already paid, which is why A* finds the cheapest path when h is admissible.
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
MIN picks the smaller child (3 and 6); MAX picks the larger (6). Alpha-beta prunes branches that cannot change the result
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)).
Example
Alpha-beta pruning in a small tree: MAX at the root has two MIN children. The left MIN node's leaves are 3 and 5, so its value is 3 and α = 3 at the root. At the right MIN node, the first leaf is 2 — this MIN node will be at most 2, which is already worse for MAX than 3. Its remaining leaves are pruned without being evaluated, and the root's value is 3.
Exam tip
In minimax answers, back the values up level by level (MIN takes the smallest, MAX the largest) and circle the chosen move. For alpha-beta, mark each pruned branch with a cross and state the α and β values at that point.
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
Example
Crossover and mutation on bit strings: parents 11001|010 and 00110|111 with a crossover point after bit 5 produce children 11001111 and 00110010. Mutation then flips a random bit — the child 00110010 might become 00110110. Fitter children survive to the next generation.
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.
