Search and Optimization

Introduction

Many artificial-intelligence systems must choose actions without being given a direct procedure for every situation. A route planner selects a path, a game-playing program selects a move, a robot plans movements, and a scheduling system allocates scarce resources. These tasks can often be expressed as search problems: the system explores a space of possible states and seeks a solution that satisfies a goal, preferably at low cost.

Search is not merely trial and error. Its effectiveness depends on how states are represented, which frontier node is selected next, whether domain knowledge is available, and how solution quality is measured. This chapter develops the principal uninformed, informed, local, and evolutionary search methods used in introductory AI. It compares completeness, optimality, time complexity, space complexity, and heuristic quality, while also considering implementation, practical applications, and limitations.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Formulate an AI task as a state-space search problem.

2. Explain and implement breadth-first, depth-first, uniform-cost, greedy best-first, and A* search.

3. Compare algorithms using completeness, optimality, time, and space complexity.

4. Explain admissible and consistent heuristics and evaluate heuristic quality.

5. Distinguish systematic graph search from local and evolutionary search.

6. Select an appropriate search strategy for a practical AI application.

7. Identify limitations, computational risks, and ethical implications of automated search.

1. Search as Problem Solving

A search problem is commonly specified by five components:

• Initial state: the condition in which the agent begins.
• Actions: the legal operations available in a state.
• Transition model: the state produced when an action is applied.
• Goal test: a procedure that determines whether a state satisfies the objective.
• Path-cost function: a nonnegative measure of the cost of an action sequence.

A state describes information relevant to future decisions. A node is a data structure used by the search algorithm; it normally stores a state, its parent, the action used to reach it, path cost, and depth. Several nodes may represent the same state if that state is reached through different paths.

The set of all reachable states is the state space. A sequence of actions from the initial state to a goal is a solution. An optimal solution has minimum path cost among all solutions. If every action has identical cost, minimum-cost search is equivalent to finding a shortest path in number of steps; if costs differ, the two notions are not equivalent.

Search algorithms maintain a frontier (or open list) containing generated but unexpanded nodes. In graph search, an explored set records states already expanded. Tree search does not use this set and can repeatedly explore the same state, potentially causing loops and severe inefficiency.

A useful abstract procedure is:

1. Put the initial node in the frontier.

2. Remove a frontier node according to the algorithm's selection rule.

3. Test it for the goal.

4. If it is not a goal, expand it by generating successors.

5. Add appropriate successors to the frontier and continue.

The central design choice is step 2: which node should be expanded next?

2. Measuring Search Performance

Four standard criteria are used.

Completeness means that the algorithm is guaranteed to find a solution whenever one exists, under stated assumptions. Optimality means that the returned solution has minimum path cost. Time complexity measures the number of generated or expanded nodes. Space complexity measures the maximum number of nodes stored in memory.

Let:

• \(b\) be the maximum branching factor;
• \(d\) be the depth of the shallowest goal;
• \(m\) be the maximum depth of the search space;
• \(C^*\) be the cost of an optimal solution;
• \(\varepsilon>0\) be a lower bound on every action cost.

Complexity statements are asymptotic and assume finite branching where required. They describe worst-case behavior, not the exact performance of every problem.

A search tree may contain exponentially many nodes. Consequently, memory is often the practical bottleneck. A method that is theoretically attractive but stores the entire frontier may fail on a modestly large problem.

3. Uninformed Search

Uninformed, or blind, search uses no problem-specific estimate of distance to a goal. It relies only on the formal problem definition.

3.1 Breadth-First Search

Breadth-first search (BFS) expands the shallowest unexpanded node first. A first-in, first-out queue implements this rule. It explores the root, then all nodes at depth one, then all nodes at depth two, and so forth.

With finite branching factor, BFS is complete. It is optimal when every action has the same cost, because the first goal found is at the smallest depth. It is not generally optimal when action costs differ: a shallow path may be more expensive than a deeper path.

For unit-cost actions, BFS has time complexity \(O(b^{d+1})\) and space complexity \(O(b^{d+1})\) under a conventional tree-search bound. These bounds are often summarized as \(O(b^d)\) when constant factors and the final layer are ignored. BFS's major weakness is memory consumption.

3.2 Depth-First Search

