Advanced

Analysis of
Algorithm
LECTURE: SEARCH ALGORITHMS IN ARTIFICAL
INTELLEGENCE
INSTRUCTOR: DR . HUSNAIN ASHFAQ
Tree
Tree can be defined as a collection of entities
(nodes) linked together to simulate a
hierarchy.
 Hierarchy of a
University Example
Reactor

Dean Dean Dean Dean

HOD HOD HOD HOD HOD HOD HOD

F F F F F F F F F F F F F
 Terminology in Trees
Node: The elements of the trees are called nodes.
Root: The node which is not having any parent is called root node of the tree ( top most element/node).
Parent node: The immediate predecessor of a node is known as parent node.
Child node: The immediate successor of a node is known as child node.
Leaf node: A node which does not any child is known as leaf node. They are also called external node.
Path: Sequence of consecutive edges from source node to destination node
Ancestors: Any predecessor node on the path from root to that node
Descendant: Any successor node on the from that node to leaf node
Sub-tree: The sub-tree of any tree (T) is which is containing a node of a tree (t) and all
its descendant.
Depth of node: Length of path from root to that node is known as depth of a node. Or
in simple terms its number of edges from root to that node.
Level of a node: The distance from root to the given node. Or you can say each
hierarchy is known as level. Level of node is always equal to depth of a node. And Level
of a tree is equal to height of a tree.
 Graphs
A graph is a collection of nodes (also called vertices) and edges
that connect pairs of nodes.

Key Components of a Graph

[Link] (Nodes): These represent entities or points in the
graph.
[Link] (Links): These represent connections or relationships
between vertices. An edge connects two vertices.
Graphs
A graph is a pair: G = (V, E) Han Luke
A set of vertices, also known
as nodes: V = {v1,v2,…,vn} Leia

A set of edges E = {e1,e2,…,em}

◦ Each edge ei is a pair of vertices (vj,vk) V = {Han,Leia,Luke}
E = {(Luke,Leia),
(Han,Leia),
◦ An edge "connects" the vertices
(Leia,Han)}
Graphs can be directed or undirected
Problem Solving Agents
A problem-solving agent is an intelligent agent in Artificial
Intelligence (AI) that decides what actions to take in order
to reach a specific goal. It does this by formulating
problems and searching for solutions through a series of
logical steps.
8 Puzzle Problem
Problem-solving agents:

In Artificial Intelligence, Search techniques are

universal problem-solving methods.
Rational agents or Problem-solving
agents in AI mostly used these search
strategies or algorithms to solve a specific
problem and provide the best result.
Problem-solving agents are the goal-based
agents.
Searching Strategies in AI

Applications of Searching Strategies

Definition: Searching strategies find applications in robotics, natural language processing, planning, and
optimization.
Important Points:
- Robotics: Path planning, localization, and navigation.
- Natural Language Processing: Information retrieval, question answering, and text summarization.
- Planning and Optimization: Resource allocation, scheduling, and logistics.
Search Algorithm Terminologies:

1. 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.

2. 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.
3. Actions: It gives the description of all the available actions to the agent.
4. Transition model: A description of what each action do, can be represented as a transition
model.
5. Path Cost: It is a function which assigns a numeric cost to each path.
6. Solution: It is an action sequence which leads from the start node to the goal node.
7. Optimal Solution: If a solution has the lowest cost among all solutions.
Properties of Search Algorithms

Following are the four essential properties of search algorithms to compare

the efficiency of these algorithms:
1. 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.
2. 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.
3. Time Complexity: Time complexity is a measure of time for an algorithm
to complete its task.
4. 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

UN
Conversion of graph into tree

A B C

S G

D E F

18
Conversion of graph into tree

Node Explore
S A, D
A S,B,D
B A,C,E
C B
D S,A,E
E B,D,F
F E,G
G F
Conversion of graph into tree
Searching Strategies in AI

