Concepts

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

The impetuous search — dive deep, backtrack late. Linear space but no shortest-path guarantee

The conservative search — sweep level by level. Guaranteed shortest path, but Open explodes exponentially

The best of both worlds — BFS's shortest-path guarantee at DFS's linear memory cost, for only ~11% overhead

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

A* with inflated heuristics — faster but suboptimal, with bounded error

Best-first search for game trees — explores fewer nodes than alpha-beta by being smarter about which branches to pursue

The most famous NP-hard optimization problem — visit every city exactly once at minimum cost

The exact method that prunes impossible branches — guaranteed optimal, exponential worst case but fast in practice

The classic shortest-path algorithm — Branch & Bound made elegant. A* with zero intuition, and still guaranteed optimal

A* that fits in whatever memory you have — forgets the worst leaf, remembers the best forgotten path

The multi-select question that reappears in nearly every paper — one table to answer them all

The pure heuristic search — follow the gradient downhill, no cost awareness. The precursor to A* and the foil to Dijkstra

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

Stop searching states, start searching solutions — synthesis vs perturbation, the SAT landscape, and why ridge edges trap hill climbers

Accept bad moves on purpose — the sigmoid rule, the temperature dial, and the metallurgy metaphor that escapes local optima

Evolve a population of solutions — roulette selection, crossover, mutation, and why losing diversity kills the search

Why naive crossover breaks tours — cycle crossover, PMX, order crossover, adjacency encoding, and the ordinal trick that makes any cut safe

Simple ants, collective intelligence — pheromone trails solve TSP without any ant knowing the tour exists

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

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'

Aligning DNA strings is shortest-path search on a grid — the problem whose Closed list grows so fat it motivated frontier search

Frontier search attacked Closed; this page attacks Open — upper bounds, breadth-first heuristic search, and the beam stack that can still backtrack

The one inequality that lets A* never reopen a closed node — and the two consequences every exam trace relies on

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

Minimax's answer without reading every leaf — prune branches that provably can't matter. Asked in every exam paper

What a 'strategy' really means in a game tree — and how to list the horizon nodes that make up MAX's optimal plan

The inverted exam question — assign values to leaves to MAXIMIZE pruning. Master the α/β window trick behind 2026 papers

Change ONE horizon eval to force the root to a target value — the inverse problem from 23T1 papers, solved with backup arithmetic

When the game tree is too big to search to the end — cut off at k-ply, score the board statically, and back up as if it were terminal

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

Linear planning with a stack of goals — simple, systematic, and famously broken by one tiny problem

Search over partial plans, not states — causal links, threats, promotion/demotion, and the elegant answer to the Sussman anomaly

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

Build the space of all possible plans as a layered graph, then hunt mutex pairs — the technique that jumped planning from 15 to 200 steps

When does order matter? When do mutexes persist? The theoretical edge cases that become multiple-choice traps

Given layers k and k+1 mid-planning-graph — can layer k be a state? Which actions apply next? Why are two facts (non-)mutex? The 25T3 question family

Reason like a human planner — find the biggest difference, pick the operator that kills it, recurse on preconditions. Newell & Simon's GPS

Proof search is AND-OR search — modus ponens, forward vs backward chaining, unification with variables, and why AO* can prove theorems

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

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

Label every edge as convex, concave or arrow — the CSP that proves a 2D drawing can (or cannot) depict a real 3D trihedral object

From math definitions to pruning power — compute R_AC from mod constraints, then enforce arc and path consistency like the papers demand