On holiday in Romania
Russell and Norvig's most famous example: you're in Arad, in Romania, and your flight leaves tomorrow from Bucharest. Which roads should you take? A reflex agent can't answer — the right turn now depends on where it leads three cities later. You need a goal-based agent that searches through possible futures before acting.
Search is one of the oldest ideas in AI, and it's everywhere: sat-nav routes, puzzle solvers, robot motion planning, even the order a compiler tries optimisations. Today you'll write breadth-first search over the real map from the textbook.
Defining a search problem
A search problem has five parts: an initial state, the actions available in each state, a transition model (result) saying where an action leads, a goal test, and an action cost. Together they define a state space — a graph of states joined by actions. The algorithm never needs the whole graph in memory; it generates neighbours as it goes.
const routeProblem = (from, to) => ({
initial: from,
actions: (city) => Object.keys(ROADS[city]),
result: (city, next) => next,
cost: (city, next) => ROADS[city][next],
isGoal: (city) => city === to,
});Writing the problem as an object lets one search function solve routes, puzzles and anything else with the same shape — you'll reuse it all week.