Depth-first search (DFS) expands the deepest available node first. A last-in, first-out stack, or recursion, implements the policy. DFS follows one branch until it reaches a goal, a dead end, or a depth limit, then backtracks.

DFS uses relatively little memory: \(O(bm)\) for a tree-search implementation. However, it is not complete in infinite-depth spaces or spaces containing cycles unless suitable cycle checking or depth limits are used. It is not optimal, since it may find a very long solution before a short one.

DFS can be effective when solutions are deep, memory is limited, and the order of successors is favorable. It can be disastrous when the first branch is infinite or contains a huge irrelevant subtree.

3.3 Depth-Limited and Iterative-Deepening Search

Depth-limited search is DFS with a maximum depth \(\ell\). It avoids infinite descent but may fail to find a solution deeper than \(\ell\). Iterative-deepening depth-first search (IDDFS) repeatedly applies depth-limited search with limits 0, 1, 2, and so on until a goal is found.

Although IDDFS regenerates nodes at shallow depths, the deepest layer usually dominates the work. With unit costs and finite branching, its time complexity is \(O(b^d)\), and its space complexity is \(O(bd)\). It is complete and optimal for unit-cost actions. IDDFS is valuable when the solution depth is unknown and memory is insufficient for BFS.

3.4 Uniform-Cost Search

Uniform-cost search (UCS) expands the node with the smallest path cost \(g(n)\), where \(g(n)\) is the cost from the initial state to node \(n\). A priority queue implements the frontier.

UCS is equivalent to Dijkstra's algorithm when applied to a graph with nonnegative edge costs. If every action cost is at least \(\varepsilon>0\), UCS is complete and optimal. The positive lower bound prevents infinitely many increasingly long paths from having bounded total cost. With arbitrary zero-cost cycles, additional graph-search controls are necessary, and standard complexity guarantees must be stated carefully.

A common bound is \(O(b^{1+\lfloor C^*/\varepsilon\rfloor})\) time and space, because no node with path cost greater than the optimal solution needs to be expanded before an optimal goal is selected. In practice, UCS is appropriate when costs differ and no reliable heuristic is available. It may explore many low-cost but irrelevant paths.

4. Informed Search and Heuristics

An informed search uses a heuristic function \(h(n)\), an estimate of the least remaining cost from node \(n\) to a goal. The heuristic does not have to be exact. Its purpose is to guide search toward promising regions.

A heuristic is admissible if it never overestimates the true remaining cost:

\[

0 \le h(n) \le h^*(n),

\]

where \(h^*(n)\) is the actual minimum cost from \(n\) to a goal. It is consistent (or monotone) if, for every edge from \(n\) to successor \(n'\) with cost \(c(n,n')\),

\[

h(n) \le c(n,n')+h(n').

\]

Consistency implies admissibility when the heuristic is zero at goals. It also implies that the evaluation value \(f(n)=g(n)+h(n)\) does not decrease along a path. In graph-search A*, consistency permits a state to be closed permanently when it is removed from the frontier, assuming nonnegative edge costs.

Good heuristics are accurate, inexpensive to compute, and appropriately matched to the problem. A heuristic that is always zero provides no guidance but remains admissible. A heuristic equal to the exact remaining cost makes search highly efficient, although obtaining it is usually as difficult as solving the original problem.

If two admissible heuristics satisfy \(h_2(n)\ge h_1(n)\) for all states, \(h_2\) is said to dominate \(h_1\). Under standard A* graph-search conditions, the more informed heuristic generally causes no more node expansions than the weaker one, apart from tie-breaking effects.

4.1 Greedy Best-First Search

Greedy best-first search selects the node with the smallest \(h(n)\). It attempts to reach a goal as quickly as estimated, ignoring the cost already incurred. It can be fast when the heuristic is informative, but it is neither generally complete in unrestricted spaces nor optimal. It may follow an apparently close goal through an extremely expensive route.

4.2 A* Search

A* selects the node with minimum

\[

f(n)=g(n)+h(n),

\]

where \(g(n)\) is the cost already paid and \(h(n)\) estimates the remaining cost. A* therefore balances past cost and predicted future cost.

For a finite branching graph with positive action costs, A graph search is complete. With an admissible and consistent heuristic, it is optimal. With admissibility but inconsistency, optimal graph search may need to reopen states when a cheaper path is discovered. A tree search remains optimal under an admissible heuristic if the usual assumptions hold, but may contain duplicate states.

