Search Algorithms in

Artificial Intelligence
 Problem-solving agents
uses Search Algorithms to
solve specific problem and
provide the best results.
Search Algorithm Terminologies:
• Search: Searching is a step by step procedure to
solve a search-problem in a given search space.
A search problem can have three main factors:
• Search Space: Search space represents a set of
possible solutions, which a system may have.
• Start State: It is a state from where agent
begins the search.
• Goal test: It is a function which observe the current
state and returns whether the goal state is achieved
or not.
 Problem-solving agent
• A problem-solving agent is a goal-
driven agent and focuses on
satisfying the goal.

Dr. Pawan Kumar

 According to psychology, “a problem-
solving refers to a state where we wish
to reach to a definite goal from a
present state or condition.”
According to computer science, a
problem-solving is a part of artificial
intelligence which encompasses a
number of techniques such as
algorithms, heuristics to solve a
problem. Dr. Pawan Kumar
 Travelling salesman problem
The travelling salesman problem asks the following question: "Given a list of cities and the
distances between each pair of cities, what is the shortest possible route that visits each city
exactly once and returns to the origin city?
A TSP tour in the graph is 1-2-4-3-
1. is
The cost of the tour
10+25+30+15 which is 80.

Dr. Pawan Kumar

 Steps performed by Problem-
solving agent
1-Goal Formulation:
• It is the first and simplest step in problem-solving.
• It organizes the steps/sequence required to formulate
one goal out of multiple goals as well as actions to
achieve that goal.
• Goal formulation is based on the current situation and
the agent's performance measure.
2-Problem Formulation:
• It is the most important step of problem-solving which
decides what actions should be taken to achieve the
formulated goal.
• There are following five components involved in
problem formulation. Dr. Pawan Kumar
Steps performed by Problem-
solving agent
3-Initial State: It is the starting state or initial step of the agent
towards its goal.
4-Actions: It is the description of the possible actions available to
the agent.
5-Transition Model: It describes what each action does.
6-Goal Test: It determines if the given state is a goal state.
7-Path cost:
• It assigns a numeric cost to each path that follows the goal.
• The problem-solving agent selects a cost function, which
reflects its performance measure.
Remember, an optimal solution has the lowest path cost among
all the solutions.
Dr. Pawan Kumar
• Initial state, actions, and transition model together
define the state-space of the problem implicitly.

• The state-space forms a directed map or graph

where nodes are the states, links between
the nodes are actions, and the path is a
sequence of states connected by the sequence of
actions.

Dr. Pawan Kumar

 Working Steps of Problem
Solving agent
• Search: It identifies all the best possible
sequence of actions to reach the goal state from
the current state. It takes a problem as an input
and returns solution as its output.
• Solution: It finds the best algorithm out of
various algorithms, which may be proven as the
best optimal solution.
• Execution: It executes the best optimal
solution from the searching algorithms to reach
the goal state from the current state.
Dr. Pawan Kumar
8 Puzzle Problem

Dr. Pawan Kumar

8-queens problem

Dr. Pawan Kumar

 Measuring
problem-solving
performance
There are four ways to measure
the performance of an algorithm
• Completeness: It measures if the
algorithm guarantees to find a
solution (if any solution exist).
• Optimality: It measures if the
strategy searches for an optimal
solution.
• Time Complexity: The time taken
by the algorithm to find a solution.
• Space Complexity: Amount of
memory required to perform a
search. Dr. Pawan Kumar
 Search Strategies
• Uninformed Search (Blind Search)
• Informed Search (Heuristic Search)

Dr. Pawan Kumar

 Uninformed Search (Blind
Search)
• This type of search strategy does not have
any additional information about the
states except the information provided in
the problem definition.
• They can only generate the successors and
distinguish a goal state from a non-goal state.
• These type of search does not maintain any
internal state, that’s why it is also known
as Blind search.
Dr. Pawan Kumar
 Uninformed Search (Blind
Search)
There are following types of uninformed searches:
• Breadth-first search
• Uniform cost search
• Depth-first search
• Depth-limited search
• Iterative deepening search
• Bidirectional search

