Introduction to AI and Applications -1BAIA103

Search Algorithms

Agents make use of some or the other search algorithms in the background to
achieve their tasks( For example, games, Sudoku, crossword, etc., use search
algorithms to deduce a particular position in the game.)
A search problem consists of the following:
 State space is the set of all possible states that can be attained by an agent.
 Start state is the state from where the searching is done.
 Goal test is a function that checks if the current state is the goal state or not.
 Solution to a search problem is a sequence of actions (also known as plan) that
transforms the start state to the goal state. This plan is realized using search
algorithms.

Types of Search Algorithms

Figure: Different Types of Search Algorithms

Properties of Search Algorithms

 Completeness: A search algorithm is said to be complete if it returns at least one

solution for a particular input.
 Optimality: A search algorithm is said to give an optimal (best) solution if it has
the lowest path cost.
 Time and space complexity: Time complexity is the time taken by an algorithm to
complete a given task, and space complexity is the maximum storage space
required to perform the search operation. A good search algorithm takes less
time and space to do its work.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 1

 Introduction to AI and Applications -1BAIA103

Uninformed Search Algorithms

 A uninformed search, also known as a blind search algorithm,
 has no additional information about the goal state other than the one provided in the
problem definition.
 The only information they have is on how to traverse or visit the nodes in the tree.
 the machine blindly follows the technique irrespective of whether it is right or wrong,
efficient or inefficient.
 There can be multiple plans to reach the goal state from the start state. All these paths
differ by the order and/or length of actions.

Each of these uninformed algorithms has the following information

 Problem graph: the start node S to the goal node G.
 Strategy: stating the path followed by the graph reach G.
 Fringe: data structure to store all the possible states (nodes) that can be reached from
the current state.
 Tree: that depicts path while traversing to the goal node.
 Solution plan: that specifies the sequence of nodes from S to G.
 Path/Step cost: are integers that represent the cost to move from one node to another
node.
Depth First Search (DFS)
 In this search algorithm, the tree is traversed from the root node.
 The key will be searched till the leaf node of a particular branch.
 If the key is not found, then the search process backtracks to the point from
where the other branch was left unexplored.
 This process is repeated for that other branch either until the key is found or the
entire tree is completely traversed.
 DFS is implemented using LIFO, that is, stack data structure

 Searching starts from the root node A and then traverses

nodes B, D and H.
 Now, H is the leaf node, so we retrace the path to reach
node B to traverse its unexplored branch.
 Nodes E and I are thus traversed. Now, I is the leaf node, so
again, the path is retraced to follow the unexplored branch
of node E.
 As a result, node J is visited and then it is found that all
nodes in branches of node B have been traced.
Figure: Depth-first search
 So, the algorithm will move further by exploring the other
untraced branch of the root node.
Here, node C, followed by nodes F, K and G are explored
Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 2
 Introduction to AI and Applications -1BAIA103

 DFS algorithm occupies a lot of memory space, and takes a lot of time to
execute when the solution is at the bottom or end of the tree.
 DFS algorithm Explores as far as possible along each branch before
backtracking.
 DFS algorithm Is complete if the search tree is finite and a solution exists, it
is not optimal as the number of steps in reaching the solution, or the cost
spent in reaching it is high
.
Time complexity= O(bm) Space complexity= O(bm),
equivalent to the number of nodes traversed in DFS equivalent to how large can the fringe get
Path = the depth of the search tree = the number of levels of the search tree =
number of nodes in level.

b = maximum branching factor in a tree.

d = depth of the least-cost solution.
m = maximum depth of the state space (It maybe infinity.)
Advantages
 It uses less memory as it stores only the nodes on the path from the root node to the
current node.
 It takes less time to reach the goal node/state as compared to the BFS algorithm.
Disadvantages
 Sometimes, many states keep recurring. In such a scenario, there is no guarantee of
finding the solution.
 In certain cases, the algorithm may get stuck in an infinite loop while going deep
