AI Search

The two functions that define every search problem — how states, moves, and goals turn real problems into graphs a search algorithm can walk

• MoveGen and the State Space
• Depth-First Search (DFS)
• Breadth-First Search (BFS)
• Depth-First Iterative Deepening (DFID)

The smartest way to find the shortest path — explained so simply you'll never forget it

• A* Search Algorithm
• Weighted A* Search (WA*)
• SSS* Algorithm
• Traveling Salesperson Problem (TSP)
• Branch and Bound (BnB)
• Dijkstra's Algorithm
• SMA* — Simplified Memory-Bounded A*
• Which Algorithms Guarantee the Optimal Path?
• Best First Search

The constant-memory optimizer — climb the best local neighbor, stop when stuck. Why it fails and beam/search/variants fix it

• Hill Climbing and Local Search
• Solution Space Search and the SAT Landscape
• Stochastic Hill Climbing and Simulated Annealing
• Genetic Algorithms
• Genetic Algorithms for TSP — Representations and Crossover
• Ant Colony Optimization

How to read any BnB search tree from the papers — number of cities, refinement order, optimal tour, and why the numbers increase toward leaves

• Reading a TSP Branch-and-Bound Tree

When A* won't fit in memory — keep only the frontier, use relay layers, and stay optimal. The exam's favorite answer for 'large space + best admissible heuristic'

• SMGS and Frontier Search — Memory-Bounded Optimal Search
• Sequence Alignment as Graph Search
• Pruning OPEN — BFHS and Beam Stack Search
• The Monotone (Consistency) Condition

Two players, perfect information, one optimal strategy — the backup rule behind every board game AI. Asked in every exam paper

• Minimax — Game Tree Search
• Alpha-Beta Pruning
• Game Strategies and the Best Strategy
• Alpha-Beta Optimal Leaf Assignment
• Forcing the Minimax Value — One-Leaf Tweaks
• Game Evaluation Functions

The classic planning domain — operators with preconditions, add and delete lists. 'Applicable vs relevant actions' is an exam staple

• STRIPS and the Blocks World
• Goal Stack Planning and the Sussman Anomaly
• Plan-Space Planning and Partial-Order Planning (POP)

When one goal splits into many mandatory subgoals — A* grows up, leaves path-land, and starts solving subtrees. Asked in every paper

• AND-OR Trees and the AO* Algorithm
• Graphplan and Mutual Exclusion
• Action Ordering and GraphPlan Properties
• GraphPlan Mid-Flight Layer Reasoning
• Means-Ends Analysis and the General Problem Solver
• Goal Trees and Deduction in Logic

How expert systems match thousands of rules efficiently — alpha nets, beta nets, timestamps, and why specificity beats recency (or vice versa)

• Rete Algorithm — Conflict Sets and Resolution

The CSP lookahead strategy that prunes after every assignment — trace the exact order examiners expect

• Forward Checking for CSPs
• Waltz Line Labeling
• CSP Relations and Arc/Path Consistency