Dr. Pawan Kumar

 Informed Search (Heuristic
Search)
• This type of search strategy contains some additional
information about the states beyond the problem
definition.
• This search uses problem-specific knowledge to find more
efficient solutions.
• This search maintains some sort of internal states via
heuristic functions (which provides hints), so it is also called
heuristic search.
There are following types of informed searches:
• Best first search (Greedy search)
• A* search
Dr. Pawan Kumar
Dr. Pawan Kumar
Search tree
• Search tree: A tree representation of search problem is
called Search tree. The root of the search tree is the
root node which is corresponding to the initial state.
• Actions: It gives the description of all the available
actions to the agent.
• Transition model: A description of what each action
do, can be represented as a transition model.
• Path Cost: It is a function which assigns a numeric cost
to each path.
• Solution: It is an action sequence which leads from the
start node to the goal node.
• Optimal Solution: If a solution has the lowest cost
among all solutions.
Properties of Search Algorithms: four essential
properties of search algorithms to compare the
efficiency
• Completeness: A search algorithm is said to be
complete if it guarantees to return a solution if at least
any solution exists for any random input.
• Optimality: If a solution found for an algorithm is
guaranteed to be the best solution (lowest path cost)
among all other solutions, then such a solution for is
said to be an optimal solution.
• Time Complexity: Time complexity is a measure of
time for an algorithm to complete its task.
• Space Complexity: It is the maximum storage space
required at any point during the search, as the
complexity of the problem.
Types of search algorithms
Uninformed/Blind Search:
• The uninformed search does not contain any domain
knowledge such as closeness, the location of the goal.
• It operates in a brute-force way as it only includes
information about how to traverse the tree and how to
identify leaf and goal nodes.
• Uninformed search applies a way in which search tree is
searched without any information about the search
space like initial state operators and test for the goal, so
it is also called blind search.
• It examines each node of the tree until it achieves the
goal node.
Uninformed/Blind Search:
• Uninformed search is a class of general-purpose
search algorithms which operates in brute force-
way.
• Uninformed search algorithms do not have
additional information about state or search
space other than how to traverse the tree, so it is
also called blind search.
It can be divided into five main
types:
[Link]-first Search
[Link]-first Search
[Link]-limited Search
[Link] deepening depth-first search
[Link] cost search
[Link] Search
Informed Search
• Informed search algorithms use domain knowledge.
• In an informed search, problem information is available
which can guide the search.
• Informed search strategies can find a solution more
efficiently than an uninformed search strategy. Informed
search is also called a Heuristic search.
• Informed search can solve much complex problem
which could not be solved in another way.
• Informed search algorithms is a traveling salesman
problem
Informed Search
[Link] Search
2.A* Search
Uninformed/Blind Search:
 1. Breadth-first Search:
• Breadth-first search is the most common search
strategy for traversing a tree or graph. This algorithm
searches breadthwise in a tree or graph, so it is called
breadth-first search.
• BFS algorithm starts searching from the root node of the
tree and expands all successor node at the current level
before moving to nodes of next level.
• The breadth-first search algorithm is an example of a
general-graph search algorithm.
• Breadth-first search implemented using FIFO queue
data structure.
How BFS Works (Step-by-Step):

•Start with a root or starting node.

•Visit the starting node and mark it as visited.
•Enqueue all the neighboring (connected) nodes.
•Dequeue one node at a time from the front of the queue,
visit it, and enqueue all its unvisited neighbors.
•Repeat steps 3–4 until the queue is empty or the goal is
found.
Example:S---> A--->B---->C--->D---->G--->H--->E----
>F---->I---->K
BFS PYTHON Program
from collections import deque

def bfs(graph, start):

visited = [] # List to keep track of visited
nodes
queue = deque([start]) # Initialize a queue with the start
node

while queue:
node = [Link]() # Dequeue the front node
if node not in visited:
[Link](node) # Mark it as visited
print(node, end=" ") # Process the node (print or
store)

# Enqueue all unvisited neighbors

for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)
return visited
Applications of BFS:
• Finding the shortest path in an unweighted graph
• Web crawlers and network broadcasting
• Social networking sites (finding shortest connection path)
• AI and Game algorithms (finding minimum moves)
• Tree traversal (level-order traversal)
Key Properties of BFS:

Property Description
Search Type Uninformed (Blind) Search
Uses Queue
Completeness ✅ Yes (if branching factor is finite)
Optimality ✅ Yes (if all edges have equal cost)
O(b^d), where b = branching factor, d = depth of the
Time Complexity
goal
Space Complexity O(b^d)
Advantages:
• BFS will provide a solution if any solution exists.
• If there are more than one solutions for a given
problem, then BFS will provide the minimal solution
which requires the least number of steps.
Disadvantages:
• It requires lots of memory since each level of the tree
must be saved into memory to expand the next level.
• BFS needs lots of time if the solution is far away from
the root node.
2. Depth-first Search
Depth-First Search explores a graph as deep as possible along each branch
before backtracking.
It uses a Stack (LIFO) data structure — either explicitly (with a list) or implicitly
through recursion.
• Depth-first search isa recursive algorithm for traversing a tree or graph data
structure.
• It is called the depth-first search because it starts from the root node and
follows each path to its greatest depth node before moving to the next path.
• DFS uses a stack data structure for its implementation.
• The process of the DFS algorithm is similar to the BFS algorithm.
Example: Root node--->Left node ----> right node.
 Python Program DFS
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
# Mark the current node as visited
[Link](node)
print(node, end=" ") # Process the
node (print or store)
# Visit all unvisited neighbors
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)