searching for nodes in the tree. A possible solution to this problem is to choose an
appropriate value of cut-off depth. If the ideal cut-off is d, and the chosen cut-off is less
than d, then algorithm fails. But, if the chosen cut-off is more than d, the execution time
increases.
 Complexity of the algorithm depends on the number of paths.
 DFS cannot check duplicate nodes.
Example 1: Consider the graph given below and state its DFS traversal.

Solution:
 Start with node 0. Exploring its branch to node 1, we move to node 2 and node 4.
 From node 4, we backtrack to node 3.
 Hence, the DFS path can be given as, 0 -> 1 -> 2 -> 4 -> 3.
Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 3
 Introduction to AI and Applications -1BAIA103

Example 2: Explore the path that will be

explored using the DFS algorithm to
reach node G from S.

Solution: To explore the path, a search

tree for the graph will be created. Since
DFS traverses the tree using the
‘deepest node first’ technique, it would
always pick the deeper branch until it
reaches the solution or until all nodes The DFS path can be given as,
of the current branch have been S -> A -> B -> C -> G
traversed. The traversal is shown in
blue arrows.

Depth-Limited Search Algorithm (DLS)

 DLS is similar to the DFS algorithm with an addition of a predetermined limit.
 This limit helps to overcome the limitations of the infinite path in the DFS. In DLS,
the node at the depth limit will be treated as it is a leaf node (or a node with no
successor nodes).
 The DLS algorithm is terminated in any of the three cases:
1. If the problem does not have any solution. This is known as standard error
failure.
2. If the problem does not have any solution within a given depth limit. This is
known as cut-off failure.
3. When the solution is found.
 Thus, the DLS search algorithm is complete if the solution is present within the
specified depth limit
Depth limited search
 If level is limited to 2, then the search
technique will not go to level 3
 Therefore, nodes E, F, G and H will not
be traversed
 time complexity O(bℓ),
 space complexity is O(b×ℓ), ℓ = depth
limitb = maximum branching factor in
a tree.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 4

 Introduction to AI and Applications -1BAIA103

Advantages
 It is a memory efficient algorithm as it consumes less space.
 The algorithm takes less time to execute.
 It terminates in finite time.
Disadvantages
 It is an incomplete algorithm as we may not be able to get the solution every time
we do the search (even if the solution exists, due to limit constraint).
 If muDltiple solutions of a problem exist, then DLS may not be able to find the
optimal solution. In other words, the algorithm is not optimal even if ℓ>d.

Example 1: Traverse the given tree to search

node H using DLS with predefined limit as 2.
Solution:
 We start with Node A at level 0.
 The search process then continues to
explore nodes B, C, D, and E at level 1.
 Level 2 explore the child nodes of node
Finally, node H is found at level 2 as a child
B. When H is not found there, a
node of C and the algorithm terminates
backtrack is done to level 1
Example: Traverse the given tree to search node
H using DLS with predefined limit as 2.

Solution: In the tree, node H is not present till

level 2, so the algorithm terminates returning
a cutoff failure. The path traversed for
searching is marked with a dashed line.

Breadth First Search (BFS)

 BFS algorithm, nodes in the tree are traversed breadthwise to reach the goal node.
 Searching begins from the root node and expands the successor node
breadthwise before traversing depth-wise. The BFS algorithm is implemented
using a FIFO queue.
 It is a complete algorithm, that is, it finds a solution if it exits.
 The algorithm is optimal, if step cost = 1 (that is, if either there is no cost or if all
step costs are same).

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 5

 Introduction to AI and Applications -1BAIA103

 Children of the root node are traversed before

exploring other nodes on any branch.
 After traversing all nodes at a particular level,
control then passes to the next level,
 BFS algorithm starts from the root node A and then
traverses node B followed by node C.
 After node C, all nodes from D to G are traversed.
This is followed by traversal of nodes H to K
 Thus, the BFS algorithm explores all neighbour nodes
at the present depth before moving the nodes at the Figure :Breadth-first search
next depth level..

