Search Algorithms in AI

In artificial intelligence, search algorithms locate solutions by examining candidate paths or states within a problem space. They let intelligent agents choose actions, resolve problems, and meet goals efficiently—supporting uses such as navigation, robotics, gameplay, and pathfinding.

Assist AI systems in selecting the strongest option when several alternatives exist
Common in decision-making, optimization, and route-planning tasks

Types of Search Algorithms

Search methods fall into two primary families: uninformed search algorithms and informed search algorithms.

Uninformed Search Algorithms

Uninformed search—often called blind search—explores the space without domain-specific knowledge of the goal. Decisions about which node to expand next rest only on structural cues such as depth or path cost.

1. Depth First Search (DFS)

Depth First Search pushes as far as possible down one branch before backtracking. A stack (or recursion) tracks the nodes that have been visited.

Uses relatively little memory because fewer nodes are retained than with BFS
Does not always return the shortest route
Without cycle checks, it can become trapped in deep paths or loops

Example: DFS traversal from node S to G.

Because DFS favors depth, it continues along the deeper branch until it finds a solution or exhausts that branch and switches to another.
Path: S → A → B → C → G

2. Breadth First Search

Breadth First Search expands the tree level by level from the root. Every neighbor at the current depth is visited before descending further.

Guarantees a shortest path when every edge has the same cost
Complete on finite graphs
Memory-heavy because all nodes at each level must be stored

Example: BFS traversal from node S to G

Because BFS prefers shallower nodes, it expands the shallower branch until a solution appears or that level is exhausted and the next level begins.
Path: S → D → G

3. Uniform Cost Search

Uniform Cost Search expands whichever node has the smallest total cost from the start. It is appropriate when routes carry unequal costs.

Returns an optimal path with the least overall cost
Relies on a priority queue to pick the lowest-cost node
Fits weighted graphs and navigation tasks

Example: UCS traversal from node S to G

Each node’s cost is the cumulative cost from the root; UCS then selects the path whose cumulative cost is smallest.
Path: S → A → B → G

Informed Search Algorithms

Informed search incorporates domain knowledge through heuristics so the search can choose more wisely. Heuristics estimate how near a state is to the goal and steer exploration accordingly.

1. Greedy Search

Greedy Search expands the node that looks closest to the goal according to the heuristic h(n). It considers only that estimate and ignores cost already paid along the path.

Fast and memory-light thanks to heuristic guidance
Does not always yield an optimal answer
Useful when a quick approximate solution is acceptable

Example: Finding a path from S to G with greedy search; heuristic values h appear below each node name.

From S the choices are A(h=9) or D(h=5); D is chosen because its heuristic is smaller.
From D the options are B(h=4) or E(h=3); E is selected for the lower heuristic.
From E the search reaches G(h=0). The blue path in the search tree shows this sequence.
Path: S → D → E → G

2. A* Tree Search

A* Tree Search ranks nodes with an evaluation function:

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

Where:

g(n) = actual cost from the start node
h(n) = estimated cost to the goal

It prefers paths with the lowest combined cost but treats the space as a tree, so duplicate states are not recorded.

Blends real path cost with heuristic cost
May expand the same state more than once
Easier to code, yet less efficient on graphs that contain cycles

Example: Finding a path from S to G with A* search.

Starting at S, the algorithm computes g(x) + h(x) for every fringe node at each step and expands the one with the smallest sum. The table below summarizes the work.

Path	h(x)	g(x)	f(x)
S	7	0	7
S → A	9	3	12
S → D ✔	5	2	7
S → D → B ✔	4	2 + 1 = 3	7
S → D → E	3	2 + 4 = 6	9
S → D → B → C ✔	2	3 + 2 = 5	7
S → D → B → E ✔	3	3 + 1 = 4	7
S → D → B → C → G	0	5 + 4 = 9	9
S → D → B → E → G ✔	0	4 + 3 = 7	7

Path: S → D → B → E → G and Cost: 7

3. A* Graph search

A* Graph Search improves on A* Tree Search by maintaining a closed list of visited nodes. That prevents re-expansion and cuts redundant work.

Effective on graphs with cycles or repeated states
Guarantees optimality when the heuristic is admissible
Widely applied in navigation, robotics, and games

Example: Using graph search to find paths from S to G in the following graph.

Explored nodes are recorded so they are not re-explored.
Path: S → D → B → E → G and Cost: 7

Comparison of Different Search Algorithms

Algorithm	Time Complexity	Space Complexity	Complete	Optimal
Breadth First Search	\(O(b^d)\)	\(O(b^d)\)	Yes	Yes (if step cost is same)
Depth First Search	\(O(b^d)\)	\(O(d)\)	No	No
Uniform Cost Search	\(O(b^{1 + \frac{C^*}{\epsilon}})\)	\(O(b^{1 + \frac{C^*}{\epsilon}})\)	Yes	Yes
Greedy Search	\(O(b^m)\)	\(O(b^m)\)	No	No
A* Tree Search	\(O(b^d)\)	\(O(b^d)\)	Yes (if h is admissible)	Yes (if h is admissible)
A* Graph Search	\(O(b^d)\)	\(O(b^d)\)	Yes (if h is admissible)	Yes (if h is admissible)

Advantages

Help AI systems locate optimal or near-optimal answers
Valuable for pathfinding, robotics, games, and decision-making
Some methods guarantee shortest or lowest-cost routes
Heuristic approaches raise efficiency and speed

Limitations

Certain algorithms demand substantial memory and compute time
Blind search can examine many unneeded nodes
Informed search quality hinges on heuristic quality
Not every algorithm promises an optimal solution

Notifications

Search Algorithms in AI