A's worst-case time and space requirements are exponential in solution depth in the general case. Its practical success depends heavily on the heuristic and memory capacity. In the special case \(h(n)=0\), A becomes UCS. If \(g(n)\) is ignored, the selection rule resembles greedy best-first search.

Worked Example: Route Selection

Suppose a graph has two routes from S to G. Route 1 is S–A–G, with edge costs 2 and 8, so its total cost is 10. Route 2 is S–B–C–G, with edge costs 3, 3, and 3, so its total cost is 9. A shallowest-goal strategy may prefer Route 1 because it has two edges. UCS prefers Route 2 because 9 is less than 10.

Assume the heuristic values are \(h(A)=8\), \(h(B)=6\), and \(h(C)=3\), with \(h(G)=0\). At A, \(f(A)=g(A)+h(A)=2+8=10\). At B, \(f(B)=3+6=9\). A expands B before A and then obtains the nine-cost route. The heuristic values are admissible if they do not exceed the actual remaining costs: A's remaining cost is 8, B's is 6, and C's is 3. This example illustrates why depth and cost must not be confused and how A combines both.

5. Constructing and Evaluating Heuristics

Heuristics frequently arise from a simplified version of the original problem. If a relaxed problem removes constraints, its optimal solution cannot be more expensive than the original problem. Therefore, the relaxed-problem cost is admissible.

For the sliding-tile puzzle, the number of misplaced tiles is admissible because each misplaced tile must move at least once. Manhattan distance—the sum of each tile's horizontal and vertical displacement from its goal position—is also admissible when one move shifts one tile by one position, because each tile must make at least that many moves. Manhattan distance dominates misplaced-tile count in this setting because each tile's distance is at least one when misplaced and may be greater.

Heuristics can also be combined. The maximum of several admissible heuristics is admissible:

\[

h(n)=\max(h_1(n),h_2(n),\ldots,h_k(n)).

\]

The maximum remains a lower bound because none of the component estimates overestimates. Summing heuristics is not automatically safe; it is admissible only when the component costs represent non-overlapping contributions or are otherwise proven compatible.

Heuristic quality can be studied through the effective branching factor, the value \(b^*\) satisfying approximately

\[

N+1=1+b^+(b^)^2+\cdots+(b^*)^d,

\]

where \(N\) is the number of nodes generated to find a solution at depth \(d\). A lower effective branching factor indicates more effective guidance, although it depends on the test set and implementation.

6. Local Search

Systematic search retains explicit paths and a frontier. Local search instead keeps one or a small number of current candidate states and moves through neighboring states. It is especially useful for optimization problems where the path is unimportant and only the final configuration matters.

A state-space landscape assigns an objective value to each state. A local optimum is better than its immediate neighbors but may be worse than a distant state. A global optimum is best throughout the search space. Landscapes may contain plateaus, where neighboring states have equal value, ridges, and deceptive local optima.

6.1 Hill Climbing

Hill climbing repeatedly moves to a better neighboring state. In steepest-ascent hill climbing, the best available neighbor is selected. It uses little memory and can rapidly improve a solution, but it may stop at a local optimum, plateau, or ridge. Random restarts run hill climbing from multiple initial states and increase the chance of finding a good region, though they do not guarantee a global optimum in general.

6.2 Simulated Annealing

Simulated annealing sometimes accepts a worsening move to escape local optima. For a maximization problem, if a candidate is worse by an amount \(\Delta>0\), it may be accepted with probability

\[

P=\exp(-\Delta/T),

\]

where \(T>0\) is the temperature. This formula is applicable when \(\Delta\) and \(T\) are expressed on the same objective scale. As the temperature decreases according to a cooling schedule, worsening moves become less likely. With sufficiently slow cooling under theoretical conditions, global-optimum convergence can be established, but practical schedules are finite and offer no general guarantee.

6.3 Local Beam Search

Local beam search maintains \(k\) candidate states. It generates their successors and retains the best \(k\) among them. Unlike running independent searches, candidates can share information because successors from all current states compete for survival. However, the population may lose diversity and converge prematurely.

7. Evolutionary Search