In a BFS algorithm,
 Nodes in the path = the depth of the shallowest solution = number of nodes in level.
 Nodes in the path = the depth of the shallowest solution =No. of nodes in level.
 Time and Space complexity= O (bd).
b =branching factor
d =depth of the tree.
 Total number of nodes created in the worst case is b + b2 + b3 + … + bd.
 Time complexity is equivalent to the number of nodes traversed in BFS
 Space complexity is equivalent to how large can the fringe get.
Advantages
 BFS will find a solution if it exists.
 If a given problem has multiple solutions, then BFS will give the minimal
solution requiring least number of steps.
 The architecture of the BFS algorithm is simple and robust.
 It constructs the shortest path of traversing through the nodes of the graph so
that the graph can be traversed in the smallest number of iterations.
 The algorithm does not get stuck in an infinite loop.
 Due to high precision and robust implementation, BFS is used in multiple real-life
solutions like P2P networks, Web Crawlers and Network Broadcasting.
Disadvantages
 Since each level of node is saved for creating the next one, it consumes a lot of
memory space. Space requirement to store nodes is exponential.
 It takes less time if the solution is far away from the root node—at the bottom
or at the end.
 Its complexity depends on the number of nodes.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 6

Introduction to AI and Applications -1BAIA103

BFS Tree starting from a random node BFS algorithm selects

a random initial node
(also known as
source node or root
node) and traverses
the graph layer-wise
in such a way that all
the nodes and their
respective children
Visiting a node :visit or select a node nodes are visited and
Exploring a node :adjacent nodes (child nodes) of the selected explored.
node

Example: Find the BFS traversal from

node S to node G Solution: The BFS

creates a tree and traverses it using the

principle ‘shallowest node first’. So, at
note S, node D will be traversed
followed by node G.
thus, Path is S -> D -> G

Example: Consider the graph. Using node A as the source node, traverse the graph and
trace the working of the algorithm using a queue.
Step 1: Insert root node ‘a’ into the Queue.
Step 2: Remove node ‘a’ from the queue, print it and insert the child nodes of ‘a’
in the queue. Thus, nodes ‘b’ and ‘c’ are inserted.
Step 3: The queue is not empty and has node ‘b’ and ‘c’. Since ‘b’ is the first node
in the queue, remove it, print it and insert the child nodes of ‘b’ into the queue.
That is, insert node‘d’ and ‘e’.
Repeat these steps until the queue gets empty. Do not insert those nodes in the
queue that are already visited.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 7

 Introduction to AI and Applications -1BAIA103

Breadth-First Search Algorithm Pseudocode

 According to the pseudocode, s is

the root node of the graph, G.
 Initially, s is inserted in the queue.
 Then, all child nodes of ‘s’ are
marked.
 These child nodes are visited after
removing ‘s’ from the queue.
 At each step of the algorithm, child
nodes, w are inserted into the
queue to further visit its child
nodes.
 The process is repeated under the
queue is empty.

Applications of Breadth-First Search Algorithm

BFS is a simple graph traversal method that is widely used in the following areas.

Crawlers in Search Engines

 BFS algorithm is used for indexing web pages.
 The algorithm starts traversing from the source page and follows all the links
Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 8
Introduction to AI and Applications -1BAIA103

associated with that page.

GPS Navigation Systems
 GPS systems use BFS algorithm to find neighbouring locations.
 Find the Shortest Path for an Unweighted Graph
 For an unweighted graph, the shortest path can be easily calculated by
