Optimization — Local Search, Simulated Annealing, CSP & Crossword Generation | Harvard CS50 AI Week 3
Week 3 covers three ways to write an optimization problem. Local search keeps a single state: hill climbing moves to a better neighbor and gets stuck at local optima, and simulated annealing accepts a worse move with probability e^(ΔE/T). Linear programming writes the problem as a linear cost function plus linear constraints and hands it to an existing solver. Constraint satisfaction problems shrink domains with node consistency and arc consistency (AC-3), then find a solution with backtracking search guided by the MRV, degree and least-constraining-value heuristics. Includes per-section time links, plus the approach, pseudocode, pitfalls and checks for the Crossword project (the reference implementation is folded at the end).