3.1 Problem-Solving Agents
An agent formulates a goal, defines states and actions, searches for a solution, then executes the resulting plan. A problem specifies initial state, actions, transition model, goal test, and path cost.
Problem-solving · Chapter 3
Solving Problems by Searching
A goal-based problem-solving agent searches a state space for an action sequence. Search strategy determines the order in which possibilities are explored.
Chapter guide
3.2 Example Problems
Route finding, sliding-tile puzzles, and robot navigation illustrate state-space models. Good abstractions preserve important choices while omitting irrelevant detail.
3.3 Search Algorithms
A search tree records paths from the initial state. Algorithms differ in frontier ordering and are compared by completeness, optimality, time, and space.
3.4 Uninformed Search Strategies
Breadth-first search expands shallowest nodes; uniform-cost expands the lowest path-cost node; depth-first follows a branch deeply. Their guarantees depend on branching, depth, and step costs.
3.5 Informed (Heuristic) Search Strategies
Greedy best-first prioritizes estimated distance to goal. A* prioritizes g(n)+h(n); with suitable admissible or consistent heuristics, it can find least-cost solutions.
3.6 Heuristic Functions
A heuristic estimates remaining cost. More informative estimates can reduce exploration, while admissibility requires never overestimating the true remaining cost.
Key terms and worked route
State: a possible world configuration. Frontier: generated paths waiting to be expanded. g(n): cost so far; h(n): estimated remaining cost. Uniform-cost search orders by g; A* orders by f = g + h. A heuristic is admissible if it never overestimates the true remaining cost.
Here the cheapest route is S → A → C → G with cost 2 + 2 + 2 = 6. Uniform-cost expands by accumulated cost; A* uses the displayed h-values to focus on promising routes. Since S → B costs 1 but B’s h is 4, A* may first explore A despite B’s lower g. A* is optimal when costs are nonnegative and its heuristic satisfies the required conditions (here it is consistent).
Interactive lab
Search a weighted route graph
Compare uniform-cost search with A* on the same graph. Step through frontier expansion and see the resulting path and total cost. Edge labels are travel costs; node labels are admissible distance estimates.
Frontier
S (g=0)
Expanded
—
Ready. Choose a strategy and expand.
Search cost (implementation-aware)
Inputs are the fixed directed graph G=(V,E) and strategy (UCS or A*). One step sorts the array-backed frontier in O(V log V), examines outgoing edges in O(deg(u)), and redraws all graph edges in O(E). Across at most V expansions, this implementation’s worst-case bound is O(V² log V + VE) time (the repeated whole-graph rendering contributes VE) and O(V + E) total space including graph, frontier, costs, parents, closed set, and visualization (O(V) auxiliary search state beyond the stored graph). A heap-based implementation can improve priority-queue costs; these bounds describe this demo’s repeated array sort and SVG redraw. The shown graph has five vertices and six edges.