choosing a path with the least number of edges.( by traversing a minimum
number
Broadcasting
 In computer networks, data is broken down into small packets before
transmission across the communication media.
 These packets use an algorithm to compute a path to the destination.
 For messages that are broadcasted across all the nodes in a network, BFS is a
preferred choice.
Peer-to-Peer Networking
 BFS is used in peer-to-peer network as a traversal method to find all the
neighboring nodes. E x : Bit Torrent uses BFS for peer-to- peer communication.
Uniform Cost Search (UCS)
 The UCS algorithm is used to find an optimal solution to the goal state when the
step costs are not the same.
 Algorithm computes the cumulative cost to expand each node from the root node to
the goal node.
 It neither traverses depth nor breadth, but searches for the next node with the
lowest cost.
 Sorting is done in increasing cost of the path to a node so that the algorithm can
explore paths in the increasing order of cost.
 UCS always expands the node with the least cost.
 It is identical to BFS if each transition has the same cost. Remember that,
 Cost of a node: cost(node) = cumulative cost of all nodes from root
cost(root) = 0
if S is the start node and G is the
goal state
S ABDG, COST=10
S ACDG, COST=6
S ACG COST=4
S G COST=12 Figure : Uniform cost search

 Thus,UCS expands nodes based on their path costs form the root node. It can be used
to traverse any graph/tree where the optimal cost is the traversal criteria.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 9

Introduction to AI and Applications -1BAIA103

 The uniform-cost search algorithm is implemented by the priority queue, giving

maximum priority to the lowest cumulative cost.
 UCS is equivalent to BFS algorithm if the path cost of all edges is the same.
 The UCS algorithm is a complete and optimal algorithm with time and space
complexity and space complexity
 O (b(c/ε)), where ε = lowest cost ,c = optimal cost.

Advantages
 It finds an optimal solution by considering the least cost at every state.
 UCS is complete only if states are finite and if there is no loop with zero weight.
 UCS is optimal only if there is no negative cost.
Disadvantages
 The algorithm may get stuck in an infinite loop as it considers only cost and not the
number of steps taken to reach the goal state.
 It explores nodes in every ‘direction’.
 It does not have any information about the location of the goal state.
 It requires more space for storing information about nodes.
 The UCS must explore all paths including the long ones.

Example 1: Consider th e tree given Example 2: Find the path and cost to
below and its UCS traversal to reach move from node S to node G in the graph
node G from S.

given below
Solution: For a better clarity, we can
draw an equivalent search tree for the
graph. Using UCS, the path with the
least cumulative cost is chosen.
Path: S -> A -> B -> G
Cost: 5

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 10

 Introduction to AI and Applications -1BAIA103

Iterative Deepening Depth-First Search (IDDFS)

 The iterative deepening algorithm combines the features of DFS and BFS algorithms
to find out the best depth limit that can be used to implement the DLS algorithm.
 IDDFS does so by gradually increasing the limit until the goal is found.
 The algorithm performs depth-first search to level 1, starts over, executes a complete
depth-first search to level 2 and continues until the solution is found.
 It never creates a node until all lower nodes are generated.
 It only saves a stack of nodes.
 IDDFS gets benefitted by fast search technique of BFS algorithm and memory
efficiency of the depth-first search algorithm.
 This algorithm is widely used when search space is large, and depth of the goal node is
not known.
 The algorithm ends when it finds a solution at depth d. The number of nodes created
at depth d is bd and at depth d-1 is bd-1.
 Time complexity =O (bd) , space complexity = O(bd),
 In IDDFS, we perform DFS up to a certain ‘limited depth,’ and keep increasing this
‘limited depth’ after every iteration.
Advantages
 It combines the benefits of BFS and DFS search algorithms— fast search and memory
efficiency.
 The algorithm is complete is if the branching factor is finite.
 IDDFS is an optimal algorithm if path cost is a non-decreasing function of the depth
of the node.
Disadvantages
 It repeats all the work of the previous phase.
 It takes more time (exponential) to reach the goal node.
The algorithm fails when the BFS fails.
Example: Traverse the given tree using the
iterative deepening depth-first search algorithm.
Solution:
 In the first iteration, node A at level 0 is
explored.
 In the second iteration, nodes B and C are
traversed at level 1.
 In the third iteration, nodes D, E, F and G are
traversed.
 In the fourth iteration, node H is reached.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 11

Introduction to AI and Applications -1BAIA103

Example: Consider the tree given below and

demonstrate the application of DDFS.

Bidirectional Search

 In a bidirectional search, searching is done from both the directions simultaneously.

It searches forward from initial state and backward from goal state till both meet to
identify a common state.
 The path from initial state is concatenated with the inverse path from the goal state.
 Each search is done only up to half of the total path and finds the smallest path from
the source node to the goal node.
 Thus, bidirectional search replaces single search graph with two smaller sub
graphs—one starting from initial or start node to the goal node (termed as forward
search) and the other starting from goal node towards the source node (known as
backward search).
 The search process terminates when the two graphs intersect.
 Bidirectional search can be guided by a heuristic estimate of remaining distance
from source to goal and vice versa.
 Heuristic means finding the shortest path from the current node in the graph to
the goal node.
Advantages
 It is faster than other algorithms
 It avoids unnecessary exploration of nodes
 Time and space complexity of searching is O (bd/2 +bd/2), which is far less than O(bd).
B= branching factor of the tree ,d = distance of goal node from the source node.
 The algorithm drastically reduces searching time by supporting simultaneous
searches.
 It takes less memory capacity to store all the searches.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 12

 Introduction to AI and Applications -1BAIA103

 Bidirectional search is complete if BFS is used in both searches.

 The algorithm is optimal if BFS is used for search and paths have uniform cost.
Disadvantages

 The algorithm can be used only when the goal state is clearly known.
 It is difficult to implement.
 The algorithm must be robust enough to correctly deduce the intersection point
where it can terminate. Otherwise, the algorithm may get stuck in an infinite
loop.
 It is very difficult to search backwards through all states.
When to Use Bidirectional Approach?

 When both the starting node and the goal node are unique and completely defined.
 When the branching factor is exactly the same in both directions

Example 1: Consider the graph given below and Solution:

apply bidirectional search on it to reach goal node  Two searches are executed
14 from source node 0. simultaneously-, one from node 0
and the other from node 14.
 Both these searches intersect at
node 7. At this point, we have found
a path from node 0 to 7 and from
node 14 to 7.
 The search process terminates
successfully, thereby avoiding
unnecessary exploration

Example 2: Consider the graph given below and

demonstrate the application of bidirectional
search from Start forward search from node 2
and backward search from node [Link] BFS from
both directions
Solution
 In the forward search process, nodes 1, 6 and 8
are explored.
 In the backward search process, mode 7 is
explored.  Here, we find intersecting node as
 But no intersection node is Next explore node 3, so the algorithm
node 3 while doing a forward search and terminates and the path is
node 3 while doing a backward search - 2 -> 1 -> 3-> 7 -> 11

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 13

 Introduction to AI and Applications -1BAIA103

Informed Search Algorithms

 The uninformed search algorithms had no knowledge about search space. But
informed search algorithm
 Contains some information about how far we are from the goal, cost of the path, how
to reach the goal, etc.
 This knowledge helps agents to explore less to the search space and reach the goal
node more efficiently.
The informed search algorithm which is extensively used in a large space is also
known as heuristic search as it uses a heuristic function.
The heuristic function takes the current state of the agent as its input and estimates
how close the agent is from the goal.
Though the heuristic method may not always give the best solution, it is, however,
guaranteed to find a good solution in reasonable time.
A heuristic function h(n), calculates the cost of an optimal path between the pair of
states. The value of the heuristic function is always positive.
 h(n) <= h (n)
where h(n) is heuristic cost, and h (n) is the estimated cost.
 This means that the heuristic cost should be less than or equal to the estimated cost.
Pure Heuristic Search
 To solve large problems with a large number of possible states, problem-specific
knowledge needs to be added to increase the efficiency of search algorithms. In such a
situation, heuristic search algorithm performs well.
 Heuristic search is the simplest form of heuristic search algorithms that expands
nodes based on their heuristic value h(n).
 The algorithm maintains two lists—OPEN and CLOSED.
 All nodes that have already been expanded are placed in the CLOSED list, while others
that have not been expanded are in the OPEN list.
 On each iteration, nodes with the lowest heuristic value are expanded. Then, the
heuristic function is applied to the child nodes and they are placed in the open list
according to their heuristic value.
 The shorter paths are saved and the longer ones are disposed.
 The process continues unit a goal state is found.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 14

 Introduction to AI and Applications -1BAIA103

Best-First Search Algorithm (Greedy Search)

 Greedy best-first search algorithm combines depth-first search and breadth-first

search algorithms and always selects the path which appears best at that
moment.
 It uses the heuristic function and best-first search at each step to choose the
most promising node.
 The most promising node is the one that is closest to the goal node.
 The greedy best first algorithm is implemented by the priority queue.
 Heuristic evaluation functions calculate the cost of optimal path between two
states.
 The worst-case time complexity and space complexity of greedy best first search is
O (bm), m = maximum depth of the search space.
 Although the algorithm is complete, it can, at times, behave like an incomplete
algorithm even if the given state space is finite. This makes the Greedy best first
search algorithm not an optimal one.

Best first search algorithm steps:

Step 1: Insert the starting node in the OPEN list.
Step 2: Stop and return failure if the OPEN list is empty,
Step 3: From the OPEN list, remove the node having the lowest value of h(n), and insert
it in the CLOSED list.
Step 4: Expand the node (removed in Step 3) and generate its successors.
Step 5: Check each successor to find if it is the goal node or not. If any successor node
is found to be the goal node, then return success and terminate the search, else go to
Step 6.
Step 6: Check if each successor node is in either OPEN or CLOSED list. If the node is not
present in any of the lists, then add it to the OPEN list.
Step 7: Go to Step 2.
Advantages
 It takes advantage of both BFS and DFS algorithms.
 Best first search algorithm is more efficient than BFS and DFS algorithms.
Disadvantages
 Worst-case scenarios, best first search can behave as an unguided depth-first search.
 Like DFS, best first search algorithm can get stuck in a loop.
 Best first search algorithm is not an optimal algorithm.

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 15

Introduction to AI and Applications -1BAIA103

Example 1: Consider the tree Solution: Expand the node S and put it in the CLOSED list.
given below and traverse it Generate its successors and place them in the OPEN list.
using greedy best-first search Open [A, B], Closed [S]
algorithm Iteration 1: Since h(n) for node B is less than that of node A,
expand B and place it in CLOSED list. Now only node A is in
the OPEN list. Open [A], Closed [S, B]
Iteration 2: Generate successors of node B and place them in
the OPEN list. Open [E, F, A], Closed [S, B].
Since node F has the lowest heuristic value among all
nodes in the OPEN list, we will expand node F. Now, Open [E,
A], Closed [S, B, F]
Iteration 3: Generate successors of node F and place them in
the OPEN list. So, Open [I, G, E, A], Closed [S, B, F]
Now, generate succors of node F and place them in OPEN
list. Since one of the successors of node F is the goal node,
the algorithm returns success and terminates. The path is
given by the nodes present in the CLOSED list. Open [I, E, A],
Closed [S, B, F, G]
Hence,the final solution path will be: SBFG

Example 2: Apply greedy best first search algorithm on the graph given below to reach
node I from node S.

Solution:
 Add node S in the CLOSED list and place its successors in the OPEN list.
Open [A, B, C], Closed [S]
 Remove A from the OPEN list as it has minimum h(n), place it in CLOSED list and
put its successors in the OPEN list. Open [B, C, E, D], Closed [S, A]
 Remove C from the OPEN list as it has minimum h(n), place it in CLOSED list and
put its successors in the OPEN list. Open [B, E, D, H], Closed [S, A, C]
 Remove B from the OPEN list as it has minimum h(n), place it in CLOSED list and
put its successors in the OPEN [Link] [E, D, H, F, G], Closed [S, A, C, B]
Remove H from the OPEN list as it has minimum h(n), place it in CLOSED list and put its
successors in the OPEN list. Since I is the successor of node H, the algorithm returns
[Link] [E, D, F, G, I, J], Closed [S, A, C, B, H
Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 16
Introduction to AI and Applications -1BAIA103

Pallavi J Asst. Professor, Dept. of ECE, VVIET Page 17