Evolutionary algorithms maintain a population of candidate solutions. Each candidate is encoded as a chromosome or representation and evaluated by a fitness function. The usual cycle includes selection, variation, and replacement:

1. Select parent candidates, often favoring higher fitness.

2. Apply crossover to combine information from parents.

3. Apply mutation to introduce variation.

4. Evaluate offspring and form the next population.

A genetic algorithm is not guaranteed to find a global optimum in practical finite time. Its behavior depends on representation, population size, selection pressure, crossover, mutation rate, stopping criteria, and fitness design. Excessive selection pressure can destroy diversity; excessive mutation can disrupt useful structures.

Evolutionary search is suitable for difficult optimization problems with huge, irregular, discontinuous, or poorly understood spaces. Examples include timetabling, vehicle routing, feature selection, engineering design, and hyperparameter optimization. It may require many objective evaluations and may produce good rather than provably optimal solutions.

8. Comparative Analysis

BFS is complete and unit-cost optimal but memory intensive. DFS is memory efficient but neither generally complete nor optimal. IDDFS combines DFS-like memory with BFS-like guarantees for unit-cost problems. UCS is complete and optimal for nonnegative costs with a positive lower bound, but it can expand many nodes. Greedy best-first search can be rapid but sacrifices reliable solution quality. A* is complete and optimal under appropriate heuristic and cost assumptions, but its memory demand can be substantial.

Local and evolutionary methods differ fundamentally from systematic methods. They usually do not guarantee an optimal solution, but they can operate on optimization spaces where enumerating paths is impractical. Their evaluation is commonly empirical: solution quality, runtime, robustness across random seeds, and resource use should all be measured.

A practical selection guide is:

• Use BFS for shallow unit-cost solutions when memory is adequate.
• Use DFS when memory is severely constrained and completeness is not essential.
• Use IDDFS when action costs are uniform and solution depth is unknown.
• Use UCS when costs vary and no trustworthy heuristic exists.
• Use A* when a useful admissible heuristic and sufficient memory are available.
• Use greedy search when a fast, possibly suboptimal answer is acceptable.
• Use local or evolutionary methods when the objective is more important than the path and the space is too large for systematic exploration.

9. Illustrative Case: Emergency Ambulance Dispatch

Background

Consider an illustrative municipal ambulance-dispatch system. It must choose a route from an ambulance station to an incident. Roads have different travel times, some routes may be temporarily unavailable, and the system must update its recommendation as traffic changes.

Problem

A route with the fewest road segments is not necessarily fastest. A three-segment motorway route may take less time than a two-segment route through congested streets. The system therefore needs a cost model and a search strategy that can respond to changing conditions.

Analysis

The initial state is the ambulance's current intersection, actions are legal road movements, the transition model gives the next intersection and estimated travel time, the goal test checks arrival at the incident, and path cost is total estimated travel time. UCS would find a minimum-time route if all travel-time estimates are nonnegative and fixed during a search. BFS would be inappropriate because it minimizes the number of segments rather than travel time.

A* can use a heuristic based on straight-line distance divided by a maximum legally attainable speed. If the speed assumption is an upper bound on possible travel speed, the resulting time estimate is a lower bound on actual travel time and is therefore admissible. In practice, road restrictions, turn penalties, emergency-vehicle rules, and time-dependent congestion must be modeled carefully.

Approach and Outcome

The dispatch system can run A* on a current road graph, use a priority queue, maintain best-known costs, and replan when significant traffic or closure information arrives. A consistency check is useful when the heuristic is used in graph search. If conditions change during execution, the original optimality guarantee applies only to the graph and costs used at planning time; it does not guarantee optimality in the changing real world.

Learning Points

The case demonstrates that problem formulation determines what “optimal” means. It also shows why admissible heuristics must reflect physical constraints, why dynamic environments require replanning, and why a mathematically optimal route may not be operationally preferable if it ignores safety, uncertainty, or emergency access policies.

10. Implementation and Professional Practice

A robust implementation should distinguish state identity from node identity, prevent or manage duplicate states, and use appropriate priority-queue operations. For UCS and A, when a cheaper path to an existing state is discovered, the implementation must update its frontier priority or insert a new entry and ignore stale entries later. Goal testing is normally performed when a node is selected for expansion, not merely when it is generated, for UCS and A; this preserves optimality under standard assumptions.

