Search algorithms are fundamental to AI, providing a systematic way for an agent to find a sequence of actions to accomplish its goals. Instead of acting reflexively, a problem-solving agent plans ahead.

The Problem-Solving Process

An intelligent agent typically follows a four-phase process to solve problems.

1. Formulate Goal First, the agent determines a desired future state. This goal is the target it aims to reach.

2. Formulate Problem Next, the agent defines the problem in a formal way. This involves describing the possible states of the world and the actions it can take to transition between them.

3. Search The agent explores possible action sequences to find one that leads from the initial state to the goal state. This sequence is called a solution.

4. Execute Finally, the agent performs the actions found in the solution, one by one.

---

Problem Formulation

To solve a problem using search, we must first define it precisely. This involves specifying five key components:

StatesRequiredDescriptions of the world

A representation of the world's configuration. This includes the initial state (where the agent begins) and one or more goal states. The set of all states reachable from the initial state is called the state space.

ActionsRequiredOperators

The set of possible actions available to the agent in a given state s, often represented as ACTIONS(s).

Transition ModelRequired`RESULTS(s, a)`

This model describes what happens when the agent performs an action. RESULTS(s, a) returns the new state that results from performing action a in state s.

Action CostOptional`c(s, a, s')`

A function that assigns a numeric cost to taking action a in state s to reach state s'. The total cost of a path is the sum of its individual action costs.

Goal TestRequiredConstraint

A function that determines whether a given state is a goal state.

Example: Traveling in Romania

• States: The various cities on the map.
• Initial State: In(Arad)
• Goal Test: Is In(Bucharest)?
• Actions: Go(city), e.g., Go(Sibiu).
• Transition Model: RESULT(In(Arad), Go(Sibiu)) returns In(Sibiu).
• Path Cost: The sum of the distances between cities on the path.

---

Tree Search vs. Graph Search

As an agent explores the state space, it builds a search tree. However, this can lead to problems with repeated states.

Tree Search

A tree search algorithm explores the state space by building a search tree where each node represents a state and each edge is an action.

• Process: It starts at the root (initial state) and expands nodes, adding their successors to the frontier of unexpanded nodes.
• Major Flaw: It does not keep track of previously visited states. This can lead to getting stuck in infinite loops if the state space contains cycles (e.g., Arad → Sibiu → Arad). It may also explore redundant, less optimal paths to the same state.

Graph Search

A graph search improves upon tree search by actively handling repeated states.

• Process: In addition to the frontier, it maintains an explored set (or "closed list") of all nodes that have already been expanded.
• Key Improvement: When expanding a node, if a successor state is already in the explored set or the frontier, the algorithm can ignore it or update the path if the new path is cheaper. This prevents infinite loops and prunes redundant paths, making it far more efficient in many problems.

---

Uninformed Search Strategies

Uninformed (or "blind") search strategies explore the state space without any extra information about how close a state is to the goal. The only information they use is what's provided in the problem formulation.

The primary difference between these strategies is the order in which they expand nodes from the frontier.

Breadth-First Search (BFS)

BFS explores level by level. It expands the shallowest unexpanded node first. This is achieved by managing the frontier as a FIFO (First-In, First-Out) queue.

• Complete? Yes.
• Optimal? Yes, but only if all action costs are identical.
• Complexity: Time and space are $O(b^d)$.

Uniform-Cost Search (UCS)

UCS expands the node with the lowest path cost (g(n)) from the initial state. It is like BFS but prioritizes cost over depth. The frontier is managed as a priority queue.

• Complete? Yes (if action costs > 0).
• Optimal? Yes, always finds the cheapest solution.
• Complexity: Time and space are $O(b^{1+floor(C^*/\epsilon)})$, where $C^*$ is the cost of the optimal solution.

Depth-First Search (DFS)

DFS explores as deeply as possible along each branch before backtracking. It expands the deepest unexpanded node first. This is achieved by managing the frontier as a LIFO (Last-In, First-Out) stack.

• Complete? No, can get stuck in infinite loops.
• Optimal? No.
• Complexity: Time is $O(b^m)$, but space is only $O(bm)$, making it very memory-efficient.

Depth-Limited Search (DLS)

DLS is a modification of DFS that imposes a cutoff on the maximum depth of exploration. It treats any node at depth L as having no successors. This solves the infinite loop problem of DFS but introduces a new issue: if the solution is deeper than L, DLS won't find it.

Iterative Deepening Search (IDS)

IDS combines the best of both worlds. It repeatedly runs Depth-Limited Search, incrementally increasing the depth limit: L=0, L=1, L=2, .... It seems wasteful, but it is often the preferred uninformed search method when the search space is large and the depth of the solution is unknown.

• Complete? Yes.
• Optimal? Yes, if all action costs are identical.
• Complexity: Time is $O(b^d)$, and space is $O(bd)$.

Summary of Search Strategies

Here's how the uninformed search algorithms stack up based on the four key evaluation criteria.

Criterion	Breadth-First	Uniform-Cost	Depth-First	Depth-Limited	Iterative Deepening
Complete?	Yes	Yes	No	No	Yes
Optimal?	Yes (if costs are equal)	Yes	No	No	Yes (if costs are equal)
Time Complexity	$O(b^d)$	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$	$O(b^m)$	$O(b^L)$	$O(b^d)$
Space Complexity	$O(b^d)$	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$	$O(bm)$	$O(bL)$	$O(bd)$

Where:

• b = branching factor
• d = depth of the shallowest solution
• m = maximum depth of the state space
• L = depth limit for DLS
• C* = cost of the optimal solution

Changelog

8/11/25, 2:48 AM

View All Changelog

• c2b36-feat: add search notes for AIon 8/11/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)