Uninformed Search
Definition: Explores the state space systematically without any knowledge about the
goal's location. Relies solely on the problem definition (start and goal states).
Important Points:
● Explores all possible paths in a predefined order/It explores the search space in a
brute-force manner, relying only on traversal rules and goal identification.
● Can be slow and resource-intensive for problems with large state spaces.
● Guaranteed to find a solution if one exists (for complete search algorithms like
Breadth-First Search).
Uninformed/Blind Search:

Uninformed search, also known as blind search, operates

without domain-specific knowledge, such as goal location or
closeness.
It explores the search space in a brute-force manner, relying
only on traversal rules and goal identification.
These algorithms systematically examine each node without
any heuristic guidance, ensuring a thorough but potentially
inefficient search.
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.
BFS-Algorithm
1. Enter starting node in Queue.
2. If Queue is empty then return fail and stop.
3. If first element in the Queue is goal node then return success and stop.
4. Else remove and expand first element from Queue and place it’s child in the end of the
Queue.
5. Go to step 3.
Example
Time Complexity in BFS
BFS explores the tree level by level, meaning it visits all nodes at one level before moving to the next.
Suppose each node has b children (branching factor).
The shallowest goal node is found at depth d.
The total number of nodes BFS visits before reaching depth d is:
T(b) = 1 + b + b2 + b3 + ... + bd
This forms a geometric series, and in Big-O notation, we express it as:
O(bd)
Example:
 If each node has b = 2 children (binary tree) and the goal is at depth d = 5,
 The number of nodes BFS explores is roughly:
 1 + 2 + 4 + 8 + 16 + 32 = 63 = O(25)
 As depth d increases, the number of explored nodes grows exponentially.
Space Complexity of BFS
•BFS keeps track of all the nodes at the current level before moving to the next level.
•At depth d, there are about bd nodes in the worst case.
•The amount of memory BFS needs is proportional to the number of nodes at the last level:
•O(bd)
•Example:
• If each node has b = 2 children and the search depth is d = 5,
• The last level contains bd = 25 = 32 nodes, meaning we need memory to store 32 nodes at once.
• This makes BFS memory-intensive compared to other search algorithms like DFS.
Completeness of BFS
•BFS is guaranteed to find a solution if one exists.
•Since it searches level by level, it always finds the shallowest (nearest) goal node first.
•Example:
• Imagine searching for a name in a family tree.
• BFS will check parents first, then children, then grandchildren, etc.
• If the person you are looking for is at level 3, BFS will not skip it and will find it as soon as it reaches
level 3.

BFS is complete! It will always find the goal if there is a solution.

Optimality of BFS
•BFS is optimal if the path cost is a non-decreasing function of depth.
•This means if all step costs are equal, BFS always finds the shortest path first.
•Example:
• Consider a road network where every road segment has an equal cost (e.g., every road is 1 km long).
• BFS finds the shortest path in terms of the fewest number of roads because it finds the goal at the
shallowest depth.
• However, if roads have different lengths (e.g., some are highways, some are small streets), BFS may
not be optimal because it does not consider cost.

BFS is optimal if all steps have equal cost!

Advantages:

1. BFS will provide a solution if any solution exists.

2. 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.
3. It also helps in finding the shortest path in goal state,
since it needs all nodes at the same hierarchical
level before making a move to nodes at lower levels.
Disadvantages:

1. It requires lots of memory since each level of

the tree must be saved into memory to
expand the next level.
2. BFS needs lots of time if the solution is far
away from the root node.
3. It can be very inefficient approach for
searching through deeply layered spaces, as it
needs to thoroughly explore all nodes at each
level before moving on to the next
DFS in AI

Introduction to Depth-First Search (DFS) in Artificial Intelligence

Definition: Depth-First Search (DFS) is a fundamental graph traversal algorithm used in artificial
intelligence to systematically explore and search through all nodes of a graph or tree structure.
Unlike Breadth-First Search (BFS), DFS explores as far as possible along each branch before
backtracking.

