Problem Solving and Search (part 2: 2.5–2.8)
Open in the Padhaiko app2.5 Informed Search: Best first search, greedy search, A* algorithm
Informed (heuristic) search uses problem-specific knowledge beyond the definition of the problem itself—in the form of an evaluation function and a heuristic function —to find solutions much more efficiently than blind search.
Heuristic and Best-First Search
- Heuristic function : Estimated cost of the cheapest path from the state at node to a goal state (with if is a goal). Example: straight-line Euclidean distance to Bucharest in route finding, or Manhattan distance in the 8-puzzle.
- Best-first search: An instance of general tree/graph search in which nodes in the frontier are ordered by an evaluation function (expanding the node with the lowest first via a priority queue).
Greedy Best-First Search
- Evaluation function: (expands the node that appears closest to the goal).
- Properties:
- Fast in practice, guided straight toward the goal.
- Not optimal: ignores the cost already spent to reach , so it can commit to a misleading short-looking path that ends up longer overall.
- Not complete in tree search (can loop between two nodes); complete in finite spaces with graph search (explored set).
- Worst-case time and space: , though a good heuristic dramatically reduces this.
Search Algorithm
combines the cost spent so far with the estimated remaining cost:
where is the exact path cost from the start node to , and is the estimated cost from to the goal.
Admissibility, Consistency, and Optimality of A*
- Admissibility: A heuristic is admissible if it never overestimates the true minimum cost to reach a goal:
If is admissible, tree-search is optimal.
- Consistency (Monotonicity): A heuristic is consistent if for every node and every successor generated by action ,
Every consistent heuristic is admissible (by induction along any path). If is consistent, graph-search is optimal, and is non-decreasing along any path.
| Aspect | Greedy Best-First Search | A* Search |
|---|---|---|
| Evaluation function | ||
| Uses past cost ? | No | Yes |
| Completeness | Incomplete in tree search (complete in finite graph search) | Complete (if branching finite and step costs ) |
| Optimality | Not optimal | Optimal (admissible for tree; consistent for graph) |
| Heuristic accuracy | Guides fast, easily misled | Optimally efficient (no other optimal algorithm expands fewer nodes) |
2.6 Adversarial search: Minimax algorithm, alpha-beta pruning
In adversarial search (two-player, deterministic, turn-taking, zero-sum games such as chess or tic-tac-toe), the agent cannot simply plan a path to a goal because an opponent (MIN) actively works against the agent (MAX).
Formal Game Elements
A game is defined by: initial state , PLAYER(s), ACTIONS(s), RESULT(s, a), TERMINAL-TEST(s), and UTILITY(s, p) (assigning or numeric scores at terminal states).
Minimax Algorithm
MAX chooses the move maximizing the backed-up value, while MIN chooses the move minimizing it:
- Properties: Complete (if tree finite), optimal against an infallible opponent, time complexity , space complexity (DFS traversal).
Alpha-Beta () Pruning
Because is too slow for real games (in chess, , ), alpha-beta pruning computes the exact same minimax value without exploring branches that cannot possibly affect the final decision.
Alpha and Beta Bounds
- (alpha): the value of the best (highest-value) choice found so far along the path for MAX (initialized to ).
- (beta): the value of the best (lowest-value) choice found so far along the path for MIN (initialized to ).
Pruning rule: Update at MAX nodes and at MIN nodes. Whenever (or equivalently at a MAX node, or at a MIN node), prune the remaining children of that node immediately.
function ALPHA-BETA-SEARCH(state):
v = MAX-VALUE(state, -infinity, +infinity)
return action with value v
function MAX-VALUE(state, alpha, beta):
if TERMINAL-TEST(state): return UTILITY(state)
v = -infinity
for each a in ACTIONS(state):
v = max(v, MIN-VALUE(RESULT(state, a), alpha, beta))
if v >= beta: return v // beta cutoff
alpha = max(alpha, v)
return v
function MIN-VALUE(state, alpha, beta):
if TERMINAL-TEST(state): return UTILITY(state)
v = +infinity
for each a in ACTIONS(state):
v = min(v, MAX-VALUE(RESULT(state, a), alpha, beta))
if v <= alpha: return v // alpha cutoff
beta = min(beta, v)
return v- Move ordering matters: With worst move ordering, no pruning occurs (). With ideal move ordering (best moves examined first), time complexity drops from to —effectively doubling the searchable depth in the same time!
2.7 Local search and optimization: Hill climbing, simulated annealing
When only the final state matters and the path to reach it is irrelevant (e.g., 8-queens placement, VLSI chip layout, timetable scheduling), local search operates on a single current state (or small set) and moves to neighbouring states using very little memory ().
Hill Climbing Search
Hill climbing (greedy local search) continually moves to a neighbour with a higher objective value (or lower cost) until no neighbour improves on the current state.
| Concept | Explanation |
|---|---|
| Steepest-ascent hill climbing | Evaluates all neighbours and picks the best one; stops if none is better |
| Stochastic hill climbing | Picks at random among uphill moves (probability can depend on steepness) |
| Random-restart hill climbing | Runs hill climbing repeatedly from random initial states until a goal is found |
| Local maxima | Peaks lower than the global maximum where all neighbours go downhill |
| Ridges | Narrow sequences of local maxima difficult to traverse via axis-aligned single steps |
| Plateaux | Flat regions (shoulder or flat local maximum) where all neighbours have equal value |
Simulated Annealing
Inspired by metal annealing (heating then slowly cooling to reach a low-energy crystal), simulated annealing escapes local maxima by allowing occasional downhill (worse) moves with a probability that shrinks as temperature decreases.
Simulated Annealing Acceptance Rule
At step , pick a random neighbour of the current state , and compute (for maximization):
- If (better state): always accept the move ().
- If (worse state): accept with probability
where is the current temperature from a cooling schedule (if minimizing cost, and worse moves have , accepted with ).
- When is large, , allowing wide exploration; as , , turning the search into pure hill climbing. If cools slowly enough, simulated annealing finds the global optimum with probability approaching .
2.8 Evolutionary optimization: Genetic algorithm
A Genetic Algorithm (GA) is a stochastic beam-search variant inspired by biological evolution. Instead of keeping one state, it evolves a population of candidate states (individuals / chromosomes).
Genetic Algorithm Operators
- Encoding (Representation): Each candidate solution is encoded as a string (often binary bits or integer permutation), called a chromosome.
- Fitness function: Scores how good each individual is; higher fitness means higher chance of surviving and reproducing.
- Selection: Chooses parents from the current population in proportion to fitness (e.g., roulette-wheel selection, where , or tournament selection).
- Crossover (Recombination): Combines two parent chromosomes at one or more random crossover points to produce offspring sharing traits from both parents.
- Mutation: Flips a random gene/bit with a small mutation probability to maintain population diversity and prevent premature convergence to local optima.
Initialize population P of k random chromosomes
Repeat until stopping criterion (target fitness or max generations):
Evaluate fitness f(x) for every individual x in P
New population P_new = empty
Repeat k times (or k/2 pairs):
Select two parents x, y from P based on fitness
With crossover rate p_c: recombine x, y at crossover point -> child(ren)
With small mutation rate p_m: randomly alter gene(s) in child
Add child to P_new
P = P_new
Return fittest individual found| Aspect | Simulated Annealing | Genetic Algorithm |
|---|---|---|
| States tracked | Single current state | Population of states |
| Key operators | Random neighbour + temperature | Selection, crossover, mutation |
| Exploration mechanism | Uphill/downhill jumps controlled by | Recombination of building blocks + mutation |
| Memory | for individuals |
Worked Out Examples
2.4
Find the optimal path from to using Graph (). Directed edge costs are: , , , , , , . Heuristic values are .
Start at : Frontier . Expand :
- : , .
- : , .
Frontier .
Expand lowest : ():
- via : , .
Frontier .
Tie at (expand before , or —check first): Expanding () generates:
- via : (cheaper than , but was already expanded? Note: let us check consistency at : ; at : is FALSE! is admissible but not consistent!).
- via : , .
- via : , .
Because is not consistent (), with reopening updates to !
Expand (): updates to , . Expand (): reaches with , . Expand (): all remaining frontier nodes have , so is optimal!
Optimal path: with minimum total cost .
2.5
Evaluate a 2-ply game tree where the root is MAX () with three MIN children (). Leaf values under are ; under are ; under are . Trace left-to-right alpha-beta pruning and state which leaves are pruned.
Explore MIN node with :
- Leaf : .
- Leaf : .
- Leaf : .
returns to MAX root , so .
Explore MIN node with :
- First leaf is : , so .
- Now : alpha cutoff! MIN node can return at most , which MAX root will never pick over . Leaves and under are pruned. returns ; remains .
Explore MIN node with :
- First leaf : (, continue).
- Second leaf : (, continue).
- Third leaf : .
returns . Root MAX chooses (move to ).
Root minimax value (MAX chooses ). Leaves and under MIN node are pruned by an alpha cutoff.
2.6
In a maximization problem using simulated annealing, the current state has value and a randomly chosen neighbour has value . Calculate the acceptance probability of moving to this worse neighbour when temperature is (a) and (b) .
Compute the change in value:
At high temperature :
At low temperature :
Acceptance probability is () at , dropping to () at .
Exercises
Exercise: Informed Search, Adversarial Search, and Local Optimization
Define admissible and consistent heuristics. Prove briefly why graph search can be suboptimal if is admissible but not consistent, or explain how consistency guarantees optimality.
Definitions: is admissible if for all (never overestimates true cost to goal). is consistent if for every edge and .
Why consistency guarantees graph-search optimality: Along any path, , so never decreases. Thus, whenever pops a node for expansion, the optimal path to has already been found, so no suboptimal goal can ever be popped before the optimal goal.
An admissible heuristic never overestimates ; a consistent heuristic satisfies the triangle inequality , making non-decreasing along paths and ensuring the first expansion of any node (including the goal) is via its optimal path.
Trace search from to on a graph with edges , , , , , and consistent heuristic . Find the optimal path and total cost.
Expand (): Frontier .
Expand ():
- via : , update to .
- via : .
Frontier .
Expand ():
- via : , update to .
Expand (): goal reached!
Optimal path: with total cost .
In a 2-ply game tree, root MAX () has two MIN children and . Under are leaves ; under are leaves . Apply alpha-beta pruning left-to-right, find the root minimax value, and state whether any leaf is pruned.
Node (MIN) with : evaluates () and (), returning . Root MAX updates .
Node (MIN) with : evaluates first leaf . Now , triggering an alpha cutoff. Leaf is pruned. returns .
Root : .
Root minimax value (MAX picks ). Leaf under is pruned.
Explain local maxima, ridges, and plateaux in hill climbing. In simulated annealing, if a worse move reduces objective value by units at temperature , what is its acceptance probability?
Hill-climbing traps: A local maximum is a peak better than all immediate neighbours but worse than the global optimum. A ridge is a rising crest not aligned with single-step moves, forcing zig-zagging or stalling. A plateau is a flat region where neighbours have equal value, leaving no uphill direction.
Simulated annealing calculation: Here and :
Local maxima, ridges, and plateaux trap pure hill climbing because no single move improves the score. With and , simulated annealing accepts the worse move with probability .
Describe the steps and operators of a Genetic Algorithm. If four chromosomes have fitness values , compute the roulette-wheel selection probability of the fittest and least-fit chromosome.
GA operators: Representation (chromosome encoding), fitness evaluation, selection (favouring fitter parents), crossover (recombining parent substrings), and mutation (random bit/gene flip to preserve diversity).
Selection probabilities: Total fitness .
- Fittest chromosome (): ().
- Least-fit chromosome (): ().
GA cycles through fitness evaluation, selection, crossover, and mutation. With total fitness , the fittest chromosome has selection probability () and the least-fit has ().