Engineers should record generated nodes, expanded nodes, maximum frontier size, runtime, solution cost, and failure conditions. Reproducibility requires fixed data versions and, for stochastic algorithms, recorded random seeds. Comparing algorithms only by runtime can be misleading: hardware, implementation language, heuristic computation, and preprocessing all affect results.

In real systems, search objectives may encode public values. A route optimizer that minimizes time alone may produce unsafe routes, exclude accessibility requirements, or consume excessive energy. Search-based recommendations should therefore expose relevant constraints, support human override in high-stakes settings, and be tested for edge cases. Data quality and model uncertainty can undermine formal guarantees even when the search algorithm is correct.

11. Contemporary Directions and Limitations

Modern planning systems increasingly combine classical search with learned heuristics, neural representations, constraint programming, and domain-specific pruning. A learned heuristic may greatly improve speed, but unless it is bounded or verified it may overestimate and invalidate A's optimality guarantee. Systems may also use weighted A, which evaluates \(f(n)=g(n)+w h(n)\) for \(w\ge1\). Under standard conditions and an admissible heuristic, weighted A* can provide a bounded solution-cost guarantee of at most \(w\) times optimal in appropriate graph-search settings, while often expanding fewer nodes. The guarantee depends on implementation and assumptions, so it should not be claimed without checking them.

Other developments include memory-bounded A*, anytime search, incremental replanning, Monte Carlo tree search for games and decision-making, and multiobjective search. These methods address practical limits such as changing environments, multiple objectives, and restricted memory. Nevertheless, no search method removes the underlying combinatorial explosion in all problem classes. Approximation, abstraction, decomposition, and domain knowledge remain essential.

Best Practices

1. Define states and actions so that all information relevant to future decisions is represented.

2. State whether costs are uniform, nonnegative, dynamic, or uncertain.

3. Prefer graph search when duplicate states or cycles are likely.

4. Prove or test heuristic admissibility and consistency before claiming A* optimality.

5. Match the algorithm to memory limits as well as time requirements.

6. Evaluate solution quality and robustness, not only speed.

7. Use random restarts, diversity preservation, or multiple runs for stochastic methods.

8. Validate objectives and constraints with domain experts, especially in safety-critical applications.

9. Log assumptions and monitor performance after deployment.

Chapter Summary

Search formulates intelligent action selection as exploration of a state space defined by an initial state, actions, transitions, a goal test, and a cost function. BFS expands shallow nodes and is complete and unit-cost optimal but memory intensive. DFS saves memory but can be incomplete and suboptimal; IDDFS recovers strong unit-cost guarantees with low memory. UCS expands lowest path cost and is optimal for suitable nonnegative-cost problems. Greedy best-first search uses estimated remaining cost and may be fast but has weak guarantees. A* combines path cost and heuristic estimate through \(f=g+h\); with suitable assumptions, it is complete and optimal.

Admissible heuristics never overestimate, while consistent heuristics satisfy a triangle-like condition that supports efficient graph search. Relaxed problems, maximum combinations of admissible estimates, and domain knowledge are important sources of effective heuristics. Local search uses limited memory and is useful for optimization but can become trapped in local optima. Simulated annealing, beam search, and evolutionary algorithms trade formal guarantees for scalability and flexibility.

Professional search design requires careful formulation, complexity analysis, reproducible evaluation, responsible objectives, and awareness that changing data can invalidate static guarantees. The best algorithm is determined not only by theoretical properties but also by cost structure, memory, heuristic quality, uncertainty, and the consequences of failure.

Key Terms

State: A representation of the relevant condition of a problem.

Node: A search data structure containing a state and path information.

State space: The set of states reachable through legal actions.

Frontier: Generated nodes awaiting selection and expansion.

Explored set: States already expanded in graph search.

Branching factor: The number of successors generated per state, commonly represented by \(b\).

Completeness: The property of finding a solution whenever one exists under stated assumptions.

Optimality: The property of returning a minimum-cost solution.

Uniform-cost search: Search that expands the node with the smallest accumulated path cost.

Heuristic: An estimate of the cost from a state to a goal.

Admissible heuristic: A heuristic that never overestimates true remaining cost.