Important Points:
1. DFS explores nodes by going as deep as possible along each branch before backtracking.
2. It starts at the root node and explores as far as possible along each branch before backtracking.
3. DFS uses a stack data structure to keep track of the nodes to be explored.
4. This algorithm is often used in maze solving, topological sorting, and solving puzzles.
DFS in AI
Concept:
Imagine navigating a maze again. This time, DFS would be like taking a single turn at every intersection and following that
path all the way until you hit a dead end. If you don't find the exit there, you backtrack and try the next turn at the previous
intersection.
Algorithm:
1. Initialization: We choose a starting node (usually the root node) and typically use a Stack (Last-In-First-Out) data
structure.
2. Push and Mark: We push the starting node onto the Stack and mark it as visited.
3. Pop and Explore: We remove (pop) the top node from the Stack.
4. Unvisited Neighbor?
○ If the popped node has any unvisited neighbors, we choose one and push it onto the Stack, followed by
marking it as visited.
○ We repeat steps 3 and 4 until the popped node has no unvisited neighbors.
5. Backtrack: If the popped node has no unvisited neighbors (dead end), we've reached the end of a path. We backtrack
by discarding this node from consideration.
6. Repeat: We repeat steps 3-5 until the Stack is empty, signifying all reachable paths have been explored.
DFS in AI
DFS in AI
Key Points:
● DFS is not guaranteed to find the shortest path. It explores one path deeply first,
potentially missing closer solutions on other branches.
● DFS can be memory-efficient compared to BFS because it typically explores one
path at a time, requiring less storage for multiple levels.
● DFS is a good choice for problems where the goal is likely located at a deeper
level in the search space.
DFS in AI

Applications and Limitations of DFS

Important Points:
1. DFS is commonly used in applications like maze solving, where deep exploration is necessary.
2. It is also useful for topological sorting of graphs and solving puzzles like Sudoku.
3. However, DFS may not always find the optimal solution and can be inefficient in large graphs.
DFS in AI
Comparison Between DFS and BFS

Important Points:
1. DFS explores deep before going wide, while BFS explores wide before going deep.
2. DFS uses less memory compared to BFS.
3. BFS guarantees finding the shortest path in an unweighted graph, while DFS does not.
4. Each algorithm has its strengths and weaknesses, and the choice depends on the
specific problem and requirements.
DFS in AI
Advantages:
● Fast for Deep Solutions: If the goal state lies along a deep path in the search space,
DFS can find it quickly. It prioritizes exploring one path entirely, potentially reaching
the goal faster than algorithms that explore all paths at a similar depth.

● Lower Memory Requirements: Compared to Breadth-First Search (BFS), DFS

generally requires less memory. It focuses on a single path at a time, reducing the
need to store information about all possible paths at a specific depth.

● Can be Suitable for Finding Any Solution: In some scenarios, finding any solution
quickly might be more important than finding the optimal one. DFS can be useful in
such cases, as it explores paths efficiently until it finds a goal state.
DFS in AI
Disadvantages:
● Not Guaranteed Optimal Solution: DFS prioritizes depth over breadth, and it might get
stuck in deep, non-optimal paths. It explores one path entirely before considering
alternatives, potentially missing shorter paths to the goal.

● Completeness Issues (Potential Infinite Loops): In some cases, DFS might fall into infinite
loops, especially in problems with cycles (repetitive state transitions). It might keep
exploring the same path repeatedly without finding a way out.

● Potential for Inefficient Exploration: DFS might explore many irrelevant states before
finding the goal, especially if the goal is located far away in the search space. It can be
inefficient for problems with branching search spaces (many possible actions from each
state).
DFS in AI
When to Use DFS:
● When finding a solution quickly is more important than finding
the optimal one (e.g., escaping a maze in a game).
● When memory limitations are a concern, and the state space is
not massive.
● As a preliminary search to identify promising areas in the
search space for further exploration with other algorithms.
DFS in AI

● Space Complexity = O(b*d)

● Time Complexity = O(bd)

b = branching factor (number of child nodes per state)

d = depth of the deepest solution
UCS in AI

Definition
- Uniform Cost Search (UCS) is an uninformed search algorithm
utilized in artificial intelligence to find the lowest-cost path from
a starting node to a goal node in a weighted graph.
UCS in AI