# Example Graph (Adjacency List)

graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': []
}

print("Depth-First Search Traversal:")

dfs(graph, 'A')
Depth-First Search Traversal: A B D E C F
Key Properties of DFS:

Property Description
Search Type Uninformed (Blind) Search
Data Structure Used Stack (LIFO) or Recursion
❌ Not always (can get stuck in infinite loops on cyclic
Completeness
graphs)
Optimality ❌ No (doesn’t guarantee shortest path)
Time Complexity O(V + E) — where V = vertices, E = edges
Space Complexity O(V) — due to recursion/stack
Advantage:
• DFS requires very less memory as it only needs to store
a stack of the nodes on the path from root node to the
current node.
• It takes less time to reach to the goal node than BFS
algorithm (if it traverses in the right path).
Applications of DFS
• Pathfinding in AI and games
• Detecting cycles in a graph
• Topological sorting in Directed Acyclic Graphs (DAGs)
• Finding connected components in a graph
• Solving puzzles/mazes (e.g., N-Queens, Sudoku)
• Web crawling and network analysis
Disadvantage:
• There is the possibility that many states keep re-
occurring, and there is no guarantee of finding the
solution.
• DFS algorithm goes for deep down searching and
sometime it may go to the infinite loop.
DFS vs BFS (Quick
Comparison)

Feature DFS BFS

Level-wise (explore all neighbors
Approach Depth-wise (go deep first)
first)
Data Structure Stack / Recursion Queue
Completeness No Yes
Optimality No Yes (for equal-cost paths)
Memory Usage Low High
Graph is deep; solution may be Graph is broad; solution is near
Best Used When
far root
3-Depth-Limited Search Algorithm:
• A depth-limited search algorithm is similar to depth-first
search with a predetermined limit.
• Depth-limited search can solve the drawback of the infinite
path in the Depth-first search. In this algorithm, the node at
the depth limit will treat as it has no successor nodes further.
• Depth-limited search can be terminated with two Conditions
of failure:
• Standard failure value: It indicates that problem does not have
any solution.
• Cutoff failure value: It defines no solution for the problem within a
given depth limit.
Example:
Advantages:
• Depth-limited search is Memory efficient.
Disadvantages:
• Depth-limited search also has a disadvantage of
incompleteness.
• It may not be optimal if the problem has more than one
solution.
Properties
• Completeness: DLS search algorithm is complete if the
solution is above the depth-limit.
• Time Complexity: Time complexity of DLS algorithm
is O(bℓ).
• Space Complexity: Space complexity of DLS algorithm
is O(b×ℓ).
• Optimal: Depth-limited search can be viewed as a
special case of DFS, and it is also not optimal even if
ℓ>d.
 Informed Search Algorithms
• The informed search algorithm is more useful for large
search space.
• Informed search algorithm uses the idea of heuristic, so
it is also called Heuristic search.
What is a Heuristic
Search?

Search with partial Information

 What is a Heuristic Search?
• A Heuristic is a technique to solve a problem faster
than classic methods, or to find an approximate
solution when classic methods cannot.
A Heuristic (or a heuristic function) takes a look at
search algorithms. At each branching step, it
evaluates the available information and makes a
decision on which branch to follow.

10+20+10=40
Informed Search
[Link] Best First Search
2.A* Search
Greedy Best First Search
• Greedy best-first search algorithm always selects the
trail which appears best at that moment.
• Within the best first search algorithm, we expand the
node which is closest to the goal node and therefore
the closest cost is estimated by heuristic function.
• This sort of search reliably picks the way which
appears best by then.
• It is the blend of BFS and DFS. It uses heuristic limit
and searches. The BFS grants us to take the
advantages of the two estimations.
Find the path from S to G using greedy
search. The heuristic values h of each node
below the name of the node.
 Solution
Starting from S, we can traverse to A(h=9) or D(h=5).

We choose D, as it has the lower heuristic cost.

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.
S -> D -> E -> G
Python Program Refer Python File
• Advantage: Works well with informed search problems,
with fewer steps to reach a goal.

• Disadvantage: Can turn into unguided DFS in the

