Search Algorithms in AI - GeeksforGeeks 05/11/25, 1:32 PM

Search... Courses Tutorials Practice Jobs Sign In

Search Algorithms in AI
Last Updated : 28 Jul, 2025

Search algorithms in AI help find solutions by exploring possible paths or options in a problem space.
tasks like pathfinding, decision making and game playing. These algorithms work by searching throug
possibilities to reach a goal, either blindly without extra information or with guidance using heuristics.

Types of search algorithms

SearchAlgorithms

UninformedSearch InformedSearch

Depth Breadth Uniform

First First Cost Greedy A*
Search Search Search
Search Search Sea

Search Algorithms in AI

There are mainly 2 types of search algorithms i.e Uninformed Search Algorithms and Informed Search

Uninformed Search Algorithms

Uninformed search also called blind search explores the search space without any domain specific kno
heuristics. It treats all nodes equally and chooses which path to explore next based solely on general
or path cost.

1. Depth First Search

Depth First Search explores paths by going as deep as possible along one direction before backtrac
or recursion to keep track of the path.
DFS is memory efficient compared to BFS since it doesn’t need to store all siblings at each level.
However it is not guaranteed to find the shortest path and may get stuck in an infinite loop if the se
contains cycles unless depth limits or visited checks are applied.

For Example: Which solution would DFS find to move from node S to node G if run on the graph below

https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/ Page 1 of 6
Search Algorithms in AI - GeeksforGeeks 05/11/25, 1:32 PM

As DFS traverses the tree deepest node first it would always pick the deeper branch until it reaches
runs out of nodes and goes to the next branch.
Path: S->A->B->C->G

2. Breadth First Search

Breadth First Search is a fundamental search algorithm that explores all possible paths level by lev
the root node and explores all neighboring nodes before moving to the next level of nodes.
BFS is complete and guarantees finding the shortest path if each move has the same cost.
However its main drawback is high memory usage as it stores all nodes at the current level before
which can grow rapidly for large or complex problems.

For Example: Which solution would BFS find to move from node S to node G if run on the graph below

As BFS traverses the tree shallowest node first it would always pick the shallower branch until it re
or it runs out of nodes and goes to the next branch.
Path: S->D->G

https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/ Page 2 of 6
 Search Algorithms in AI - GeeksforGeeks 05/11/25, 1:32 PM

3. Uniform Cost Search

Uniform Cost Search is similar to BFS but takes the cost of each move into account. It always expan
lowest cumulative path cost from the start.
This makes UCS optimal and complete and useful when actions have different costs such as in navi
It uses a priority queue to manage the frontier and ensures the cheapest path is always chosen nex

For Example: Which solution would UCS find to move from node S to node G if run on the graph belo

The cost of each node is the cumulative cost of reaching that node from the root and based on the U
path with the least cumulative cost is chosen.
Path: S->A->B->G

Informed Search Algorithms

Informed search uses domain knowledge in the form of heuristics to make smarter decisions during th
These heuristics estimate how close a state is to the goal guiding the search more efficiently.

1. Greedy Search

Greedy search is a heuristic based algorithm that selects the path which appears to lead most direc
It makes decisions based solely on the estimated cost from the current node to the goal (h(n)) ignor
taken to reach the current node (g(n)).
This approach makes greedy search fast and memory efficient as it focuses only on immediate gain

Skip to content
For Example: Find the path from S to G using greedy search, the heuristic values h of each node below
Machine Learning with R node.
Machine Learning Algorithms EDA Math for Machine Learning Machine Learning Interview Questions ML Projects Deep Learning Sign In

Explore GfG Connect New

Share Your Experiences

Machine Learning Basics

Python for Machine Learning

Feature Engineering

https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/ Page 3 of 6
Search Algorithms in AI - GeeksforGeeks 05/11/25, 1:32 PM

Supervised Learning
S
Unsupervised Learning
h=7

Model Evaluation and Tuning