Key Points
-Objective: The goal is to path finding to goal node with lowest comulative cost.
Cost-Based Exploration: UCS prioritizes nodes based on their cumulative path cost from the start node.
- Optimality: UCS guarantees finding the optimal solution in terms of cost, assuming non-negative edge
costs.
- Queue-Based Implementation: UCS typically employs a priority queue to efficiently select and expand
nodes with the lowest cost.
- Weighted Graphs: UCS is suitable for solving problems in weighted graphs where each edge has an
associated cost.
UCS in AI

Algorithm Initialization
- Start with the initial node as the current node.
- Set up an empty priority queue to store nodes to be explored, with
priority based on the cumulative path cost from the start node.
UCS in AI
Exploration
- Continue exploring until the priority queue is empty.
- Dequeue the node with the lowest cumulative path cost from the priority
queue. This node becomes the current node for exploration.
- If the current node is the goal node, terminate the search and return the
solution.
- Otherwise, expand the current node by generating its neighboring nodes.
UCS in AI

Exploration (continued)
- For each neighboring node:
- Calculate the total cost from the start node to the neighboring node.
- If the neighboring node has not been visited or if the new total cost is lower than the existing
cost, update the cost and add the neighboring node to the priority queue with its priority
based on the new total cost.
Termination
- If the priority queue becomes empty without finding the goal node, terminate the search and conclude that there is
no solution.
Output
- If a solution is found, output the lowest-cost path from the start node to the goal node.
Example

1 S
4
A B
3 2
5
C
D
5 3
4 G Priority queue (sort it with
E
minimum cost min heap)
F G
5
s
G

Visited Node
Example

1 S
4
A B
3 2
5
C
D
5 3
4 G Priority queue (sort it with
E minimum cost min heap)
F G
5
A B
G

s Visited Node
Example

1 S
4
A B
3 2
5
C
D
5 3
4 G Priority queue (sort it with
E minimum cost min heap)
F G
5
D B C
G

s A Visited Node
Example

1 S
4
A B
3 2
5
C
D
5 3
4 G Priority queue (sort it with
E minimum cost min heap)
F G
5
B C G F
G

s A D Visited Node
Example

1 S
4
A B
3 2
5
C
D
5 3
4 G Priority queue (sort it with
E minimum cost min heap)
F G
5
C G F G
G

s A D B Visited Node
Example

1 S
4
A B
3 2
5
C
D
5 3
4 G Priority queue (sort it with
E minimum cost min heap)
F G
5
G F G E
G

s A D B C Visited Node
Example

1 S
4
A B
3 2
5
C
D
5 3
4 G Priority queue (sort it with
E minimum cost min heap)
F G
5
F G E
G

s A D B C G Visited Node
Example
Goal is found and the program will terminate.
1 S
4 The path is not the visited nodes
A B
3 2 To find the path see the visited node and only
consider those nodes in path which are
C 5 directly linked in this case S->A->D->G =6
D
5 3
4 G Priority queue (sort it with
E minimum cost min heap)
F G
5
F G E
G

s A D B C G Visited Node
Properties of UCS
● It is complete and optimal
● Time and space complexity of UCS is:

O(b(1+(C* / Є ))
Where b = branch factor
C*= optimal path cost from source to goal node
Є = Least cost of the edge in a tree
UCS in AI
Applications
- Route Planning: UCS can find the shortest and least expensive route
between locations in transportation networks.
- Resource Allocation: UCS optimizes resource allocation by minimizing costs
in project scheduling and task assignment.
- Navigation Systems: UCS powers navigation systems to calculate cost-
effective routes based on factors like distance and time.
UCS in AI

Considerations
- Edge Costs: UCS assumes non-negative edge costs and may produce
incorrect results with negative edge costs.
- Memory Usage: UCS may consume more memory due to storing path costs
for each node.
- Complexity: UCS can have high time complexity, especially in graphs with
many nodes or high-cost paths.
UCS in AI
Advantages:
● Guaranteed Optimality (with Uniform Costs): If a solution exists in a problem with
uniform costs (where all actions have the same cost or the cost only depends on the
current state), UCS is guaranteed to find the path with the minimum total cost. This
makes it ideal for scenarios where minimizing overall cost is crucial.
● Completeness: UCS explores all reachable states in the search space systematically. This
ensures it will eventually find a solution if one exists, as long as the search space is finite.
● Ease of Implementation: The core concept of UCS is relatively straightforward, making it
easier to implement compared to some other search algorithms.
UCS in AI
Disadvantages:
● Potential Slowness for Uneven Costs: While UCS guarantees optimality with uniform costs, it can be
slow for problems with uneven costs (where some actions are significantly more expensive than
others). It might explore many expensive paths before finding a cheaper one that leads to the goal.
● Getting Stuck in Loops or Irrelevant Paths: In some cases, UCS might get stuck in loops or explore
irrelevant paths with equal costs. This can happen if the problem has cycles (repetitive state
transitions) or many states with the same cost that don't lead efficiently to the goal.
● Memory Intensiveness for Large State Spaces: UCS can become memory-intensive for problems with
very large state spaces. As it explores all reachable states systematically, it needs to store information
about all these states during the search process.
UCS in AI ( Example Class Activitiy ) V6 is goal
UCS in AI ( Example Class Activitiy ) A si starting point and G is goal
Example class Activity Z is goal
Depth Limited Search (DLS)
DLS in AI
DLS in AI
Introduction
● Depth-Limited Search (DLS) is a variant of Depth-First
Search (DFS), which imposes a depth limit on the
exploration of the search tree.
● Unlike DFS, which can potentially traverse infinitely
deep paths, DLS restricts the search to a specified
depth level.
DLS in AI
Algorithm
● Initialization: Start at the root node and set the depth limit.
● Exploration: Explore each branch of the tree recursively, but
stop when the depth limit is reached.
● Termination: If a goal node is found within the depth limit,
return the solution. Otherwise, backtrack to the previous level
and continue exploration.
Example
DLS in AI
Key Points
● Depth Limit: DLS imposes a depth limit on the search,
preventing it from exploring paths beyond a certain depth.
● Memory Efficiency: Compared to DFS, DLS is more
memory-efficient as it limits the number of nodes stored in
memory.
● Completeness and Optimality: DLS may not be
complete or optimal, especially if the solution lies beyond
the depth limit.
DLS in AI
Applications
● DLS is commonly used in scenarios where infinite depths are not
feasible or practical, such as game tree search, web crawling, or
puzzle-solving.
● It is particularly useful in scenarios where the search space is
vast, and exploring infinitely deep paths is impractical or
unnecessary.
DLS in AI
Considerations
● Depth Limit Selection: The choice of depth limit influences
the effectiveness of DLS. Too shallow a limit may miss the
solution, while too deep a limit may lead to excessive memory
usage.
● Performance Trade-offs: DLS trades completeness and
optimality for efficiency and reduced memory usage. Careful
consideration is needed to balance these trade-offs based on
the specific problem domain.
DLS in AI
Advantages
● Controlled Memory Usage: DLS limits the number of nodes stored in memory,
making it more memory-efficient compared to uninformed search algorithms like
Depth-First Search (DFS).
● Efficient Exploration: By restricting the search to a specified depth limit, DLS
can efficiently explore large search spaces without getting trapped in infinitely
deep paths.
● Practicality: DLS is practical in scenarios where exploring infinitely deep paths is
not feasible or necessary, such as game tree search or web crawling.
DLS in AI
Disadvantages
● Completeness: DLS may not find a solution even if one exists beyond the
depth limit. This lack of completeness can be a significant drawback,
especially in scenarios where the solution lies deeper in the search space.
● Optimality: Due to its depth-limiting nature, DLS may not always find the
optimal solution. It might terminate prematurely without exploring
potentially better solutions beyond the depth limit.
● Dependence on Depth Limit: The effectiveness of DLS heavily depends
on the selection of an appropriate depth limit. Choosing a limit too shallow
may result in missing the solution, while a limit too deep may lead to
excessive memory usage and performance issues.
Comparison of DFS and DLS
Feature Depth-First Search (DFS) Depth-Limited Search (DLS)
Definition Explores as far as possible along a branch DFS with a predetermined depth limit to
before backtracking. avoid going too deep.

Completeness Not complete (fails on infinite or deep Complete if the solution is within the
graphs). depth limit. Otherwise, incomplete.

Optimality Not optimal. Not optimal.

O(b^m) O(b^l)
Time Complexity where b is branching factor and m is max where l is the depth limit.
depth.

Space Complexity O(m) (linear in depth of tree). O(l) (linear in depth limit).

Key Limitation Can get stuck in infinite branches. Might miss solutions beyond depth limit.

Use Case Useful when the solution is deep and Useful when max depth of solution is
memory is limited. known or to avoid infinite loops.
Iterative Deepening Depth-First
Search (IDDFS)
DFS and BFS algorithms are combined in the iterative deepening algorithm.
This search algorithm determines the best depth limit by gradually increasing
it until a goal is discovered.
This algorithm searches in depth first up to a certain "depth limit," then
increases the depth limit after each iteration until the goal node is found.
This search algorithm combines the speed of breadth-first search with the
memory efficiency of depth-first search.
When the search space is large and the depth of the goal node is unknown,
the iterative search algorithm is useful for uninformed search.
IDS in AI
Algorithm
● Initialization: Start with a depth limit of 0.
● Iteration: Perform DFS with increasing depth limits, starting from 0 and
incrementing by 1 in each iteration.
● Exploration: Explore the search space until the goal node is found or
until the maximum depth limit is reached.
● Termination: If the goal node is found, return the solution. If the
maximum depth limit is reached, increment the depth limit and repeat
the process.
Characteristics of IDDFS
Completeness: Yes (if branching factor is finite)
Optimality: Yes (for uniform cost)
Time Complexity: O(b^d) (IDDFS has a time complexity
similar to DFS but with a slightly higher constant factor due
to multiple iterations).

Space Complexity: O(bd)

IDDFS
IDDFS is a hybrid search technique.
Useful when goal depth is unknown.
Offers completeness, optimality, and low memory usage.
Applications
Games (e.g., chess)
Problem-solving agents
Robotics navigation
Informed Search Algorithm
Informed Search, also known as Heuristic Search, is a type of search algorithm in Artificial
Intelligence (AI) that uses additional information (heuristics) about the problem to make better
decisions and find solutions more efficiently than uninformed (or blind) search strategies.
Instead of searching blindly, informed search estimates the cost or distance to the goal from a
given state, allowing the search to focus on promising paths.

Heuristic Search Tries to optimize using heuristic function.

Means it tries to solve the problem either in minimum
number of steps or cost.
 Informed Search Algorithm
Evaluation Function
Informed search algorithms use an evaluation function f(n) to determine the
"promise" of a node.

An evaluation function, denoted as f(n), is used by informed search algorithms to determine the
order in which nodes are expanded.

It assigns a numerical value to each node n, estimating how promising that node is in leading to
the goal.

The lower the value, the more attractive the node.

Best-First Search
Best-First Search (BFS) is a general search algorithm that uses a priority queue and selects the
most promising node to expand based on a given Evaluation function.
Best-First Search has several variants depending on the evaluation function used some of them
are:
1. Uniform Cost Search Algorithm (Uninformed Search: no knowledge about goal)
2. Greedy best First Search Algorithm
3. A*
Heuristic Function
Heuristic Function h(n) function estimates the cost
(distance) from the current state (n) to the goal state.

It helps in selecting optimal node for expansion. Means

they provide a measure of optimism about a state and
aid in avoiding unecessary expploration of unpromising
paths. This ensures that the search process is not only
targeted but also efficient.
Need For Heuristic Function
In vast landscape of problem spaces, blind
exploration is often impractical. This is where
heuristic function comes into play. (for example in 8
puzzle problem or chess game etc)
They provide a way for AI systems to make informed
decisions about which paths to be explored based on
heuristic evaluations.
Types of Heuristic Function
Admissible Heuristic function: In this the heuristic function
never overestimate the cost of reaching the goal. Means
h(n) always less than or equal to actual cost of lowest-cost
path from n node to goal node.
Non-Admissible Heuristic Function: In this the heuristic
function overestimate the cost of reaching the goal. Means
h(n) always greater than to actual cost of lowest-cost path
from n node to goal node.
Different Methods to calculate
Heuristic Function
These are designed based on expert knowledge of the problem.
Examples:
1. Manhattan Distance: For grid-based problems (like puzzles,
games, or robot movement on a 2D grid). h(n)=∣x1​−x2​∣+∣y1​−y2​∣
2. Euclidean Distance (straight Line distance): For continuous
spaces (e.g., GPS, robotics).
h(n)=
Missed Tiles in 8 Puzzle Games
Greedy Best-first Search(GBFS)
Greedy Best-first search algorithm is a search
algorithm that uses a heuristic function (value)
as an evaluation function to explore the
possible node which will lead to goal
f(n) = h(n)
 Greedy Best First Search
Visualizing GBFS:
● Imagine you're lost in a maze and want to find the exit.
● A perfect heuristic function would tell you the exact distance and direction to the exit from any point
in the maze.
● GBFS uses an estimated distance function (heuristic) to choose the path that seems closest to the exit
at each junction.
● While it might not always take the optimal path, it usually gets you to the exit efficiently.
Difference Between UCS and GBFS

UFS uses actual cost while GBFS uses heuristic cost

Actual Cost and Heuristic Cost:

● Actual Cost (g(x)): This represents the actual cost incurred to reach the current state (x) from the
starting state. It's calculated by summing up the costs of the transitions taken so far in the search
process.
● Heuristic Cost (h(x)): This is an estimate of the cost remaining to reach the goal state from the current
state (x). It's provided by the heuristic function, and its accuracy significantly impacts GBFS's
performance.
Algorithm of GBFS

1. Initialization:
● Start with initial node as current node
● Create an open list (priority queue) to stores the nodes that are possible candidates for exploration.
Initially, this list contains only start node.
● Create a closed list (visited node list) to keep the track of nodes that have already been explored
● Compare the current node with goal node if it is goal node then terminate else deque it ( add it into
closed list) and explore its children.
2. Select the next node:
● Once you dequeue the current node next step is add its children into open list (priority queue).
However in GBFS we add children based on heuristic value.
● Once you add it then arrange the open list in ascending order (based on heuristic value).
● After sorting in ascending order, the node at front of the queue will be your next node if it is already
not in the closed list (visited list).
Example
Node h(n)
C 6
B 6
T 7
O 4
E 6
P 7
A 8
R 7
S 6
I 2
N 3
G 8
L 9
F 8
3
G
5
Node h(n)
C 5
B 3
A 2
G 1
Z 0
O 7
I 6
Example 3
Greedy Best First Search

Optimality:

● Not Optimal: This is a crucial aspect of GBFS. Unlike A search, GBFS cannot guarantee finding
the shortest path (optimal solution) to the goal state.

● Local Optima Trap: The heuristic function (h(x)) can be misleading. It might guide GBFS
towards states that seem promising based on the estimated distance (h(x)) but are actually not on the
optimal path. These "dead ends" are called local optima. GBFS can get stuck in these loops, missing
the actual optimal solution.
Greedy Best First Search

Completeness:

● Generally Incomplete: GBFS is not guaranteed to find a solution even if

one exists in the search space. This depends on the specific problem and the
quality of the heuristic function.
● Infinite Loops: A poorly designed heuristic or a complex search space with
many local optima can lead GBFS down an infinite loop, continuously
exploring paths that never reach the goal.
Greedy Best First Search
● Time Complexity:
● Generally Faster than Uninformed Search: Compared to uninformed search algorithms (BFS, DFS),
GBFS usually explores fewer unnecessary paths because of the heuristic's guidance. This can
significantly improve time complexity, especially for problems with a large branching factor (many
options at each step).
● Heuristic Quality Impact: The quality of the heuristic function significantly impacts time complexity. A
good heuristic that accurately estimates the distance to the goal will lead to a faster search. Conversely,
a poor heuristic might extend the exploration time by guiding GBFS down less promising paths.
● Worst-Case Scenario: In the worst case, if the heuristic is misleading and there are many local optima,
GBFS can exhibit exponential time complexity similar to uninformed search algorithms.
● Worst-case time complexity of GBFS is:
• O(bm)
• Because GBFS does not guarantee finding the shortest path and may explore deep paths due to
misleading heuristics.
• In the worst case (bad heuristic), it behaves like an uninformed search such as DFS or BFS.

● Best case (good heuristic): It can be significantly better if the heuristic is highly accurate, possibly
closer to:
● O(bd)
● But this is optimistic and depends entirely on the heuristic.

Where m is maximum depth of a search state

d = depth of the shallow solution

102
Greedy Best First Search

Space Complexity:
Similar to BFS: GBFS typically has a space complexity comparable to Breadth-First Search (BFS). This is
because, like BFS, GBFS might need to store information about multiple nodes at the same "frontier" (the
set of unexpanded nodes) during the exploration process. This can be significant for problems with a large
branching factor and a deep search space (goal is far from the starting point).
A* Algorithm

● ‘n’ is the last node on the path

● g(n) is the cost of the path from start node to node ‘n’
● h(n) is a heuristic function that estimates cost of the cheapest path from node ‘n’ to the goal node
A* Algorithm
A* Algorithm
● 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.
A* Algorithm

A Algorithm works as

● It maintains a tree of paths originating at the start node.

● It extends those paths one edge at a time.
● It continues until its termination criterion is satisfied.
A* Algorithm

● ‘n’ is the last node on the path

● g(n) is the cost of the path from start node to node ‘n’
● h(n) is a heuristic function that estimates cost of the cheapest path from node ‘n’ to the goal node
A* Algorithm
Algorithm

● The implementation of A Algorithm involves maintaining two lists- OPEN and CLOSED.
● OPEN contains those nodes that have been evaluated by the heuristic function but have not been
expanded into successors yet.
● CLOSED contains those nodes that have already been visited.
A* Algorithm
To find the lowest cost path, a search tree is constructed in following way:

● Initialize a tree with the root node being the start node S.
● Remove the top node from the open list for exploration.
● Add the current node to the closed list.
● Add all nodes that have an incoming edge from the current node as child nodes in the tree.
● Update the lowest cost to reach the child node.
● Compute the evaluation function for every child node and add them to the open list.
A* Algorithm
A* Algorithm

1- Time Complexity:

In the worst-case scenario, the time complexity of the A algorithm is exponential, O(b^d), where 'b' is the
branching factor of the search tree and 'd' is the depth of the optimal solution. However, in practice, with a
good heuristic function, A often performs much better and approaches linear time complexity, making it
very efficient.
A* Algorithm

2- Space Complexity:

The space complexity of the A algorithm is also exponential in the worst case, O(b^d), due to the need to
store all generated nodes and their associated information in memory. However, like its time complexity, A
can often have much better space usage in practice, especially with pruning techniques and efficient data
structures.
A* Algorithm

3- Completeness:

A is considered a complete algorithm, meaning that if there exists a solution, it will eventually find it,
provided there is enough memory to store the nodes generated during the search. This property holds true
regardless of the type of heuristic function used. However, completeness can be compromised if there are
infinite paths or loops in the search space.
A* Algorithm

Optimality:

A is also optimally efficient if the heuristic function used is admissible, meaning it never overestimates the
cost to reach the goal from any given node, and it is consistent, meaning the estimated cost from any given
node to the goal is never greater than the cost of reaching its successor plus the estimated cost from there
to the goal. When these conditions are met, A is guaranteed to find the shortest path from the start node
to the goal node.