Consistent heuristic: A heuristic satisfying \(h(n)\le c(n,n')+h(n')\) for every successor.

A* search: Search ordered by \(f(n)=g(n)+h(n)\).

Effective branching factor: An empirical measure of search expansion efficiency.

Local optimum: A state better than its immediate neighbors but not necessarily globally best.

Hill climbing: Local search that moves to an improving neighboring state.

Simulated annealing: Local search that sometimes accepts worsening moves according to temperature.

Evolutionary algorithm: Population-based optimization using selection and variation.

Fitness function: A function measuring the quality of a candidate solution.

Replanning: Computing a new plan when the environment or problem information changes.

Review Questions

Short Answer Questions

1. What five components define a classical search problem?

2. Why is BFS not generally optimal when action costs differ?

3. Define an admissible heuristic.

4. What is the evaluation function used by A*?

5. State one limitation of hill climbing.

Long Answer Questions

1. Compare BFS, DFS, IDDFS, and UCS in terms of selection rule, completeness, optimality, time, and space.

2. Explain admissibility and consistency, and discuss why they matter for A* graph search.

3. Describe how relaxed problems can be used to construct heuristics, using the sliding-tile puzzle as an example.

4. Compare systematic search, local search, and evolutionary search in terms of memory, guarantees, and appropriate applications.

5. Explain how an ambulance-dispatch problem can be formulated as a search problem and why A* may be preferable to BFS.

Analytical / Application Questions

1. Design a search strategy for a warehouse robot in which movement costs vary because some floor areas are congested. State the algorithm, cost model, heuristic, and assumptions needed for optimality.

2. A team proposes adding two admissible heuristics by summing them. Analyze when this is safe and propose a safer alternative.

3. An A* system is fast but occasionally returns a costly route after a learned heuristic is introduced. Diagnose possible causes and recommend tests or design changes.

Multiple Choice Questions with Answers

Question 1

Which search strategy expands the node with the lowest accumulated path cost?

A. Breadth-first search

B. Depth-first search

C. Uniform-cost search

D. Greedy best-first search

Correct Answer: C. Uniform-cost search

Question 2

Under standard assumptions, A* uses which evaluation function?

A. f(n)=h(n)-g(n)

B. f(n)=g(n)+h(n)

C. f(n)=g(n)h(n)

D. f(n)=g(n)/h(n)

Correct Answer: B. f(n)=g(n)+h(n)

Question 3

A heuristic is admissible when it:

A. Always equals the true remaining cost

B. Never overestimates the true remaining cost

C. Always overestimates the true remaining cost

D. Ignores the goal state

Correct Answer: B. Never overestimates the true remaining cost

Question 4

Which algorithm is optimal for unit-cost actions and uses a FIFO queue?

A. Breadth-first search

B. Depth-first search

C. Greedy best-first search

D. Hill climbing

Correct Answer: A. Breadth-first search

Question 5

What is a principal weakness of depth-first search?

A. It always requires exponential memory

B. It cannot use a stack

C. It is not generally complete or optimal

D. It cannot operate on graphs

Correct Answer: C. It is not generally complete or optimal

Question 6

If h(n)=0 for every state, A* behaves like:

A. Depth-first search

B. Uniform-cost search

C. Greedy best-first search

D. Simulated annealing

Correct Answer: B. Uniform-cost search

Question 7

Which method is specifically designed to escape some local optima by accepting selected worsening moves?

A. Breadth-first search

B. Uniform-cost search

C. Simulated annealing

D. Depth-limited search

Correct Answer: C. Simulated annealing

Question 8

For a maximization problem in simulated annealing, the probability exp(-Δ/T) is used when:

A. The candidate move improves the objective

B. The candidate move is worse by Δ>0

C. The temperature is exactly zero

D. There is no objective function

Correct Answer: B. The candidate move is worse by Δ>0

Question 9

Which combination of admissible heuristics is guaranteed to remain admissible?

A. Their unrestricted sum

B. Their maximum

C. Their product

D. Their average multiplied by the branching factor

Correct Answer: B. Their maximum

Question 10

What is a major practical limitation of A*?

A. It cannot use heuristics

B. It never considers path cost

C. Its memory requirement can become very large

D. It is only applicable to continuous spaces

Correct Answer: C. Its memory requirement can become very large