--- title: Uninformed Search module: Search moduleNumber: 2 lessonNumber: 1 order: 201 summary: > A goal-based agent that cannot see which action is best turns the problem into a state space — an initial state, a set of actions, a transition model, a goal test, and a path cost — and searches for a sequence of actions reaching the goal. We build the state-space formulation on the 8-puzzle and route-finding, give the one TREE-SEARCH / GRAPH-SEARCH skeleton every algorithm specializes, and measure strategies by completeness, optimality, and complexity. This lesson develops the first two frontier disciplines — breadth-first and uniform-cost search; the rest follow in the next lesson. topics: [Search] sources: - book: AIMA ref: "Ch. 3 — Solving Problems by Searching; §3.1 Problem-Solving Agents; §3.2 Example Problems" - book: AIMA ref: "§3.3 Searching for Solutions; §3.4 Uninformed Search Strategies" --- A reflex agent maps the current percept straight to an action, and for many environments that is not enough: no single action reaches the goal, and the agent has to string together a whole _sequence_ of them, choosing the first only after reasoning about where the later ones lead. An agent standing in Arad with a non-refundable ticket out of Bucharest gains nothing from any one move — every road out of Arad leads to a town that is not Bucharest — yet with a map it can plan a route, examining future actions that eventually reach a state of known value before committing to the first one.[^aima-solving] That is the whole idea of a **problem-solving agent**: adopt a goal, formulate the problem as a state space, _search_ for a solution offline, then execute it. This lesson does three things. It defines what a **problem** is — the five components any search algorithm takes as input. It gives the one search skeleton, `Tree-Search` and its repeated-state-safe cousin `Graph-Search`, that every strategy specializes. And it works through the first two **uninformed** strategies — breadth-first and uniform-cost search — which differ in precisely one design choice: the order in which the frontier hands back nodes. The remaining strategies (depth-first, iterative deepening, bidirectional) and the head-to-head comparison of all of them are the subject of the companion lesson, [Search Strategies Compared](/artificial-intelligence/search/search-strategies-compared). ## Formulating a problem Between goal and solution sits **problem formulation**: deciding which actions and states to consider. Consider the level of "turn the steering wheel one degree" and the agent never leaves the parking lot; consider driving from one town to the next and the problem becomes a graph of two dozen cities. Choosing the right level of _abstraction_ — dropping every detail irrelevant to reaching the goal — is what makes a real-world task tractable at all.[^aima-formulate] Formally, a problem has five components. > **Definition (Problem).** A **problem** is a tuple $(s_0, \text{Actions}, > \text{Result}, \text{Goal-Test}, c)$: an **initial state** $s_0$; a function > $\text{Actions}(s)$ giving the actions **applicable** in state $s$; a > **transition model** $\text{Result}(s, a)$ returning the state that results from > doing $a$ in $s$; a **goal test** deciding whether a state is a goal; and a > **step-cost** function $c(s, a, s')$, assumed nonnegative, whose sum along a path > is the **path cost**. The initial state, actions, and transition model together define the **state space** implicitly: the set of all states reachable from $s_0$ by any sequence of actions. The state space is a directed graph whose nodes are states and whose edges are actions; a **path** is a sequence of states connected by actions. A **solution** is a path from $s_0$ to a goal state, and an **optimal solution** is one of least path cost. Notice the state space is defined _implicitly_ — by the three functions, not by an enumerated list, and so it can be enormous or even infinite while the description stays small. $$ % caption: A problem is five components; the initial state, actions, and % transition model together generate the state-space graph implicitly, over which % the goal test and path cost define what counts as a solution. \begin{tikzpicture}[>=stealth, font=\footnotesize, comp/.style={draw, minimum width=26mm, minimum height=8mm, align=center, font=\scriptsize}, gen/.style={draw, draw=acc, text=acc, thick, minimum width=30mm, minimum height=9mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[comp] (s0) at (0,1.4) {initial state}; \node[comp] (act) at (0,0) {actions}; \node[comp] (res) at (0,-1.4) {transition model}; \node[gen] (ss) at (5.3,0) {state-space graph}; \node[comp] (gt) at (10.6,0.8) {goal test}; \node[comp] (pc) at (10.6,-0.8) {path cost}; \draw[->, acc, thick] (s0) -- (ss); \draw[->, acc, thick] (act) -- (ss); \draw[->, acc, thick] (res) -- (ss); \draw[->, black, thick] (ss) -- (gt); \draw[->, black, thick] (ss) -- (pc); \node[font=\scriptsize, text=black, anchor=north, align=center] at (5.3,-0.75) {generated\\implicitly}; \node[font=\scriptsize, text=black, anchor=west, align=left] at (11.9,0) {test the\\solution}; \end{tikzpicture} $$ ### Route-finding on a map The running example is route-finding in Romania. The agent is in Arad and must reach Bucharest. The abstraction is deliberate: a state is just _which city the agent is in_, ignoring the companions, the radio, the weather — everything irrelevant to finding a route. - **States**: the agent's current city, e.g. $\text{In}(\text{Arad})$. - **Initial state**: $\text{In}(\text{Arad})$. - **Actions**: from a city, drive to an adjacent city; $\text{Actions}(\text{In}(\text{Arad})) = \{\text{Go}(\text{Sibiu}), \text{Go}(\text{Timisoara}), \text{Go}(\text{Zerind})\}$. - **Transition model**: $\text{Result}(\text{In}(\text{Arad}), \text{Go}(\text{Zerind})) = \text{In}(\text{Zerind})$. - **Goal test**: is the state $\text{In}(\text{Bucharest})$? - **Step cost**: the road distance in kilometers; the path cost is the total distance. $$ % caption: A fragment of the Romania road map, the state-space graph for the % route-finding problem; nodes are cities and each edge carries its step cost in % kilometers. The path Arad-Sibiu-Rimnicu-Pitesti-Bucharest costs 418. \begin{tikzpicture}[>=stealth, font=\footnotesize, city/.style={draw, fill=black!4, minimum size=5mm, inner sep=1.5pt, font=\scriptsize}, goal/.style={draw, draw=acc, text=acc, thick, minimum size=5mm, inner sep=1.5pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[city] (ar) at (0,1.2) {Arad}; \node[city] (ze) at (0.6,3.0) {Zerind}; \node[city] (or) at (1.8,4.1) {Oradea}; \node[city] (ti) at (0.2,-0.9) {Timisoara}; \node[city] (si) at (3.4,2.1) {Sibiu}; \node[city] (fa) at (5.9,2.4) {Fagaras}; \node[city] (rv) at (4.4,0.7) {Rimnicu}; \node[city] (pi) at (6.6,0.2) {Pitesti}; \node[goal] (bu) at (8.9,0.7) {\texttt{Bucharest}}; \draw (ar) -- (ze) node[midway, left, font=\scriptsize] {75}; \draw (ze) -- (or) node[midway, left, font=\scriptsize] {71}; \draw (ar) -- (ti) node[midway, left, font=\scriptsize] {118}; \draw (ar) -- (si) node[midway, above, font=\scriptsize] {140}; \draw (or) -- (si) node[midway, right, font=\scriptsize] {151}; \draw (si) -- (fa) node[midway, above, font=\scriptsize] {99}; \draw (si) -- (rv) node[midway, left, font=\scriptsize] {80}; \draw (rv) -- (pi) node[midway, below, font=\scriptsize] {97}; \draw (fa) -- (bu) node[midway, above right, font=\scriptsize] {211}; \draw (pi) -- (bu) node[midway, below, font=\scriptsize] {101}; \end{tikzpicture} $$ ### The 8-puzzle Route-finding has an obvious geography; the point of a **toy problem** is that it strips that away and leaves a clean state space to test algorithms on. The **8-puzzle** is a $3 \times 3$ board with eight numbered tiles and one blank; a tile adjacent to the blank slides into it, and the object is to reach a specified goal configuration. - **States**: the location of each of the eight tiles and the blank in the nine squares. - **Initial state**: any configuration. - **Actions**: move the blank $\text{Left}$, $\text{Right}$, $\text{Up}$, or $\text{Down}$ (whichever are legal, given where the blank is). - **Transition model**: given a state and a move, return the board with the blank and the neighboring tile swapped. - **Goal test**: does the board match the goal configuration? - **Step cost**: each move costs $1$, so the path cost is the number of moves. $$ % caption: The 8-puzzle: sliding the blank one step at a time to turn the start % board (left) into the goal board (right). Each state names where all eight tiles % and the blank sit; a move swaps the blank with a neighbor. \begin{tikzpicture}[>=stealth, font=\footnotesize, tile/.style={draw, minimum size=7mm, inner sep=0pt, font=\small}, blank/.style={draw, fill=black!8, minimum size=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % start board \begin{scope} \node[tile] at (0,1.4) {7}; \node[tile] at (0.75,1.4) {2}; \node[tile] at (1.5,1.4) {4}; \node[tile] at (0,0.65) {5}; \node[blank] at (0.75,0.65) {}; \node[tile] at (1.5,0.65) {6}; \node[tile] at (0,-0.1) {8}; \node[tile] at (0.75,-0.1) {3}; \node[tile] at (1.5,-0.1) {1}; \node[font=\scriptsize, anchor=north] at (0.75,-0.55) {start state}; \end{scope} \draw[->, acc, very thick] (2.4,0.65) -- (4.2,0.65) node[midway, above, font=\scriptsize, text=black] {moves}; % goal board \begin{scope}[xshift=5.1cm] \node[blank] at (0,1.4) {}; \node[tile] at (0.75,1.4) {1}; \node[tile] at (1.5,1.4) {2}; \node[tile] at (0,0.65) {3}; \node[tile] at (0.75,0.65) {4}; \node[tile] at (1.5,0.65) {5}; \node[tile] at (0,-0.1) {6}; \node[tile] at (0.75,-0.1) {7}; \node[tile] at (1.5,-0.1) {8}; \node[font=\scriptsize, anchor=north] at (0.75,-0.55) {goal state}; \end{scope} \end{tikzpicture} $$ The 8-puzzle has $9!/2 = 181{,}440$ reachable states and is easily solved; the $15$-puzzle on a $4 \times 4$ board has about $1.3$ trillion, and the $24$-puzzle around $10^{25}$. This blow-up is why the abstraction matters, and why a good _search strategy_ matters more. ## Searching for solutions A solution is a sequence of actions, so a search algorithm builds a **search tree**: the root is the initial state, the branches are actions, and each node corresponds to a state reached by some action sequence. **Expanding** a node applies each legal action to its state, **generating** a new set of child nodes. The leaf nodes available for expansion at any moment — the boundary between what has been explored and what has not — form the **frontier**.[^aima-searching] The whole family of algorithms shares one skeleton. Initialize the frontier with the start node; then repeat: if the frontier is empty, fail; otherwise remove a leaf, test it for the goal, and if it is not a goal, expand it and add its children to the frontier. The strategies differ only in _which_ leaf gets removed. ```algorithm caption: $\textsc{Tree-Search}(problem)$ — the skeleton every strategy specializes initialize the frontier with the initial state of $problem$ loop do if the frontier is empty then return failure choose a leaf node and remove it from the frontier if the node contains a goal state then return the corresponding solution expand the node and add the resulting children to the frontier ``` There is a hazard in `Tree-Search`. On the Romania map the path Arad-Sibiu-Arad revisits Arad, and nothing stops it revisiting again: the search tree is _infinite_ even though the state space has only twenty states. Such **loopy paths** are a special case of **redundant paths** — more than one way to reach the same state — and because step costs are nonnegative, a looping or roundabout path to a state is never better than the direct one. There is no reason to keep it. The cure is to remember where the search has been. Augment the skeleton with an **explored set** (also called the _closed list_) holding every expanded state; when a newly generated node's state is already in the explored set or on the frontier, discard it. The result is `Graph-Search`. ```algorithm caption: $\textsc{Graph-Search}(problem)$ — Tree-Search plus an explored set initialize the frontier with the initial state of $problem$ initialize the explored set to be empty loop do if the frontier is empty then return failure choose a leaf node and remove it from the frontier if the node contains a goal state then return the corresponding solution add the node's state to the explored set for each resulting child of expanding the node do if the child's state is not in the explored set or the frontier then add the child to the frontier ``` `Graph-Search` keeps at most one copy of each state, so it grows a tree directly on the state-space graph. It also has a clean geometric property: the frontier **separates** the explored region from the unexplored one, so every path from the initial state to an unexplored state must pass through a frontier node. The search sweeps outward through the state space, one state at a time. $$ % caption: The separation property on a grid: the frontier (open nodes) always % separates the explored region (filled) from the unexplored one, so the search % sweeps outward one ring at a time. \begin{tikzpicture}[>=stealth, font=\footnotesize, ex/.style={circle, draw, fill=black!70, minimum size=3mm, inner sep=0pt}, fr/.style={circle, draw, thick, fill=white, minimum size=3mm, inner sep=0pt}, un/.style={circle, draw, black, fill=black!8, minimum size=3mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \x in {0,1,2,3,4} \foreach \y in {0,1,2,3,4} { \node[un] (n\x\y) at (\x*0.85, \y*0.85) {}; } % explored core \foreach \c in {22,12,32,21,23} { \node[ex] at (n\c) {}; } % frontier ring \foreach \c in {02,42,20,24,11,13,31,33} { \node[fr] at (n\c) {}; } \node[font=\footnotesize, anchor=north, text=black] at (1.7,-0.65) {\texttt{explored} = dark, \texttt{frontier} = open, \texttt{unexplored} = light}; \end{tikzpicture} $$ ### The node data structure It pays to keep _nodes_ and _states_ distinct. A **state** is a configuration of the world; a **node** is a bookkeeping record on a particular search path. Two different nodes can hold the same state if it was reached two ways. Each node $n$ carries four fields: - $n.\text{State}$ — the state it corresponds to; - $n.\text{Parent}$ — the node that generated it; - $n.\text{Action}$ — the action applied to the parent to produce it; - $n.\text{Path-Cost}$ — the cost $g(n)$ of the path from the root to $n$. The parent pointers thread the nodes into a tree and let the solution be read off by walking from a goal node back to the root. A child's cost extends its parent's: $g(\text{child}) = g(n) + c(n.\text{State}, a, \text{child}.\text{State})$. The frontier holds nodes waiting to be expanded, and the strategy is entirely a choice of _which node comes out next_. That choice is the frontier's queue discipline, and it is the one axis along which every uninformed strategy varies: - a **FIFO queue** pops the oldest node — the shallowest — giving breadth-first search; - a **priority queue** pops the node of lowest $g(n)$, giving uniform-cost search; - a **LIFO queue** (a stack) pops the newest node — the deepest — giving depth-first search. Three queue types, three strategies — the through-line of this lesson and the next. ## Measuring search Before choosing among strategies, fix how they are judged. Four criteria matter. > **Definition (Evaluating a strategy).** A search strategy is judged by: > **completeness** — is it guaranteed to find a solution when one exists?; > **optimality** — does it find a least-cost solution?; **time complexity** — how > many nodes does it generate?; and **space complexity** — how many nodes does it > hold in memory at once? In classical algorithms, complexity is measured against the graph size $|V| + |E|$. In AI the graph is usually implicit and often infinite, so complexity is expressed in three quantities of the problem itself: - $b$, the **branching factor** — the maximum number of successors of any node; - $d$, the **depth** of the shallowest goal (the fewest steps to a solution); - $m$, the **maximum depth** of any path in the state space (possibly infinite). Time is counted as nodes generated, space as the peak number of nodes stored. With these three numbers the strategies can be compared directly, without reference to any particular map or puzzle. ## Breadth-first search **Breadth-first search** (BFS) expands the root, then all its successors, then all _their_ successors — every node at one depth before any at the next. It is `Graph-Search` with a **FIFO queue** for the frontier: new (deeper) nodes go to the back, so shallow nodes come out first. One tweak pays off — apply the goal test when a node is _generated_, not when it is expanded, so the search can stop the instant it makes the goal rather than a full level later. ```algorithm caption: $\textsc{Breadth-First-Search}(problem)$ — expand the shallowest node first $node \gets$ a node with $\textsc{State} = problem.\textsc{Initial-State}$, $\textsc{Path-Cost} = 0$ if $problem.\textsc{Goal-Test}(node.\textsc{State})$ then return $\textsc{Solution}(node)$ $frontier \gets$ a FIFO queue with $node$ as the only element $explored \gets$ an empty set loop do if $frontier$ is empty then return failure $node \gets \textsc{Pop}(frontier)$ // shallowest node add $node.\textsc{State}$ to $explored$ for each $action$ in $problem.\textsc{Actions}(node.\textsc{State})$ do $child \gets \textsc{Child-Node}(problem, node, action)$ if $child.\textsc{State}$ is not in $explored$ or $frontier$ then if $problem.\textsc{Goal-Test}(child.\textsc{State})$ then return $\textsc{Solution}(child)$ $frontier \gets \textsc{Insert}(child, frontier)$ ``` $$ % caption: Breadth-first search on a binary tree expands level by level: the root, % then both depth-1 nodes, then all four depth-2 nodes. The marked node is the one % expanded next; the FIFO frontier always hands back the shallowest. \begin{tikzpicture}[>=stealth, font=\footnotesize, nd/.style={circle, draw, minimum size=5mm, inner sep=0pt, font=\scriptsize}, seen/.style={circle, draw, fill=black!12, minimum size=5mm, inner sep=0pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \foreach \s/\dx in {0/0, 1/3.7, 2/7.4} { \begin{scope}[xshift=\dx cm] \node[nd] (a) at (0.9,1.6) {A}; \node[nd] (b) at (0.3,0.7) {B}; \node[nd] (c) at (1.5,0.7) {C}; \node[nd] (d) at (0,-0.2) {D}; \node[nd] (e) at (0.6,-0.2){E}; \node[nd] (f) at (1.2,-0.2){F}; \node[nd] (g) at (1.8,-0.2){G}; \draw (a)--(b); \draw (a)--(c); \draw (b)--(d); \draw (b)--(e); \draw (c)--(f); \draw (c)--(g); \end{scope} } % stage 0: expand A \node[fill=acc, circle, minimum size=5mm, inner sep=0pt, text=white, font=\scriptsize] at (0.9,1.6) {A}; % stage 1: A seen, expand B \node[seen] at (4.6,1.6) {A}; \node[fill=acc, circle, minimum size=5mm, inner sep=0pt, text=white, font=\scriptsize] at (4.0,0.7) {B}; % stage 2: A,B seen, expand C \node[seen] at (8.3,1.6) {A}; \node[seen] at (7.7,0.7) {B}; \node[fill=acc, circle, minimum size=5mm, inner sep=0pt, text=white, font=\scriptsize] at (8.9,0.7) {C}; \end{tikzpicture} $$ How does BFS score? It is **complete** whenever $b$ is finite: a goal at depth $d$ is found after all shallower nodes are generated. It is **optimal** only when the path cost is a nondecreasing function of depth — most commonly when every step costs the same — since it returns the _shallowest_ goal, which need not be the cheapest. The cost is where the news turns bad. A uniform tree generates $b + b^2 + \cdots + b^d = O(b^d)$ nodes, and every generated node stays in memory, so both time and space are $O(b^d)$. Space is the binding constraint. | $d$ | Nodes | Time $(10^6/\text{sec})$ | Memory $(1\text{ KB}/\text{node})$ | | --- | --- | --- | --- | | $6$ | $10^{6}$ | $1.1$ seconds | $1$ gigabyte | | $8$ | $10^{8}$ | $2$ minutes | $103$ gigabytes | | $10$ | $10^{10}$ | $3$ hours | $10$ terabytes | | $12$ | $10^{12}$ | $13$ days | $1$ petabyte | | $14$ | $10^{14}$ | $3.5$ years | $99$ petabytes | At $b = 10$ the memory bill dwarfs the time bill: a depth-$12$ solution takes thirteen days but a petabyte of storage no machine has. Exponential-complexity problems cannot be solved by uninformed search for any but the smallest instances, and among the reasons, the frontier's appetite for memory is the worst. #### A traced run Trace BFS from Arad on the map fragment above, goal Bucharest. The FIFO frontier starts as `[Arad]`. Popping Arad expands it to Zerind, Timisoara, and Sibiu, which join the back of the queue. Since none is the goal (the goal test fires at generation), the queue is now `[Zerind, Timisoara, Sibiu]`. The table below records each expansion, the newly generated states, and the resulting frontier; a state already explored or already queued is dropped rather than re-added. | Step | Expand | Generates (new) | Frontier after | | --- | --- | --- | --- | | $1$ | Arad | Zerind, Timisoara, Sibiu | Zerind, Timisoara, Sibiu | | $2$ | Zerind | Oradea | Timisoara, Sibiu, Oradea | | $3$ | Timisoara | Lugoj | Sibiu, Oradea, Lugoj | | $4$ | Sibiu | Fagaras, Rimnicu | Oradea, Lugoj, Fagaras, Rimnicu | | $5$ | Oradea | (all already seen) | Lugoj, Fagaras, Rimnicu | | $6$ | Lugoj | Mehadia | Fagaras, Rimnicu, Mehadia | | $7$ | Fagaras | **Bucharest** (goal) | — return | BFS returns Arad-Sibiu-Fagaras-Bucharest, a path of $140 + 99 + 211 = 450$ km. This is the _shallowest_ goal — three edges — but not the cheapest: the four-edge route Arad-Sibiu-Rimnicu-Pitesti-Bucharest costs only $418$. BFS finds the goal at generation in step $7$, one level before it would have been expanded, exactly the early-termination tweak paying off. Notice too that when Oradea is expanded in step $5$ every successor (Zerind, Sibiu) is already on the frontier or explored, so the explored set does its job and no duplicate is queued. ## Uniform-cost search BFS is optimal only when steps cost the same, because it orders the frontier by _depth_. **Uniform-cost search** orders it by _cost_ instead: expand the node $n$ of lowest path cost $g(n)$, using a **priority queue** keyed on $g$. This is exactly Dijkstra's algorithm cast as a search over an implicit graph.[^aima-ucs] Two details separate it from BFS. The goal test is applied when a node is _selected_ for expansion, not when generated — because the first goal node generated may sit on a costly path while a cheaper route to the goal is still on the frontier. And when a shorter path to a frontier state turns up, the frontier node is replaced. ```algorithm caption: $\textsc{Uniform-Cost-Search}(problem)$ — expand the lowest-cost node first $node \gets$ a node with $\textsc{State} = problem.\textsc{Initial-State}$, $\textsc{Path-Cost} = 0$ $frontier \gets$ a priority queue ordered by $\textsc{Path-Cost}$, with $node$ as the only element $explored \gets$ an empty set loop do if $frontier$ is empty then return failure $node \gets \textsc{Pop}(frontier)$ // lowest $g(n)$ if $problem.\textsc{Goal-Test}(node.\textsc{State})$ then return $\textsc{Solution}(node)$ add $node.\textsc{State}$ to $explored$ for each $action$ in $problem.\textsc{Actions}(node.\textsc{State})$ do $child \gets \textsc{Child-Node}(problem, node, action)$ if $child.\textsc{State}$ is not in $explored$ or $frontier$ then $frontier \gets \textsc{Insert}(child, frontier)$ else if $child.\textsc{State}$ is in $frontier$ with higher $\textsc{Path-Cost}$ then replace that frontier node with $child$ ``` Uniform-cost search is **optimal in general**. Whenever it selects a node $n$, the cheapest path to $n$ has already been found: any cheaper route would run through some other frontier node $n'$ of lower $g$, which would have been selected first. Because step costs are nonnegative, paths only grow as they extend, so nodes are expanded in order of optimal path cost, and the first goal selected is the least-cost goal. Consider Sibiu to Bucharest. Sibiu's successors are Rimnicu ($80$) and Fagaras ($99$). The cheaper, Rimnicu, is expanded first, adding Pitesti at $80 + 97 = 177$. Now Fagaras is cheapest, so it expands, adding Bucharest at $99 + 211 = 310$. A goal has been _generated_ — but uniform-cost search does not stop, because Pitesti at $177$ is cheaper than that goal. Expanding Pitesti reaches Bucharest at $80 + 97 + 101 = 278$; the better path replaces the old one, and only when Bucharest at $278$ is _selected_ is the solution returned. $$ % caption: Uniform-cost search from Sibiu to Bucharest. The first Bucharest node % generated (via Fagaras, cost 310) is not returned; expansion continues until the % cheaper path through Pitesti (cost 278) is selected. \begin{tikzpicture}[>=stealth, font=\footnotesize, city/.style={draw, fill=black!4, minimum size=5mm, inner sep=1.5pt, font=\scriptsize}, goal/.style={draw, draw=acc, text=acc, thick, minimum size=5mm, inner sep=1.5pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[city] (si) at (0,2.0) {Sibiu}; \node[city] (fa) at (3.2,2.0) {Fagaras}; \node[city] (rv) at (1.1,0.9) {Rimnicu}; \node[city] (pi) at (3.0,0.2) {Pitesti}; \node[goal] (bu) at (6.0,0.9) {\texttt{Bucharest}}; \draw (si) -- (fa) node[midway, above, font=\scriptsize] {99}; \draw (si) -- (rv) node[midway, left, font=\scriptsize] {80}; \draw (rv) -- (pi) node[midway, below, font=\scriptsize] {97}; \draw (fa) -- (bu) node[midway, above right, font=\scriptsize] {211}; \draw (pi) -- (bu) node[midway, below, font=\scriptsize] {101}; \end{tikzpicture} $$ Laid out as a priority-queue trace, the run reads as follows. Each row shows the node selected (lowest $g$), the frontier entries it generates with their cumulative costs, and the frontier that results, sorted by $g$. A goal that is merely _generated_ sits in the queue like any other node and is returned only when it reaches the front. | Step | Select ($g$) | Generates ($g$) | Frontier (sorted by $g$) | | --- | --- | --- | --- | | $1$ | Sibiu ($0$) | Rimnicu ($80$), Fagaras ($99$) | Rimnicu $80$, Fagaras $99$ | | $2$ | Rimnicu ($80$) | Pitesti ($177$) | Fagaras $99$, Pitesti $177$ | | $3$ | Fagaras ($99$) | Bucharest ($310$) | Pitesti $177$, Bucharest $310$ | | $4$ | Pitesti ($177$) | Bucharest ($278$) | Bucharest $278$ (replaces $310$) | | $5$ | Bucharest ($278$) | — goal selected | — return | At step $3$ a Bucharest node exists at cost $310$, but uniform-cost search keeps going because Pitesti at $177$ is cheaper. Expanding Pitesti in step $4$ finds Bucharest again at $80 + 97 + 101 = 278$; the cheaper node replaces the costlier one on the frontier, and only when Bucharest at $278$ is _selected_ in step $5$ does the search stop and return Sibiu-Rimnicu-Pitesti-Bucharest. Testing the goal at selection rather than generation is what saves the run from returning the $310$ path. The price of guaranteed optimality is that complexity is set by cost, not depth. With $C^\ast$ the optimal cost and $\varepsilon$ a lower bound on step cost, worst-case time and space are $O\!\left(b^{1 + \lfloor C^\ast/\varepsilon \rfloor}\right)$, which can exceed $b^d$: uniform-cost search may explore large trees of tiny steps before committing to a path of a few large ones. A concrete failure: from a start with a direct edge of cost $2$ to the goal and a chain of unit-cost edges through many intermediate states, uniform-cost search expands the entire cheap chain before it ever selects the single expensive edge, even though the chain is far longer. When every step costs the same it reduces to BFS, doing a little extra work by examining all nodes at the goal's depth to confirm none is cheaper. Breadth-first and uniform-cost search both grow the frontier _outward_ and pay for it in memory. The remaining uninformed strategies trade that memory away by diving _deep_ instead of wide — depth-first search, its depth-limited and iterative-deepening refinements, and bidirectional search — and then we can line all of them up against the four criteria at once. This continues in [Search Strategies Compared](/artificial-intelligence/search/search-strategies-compared). [^aima-solving]: **Russell & Norvig**, _Artificial Intelligence: A Modern Approach_ (3rd ed.), §3.1 — Problem-Solving Agents: a goal-based agent whose future actions of unknown value are chosen by first examining actions that lead to states of known value, formulating the problem and searching offline before executing. [^aima-formulate]: **Russell & Norvig**, _AIMA_ (3rd ed.), §3.1.1–3.1.2 — Well-defined problems and abstraction: the five problem components, and choosing a level of abstraction that removes irrelevant detail while keeping the abstract solution valid and easy to carry out. [^aima-searching]: **Russell & Norvig**, _AIMA_ (3rd ed.), §3.3 — Searching for Solutions: the search tree, frontier, and explored set; TREE-SEARCH, GRAPH-SEARCH, and the separation property of the frontier. [^aima-ucs]: **Russell & Norvig**, _AIMA_ (3rd ed.), §3.4.2 — Uniform-Cost Search: expanding the lowest-$g(n)$ node with a priority queue, its optimality proof via nonnegative step costs, and the $O(b^{1+\lfloor C^\ast/\varepsilon\rfloor})$ bound; §3.4.1, §3.4.3–3.4.5 for the other strategies and the comparison of Figure 3.21.