Advanced Techniques
D
ML & Data Science Course
A
h=5
h=9

E
h=4 h=3

G
h=0

Starting from S we can traverse to A(h=9) or D(h=5). We choose D as it has the lower heuristic cos
Now from D we can move to B(h=4) or E(h=3). We choose E with a lower heuristic cost.
Finally from E we go to G(h=0). This entire traversal is shown in the search tree below, in blue.
Path: S->D->E->G

2. A* Tree Search:

A* tree search also uses the f(n) = g(n) + h(n) evaluation but treats the search space as a tree which
track already visited nodes. Every path is explored independently even if it leads to the same state.
This can result in duplicate work and a larger search space, especially in graphs with cycles.
Although it’s simpler to implement A* tree search may be less efficient and is typically used when t
is naturally a tree or when memory constraints prevent maintaining a closed list.

For Example: Find the path to reach from S to G using A* search.

Starting from S the algorithm computes g(x) + h(x) for all nodes in the fringe at each step choosing
lowest sum. The entire work is shown in the table below. It search like:

Path h(x) g(x) f(x)

S 7 0 7

https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/ Page 4 of 6
Search Algorithms in AI - GeeksforGeeks 05/11/25, 1:32 PM

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-> G-> E and Cost: 7

3. A* Graph search

A* graph search is an informed algorithm that finds the shortest path in a graph by considering bot
node (g(n)) and the estimated cost to the goal (h(n)).
It keeps track of visited nodes using a closed list to avoid revisiting them which makes it efficient an
redundant paths.
This approach ensures optimality and completeness if the heuristic is admissible.
It’s suitable for complex environments like road maps or game levels where paths may loop or inter

For Example: Use graph searches to find paths from S to G in the following graph.

In this Algo we keep a track of nodes explored so that we don't re explore them.
Path: S->D->B->E->G and Cost: 7

https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/ Page 5 of 6
Search Algorithms in AI - GeeksforGeeks 05/11/25, 1:32 PM

Comparison of Different Search Algorithms

Algorithm Time Complexity Space Complexity Complete Opt

Breadth First Search O(bd ) O(bd ) Yes Yes (if step c

Depth First Search O(bd ) O(d) No N

Uniform Cost Search O(b1+

C∗
) O(b1+
C∗
)
ϵ ϵ
Yes Y

Greedy Search O(bm ) O(bm ) No N

A* Tree Search O(bd ) O(bd ) Yes (if h is admissible) Yes (if h is

A* Graph Search O(bd ) O(bd ) Yes (if h is admissible) Yes (if h is

Related Articles:

1. Artificial Intelligence (AI) Algorithms

2. Informed Search Algorithms in Artificial Intelligence
3. Difference between Informed and Uninformed Search in AI
4. Uninformed Search Algorithms in AI

Comment M MdRafi… Follow

Article Tags : Technical Scripter Machine Learning

Company Explore Tutorials Courses O!line Preparation

About Us POTD Programming IBM Certification Centers Corner
Corporate & Communications Address: Legal Job-A-Thon Languages DSA and Noida Interview Corner
A-143, 7th Floor, Sovereign Corporate Privacy Policy Connect DSA Placements Bengaluru Aptitude
Tower, Sector- 136, Noida, Uttar Pradesh
Careers Blogs Web Technology Web Pune Puzzles
(201305)
Contact Us Nation Skill Up AI, ML & Data Development Hyderabad GfG 160
Corporate Science Data Science Patna System Design
Registered Address:
Solution DevOps Programming
K 061, Tower K, Gulshan Vivante
Apartment, Sector 137, Noida, Gautam Campus Training CS Core Subjects Languages
Buddh Nagar, Uttar Pradesh, 201305 Program GATE DevOps & Cloud
School Subjects GATE
So!ware and Trending
Tools Technologies

@GeeksforGeeks, Sanchhaya Education Private Limited, All rights reserved

https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/ Page 6 of 6