worst case.
A* Algorithm
• A * algorithm is a searching algorithm that searches
for the shortest path between the initial and the
final state. It is used in various applications, such
as maps.
• A* Algorithm is one of the best and popular techniques used
for path finding and graph traversals.
• A lot of games and web-based maps use this algorithm for
finding the shortest path efficiently.
• It is essentially a best first search algorithm.
In A* search algorithm, we use search heuristic as
well as the cost to reach the node. Hence we can
combine both costs as following, and this sum is
called as a fitness number.
Heuristic: The following points should be noted wrt heuristics in A*
search.
•Here, h(x) is called the forward cost and is an estimate of the distance
of the current node from the goal node.
•And, g(x) is called the backward cost and is the cumulative cost of a
node from the root node.
•A* search is optimal only when for all nodes, the forward cost for a node
h(x) underestimates the actual cost h*(x) to reach the goal. This property
of A* heuristic is called admissibility.
Admissibility:
Strategy: Choose the node with the lowest f(x) value.
Find the path to reach from S to G
using A* search.
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
Cost: 7
Refer Python file
Find the path distance ?

SCDEG=17
Comparison with A*

Feature Greedy Best-First A*

Evaluation f(n) = h(n) f(n) = g(n) + h(n)
Optimal ❌ No ✅ Yes (if h admissible)
Completeness ❌ No ✅ Yes
Memory Lower Higher
Focus Speed Accuracy
 Part-2 (Unit-2)
Adversarial search
1997 chess match between world champion
Garry Kasparov and IBM computer “Deep Blue”
Adversarial search
• Adversarial search is a search, where we examine
the problem which arises when we try to plan
ahead of the world and other agents are planning
against us.
Examples: Chess, business, trading, war.
You change state, but then you don't control the
next state.
Opponent will change the next state in a way:
[Link]
[Link] to you
• Searches in which two or more players
with conflicting goals are trying to
explore the same search space for the
solution, are called adversarial
searches, often known as Games.
• The algorithms used are
• MiniMax
• Alpha Beta Pruning
Minimax
• The Minimax algorithm tries to predict the opponent's
behaviour. It predicts the opponent will take
the worst action from our viewpoint.
• We are MAX - trying to maximize our score / move to
best state.
• Opponent is MIN - tries to minimize our score / move
to worst state for us.
• Mini-max algorithm is a recursive or backtracking algorithm
which is used in decision-making and game theory. It
provides an optimal move for the player assuming that
opponent is also playing optimally.
• In this algorithm two players play the game, one is called
MAX and other is called MIN.
• The minimax algorithm proceeds all the way down to the
terminal node of the tree, then backtrack the tree as the
recursion.
Working of Min-Max Algorithm:
Step:1
 •For node D max(-1, -∞) =>
max(-1,4)= 4
Step 2: •For Node E max(2, -∞) =>
max(2, 6)= 6
•For Node F max(-3, -∞) =>
max(-3,-5) = -3
•For node G max(0, -∞) =
max(0, 7) = 7
 •For node B= min(4,6) =

Step:3 4
•For node C= min (-3, 7)
= -3
 •For node A max(4, -
Step 4: 3)= 4
Properties of Mini-Max algorithm:

• Complete- Min-Max algorithm is Complete. It will

definitely find a solution (if exist), in the finite search
tree.
• Optimal- Min-Max algorithm is optimal if both
opponents are playing optimally.
• Time complexity- As it performs DFS for the game-
tree, so the time complexity of Min-Max algorithm
is O(bd), where d is branching factor of the game-tree,
and m is the maximum depth of the tree.
• Space Complexity- Space complexity of Mini-max
algorithm is also similar to DFS which is O(bd).
Limitation of the minimax
Algorithm:
• The main drawback of the minimax algorithm is that it
gets really slow for complex games such as Chess, go,
etc. This type of games has a huge branching factor,
and the player has lots of choices to decide.
• This limitation of the minimax algorithm can be
improved from alpha-beta pruning which we have
discussed in the next topic.
 Alpha-Beta Pruning
• Alpha-beta pruning is a modified version of the minimax
algorithm. It is an optimization technique for the
minimax algorithm.
• There is a technique by which without checking each
node of the game tree we can compute the correct
minimax decision, and this technique is called pruning.
This involves two threshold parameter Alpha and beta
for future expansion, so it is called alpha-beta
pruning. It is also called as Alpha-Beta Algorithm.
• Alpha-beta pruning can be applied at any depth of a
tree, and sometimes it not only prune the tree leaves
but also entire sub-tree.
• The two-parameter can be defined as:
• Alpha: The best (highest-value) choice we have found so far
at any point along the path of Maximizer. The initial value of
alpha is -∞.
• Beta: The best (lowest-value) choice we have found so far at
any point along the path of Minimizer. The initial value of beta
is +∞.
Alpha-Beta Pruning