Searching Algorithms in AI

Searching - a process of finding the solution for a given set of problems. A searching
strategy is used to specify which path is to be selected to reach the solution.

Allan Ninyesiga
Problem-Solving Agents
• Imagine an agent enjoying a touring vacation
in Romania. The agent wants to take in the
sights, improve its Romanian, enjoy the
nightlife, avoid hangovers, and so on. The
decision problem is a complex one.
• Now, suppose the agent is currently in the
city of Arad and has a nonrefundable ticket
to fly out of Bucharest the following day. The
agent observes street signs and sees that
there are three roads leading out of Arad:
one toward Sibiu, one to Timisoara, and one
to Zerind. None of these are the goal, so
unless the agent is familiar with the
geography of Romania, it will not know
which road to follow
Problem-Solving Agents
• If the agent has no additional
information—that is, if the
environment is unknown—then
the agent can do no better than
to execute one of the actions at
random.
• Here we will assume our agents
always have access to information
about the world, such as the map
in Figure with that information,
the agent can follow this four-
phase problem-solving process:
Terminologies in Search Algorithms

• Search: A step-by-step procedure to solve a given search

problem. Three main factors of a search problem:
• Search Space: The set of possible solutions a system may have.
• Start state: The state where the agent starts the search. For example: Arad.
• Goal test: A function that monitors the current state and returns whether the
goal is achieved or not.
• Search Tree: The representation of the search problem in the form of
a tree. The root of the tree is the initial state of the problem.
• Transition model: Used to represent the description of the action.
RESULT(Arad, ToZerind) = Zerind.
Terminologies in Search Algorithms

• Solution: Sequence of actions that leads from the initial node to the
final node.
• Path Cost: A function that assigns a numeric cost to each path.
• Optimal Solution: The solution with the lowest cost.
• Problem Space: The environment in which the search takes place.
• Depth of a problem: Length of the shortest path from the initial state
to the final state.
Real-world problems
• We have already seen how the route-finding problem .
• Route-finding algorithms are used in a variety of applications such as
Web sites and in-car systems that provide driving directions, are
relatively straightforward extensions of the Romania example.
• Others, such as routing video streams in computer networks, military
operations planning, and airline travel-planning systems, involve
much more complex specifications.
• Consider the airline travel problems that must be solved by a travel
planning Web site:
Real-world problems: the airline travel problems
Properties of Search Algorithms

• Completeness: If the algorithm guarantees to return a solution, if

there exists at least one for any random input then the algorithm can
be said to be complete.
• Optimality: If the algorithm found the best solution (lowest path cost)
among the others, then that solution can be said as the optimal
solution. The ability to find the optimal solution is called optimality.
• Time complexity: The time is taken by the algorithm to complete a
task
• Space Complexity: the required storage space at any point during the
search.
Search algorithms Classification
Uninformed search algorithms
• 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.
Breadth-first search

• 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.
• Breadth-first search implemented using FIFO queue data structure
Breadth-first search Example:

In the tree structure, the traversing

of the tree using BFS algorithm from
the root node S to goal node K. BFS
search algorithm traverse in layers,
so it will follow the path which is
shown by the dotted arrow, and the
traversed path will be:

S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
Breadth-first search
• Time Complexity: Time Complexity of BFS algorithm can be obtained by
the number of nodes traversed in BFS until the shallowest Node. Where
the d= depth of shallowest solution and b is a node at every state.
• T (b) = 1+b2+b3+.......+ bd= O (bd)
• Space Complexity: Space complexity of BFS algorithm is given by the
Memory size of frontier which is O(bd).
• Completeness: BFS is complete, which means if the shallowest goal node is
at some finite depth, then BFS will find a solution.
• Optimality: BFS is optimal if path cost is a non-decreasing function of the
depth of the node.
Breadth-first search
Depth-first Search

• It is a process similar to that of BFS.

• A recursive algorithm for traversing a tree or graph data structure.
• The searching procedure starts from the root node and follows each
path to the greatest depth and then backtracks before entering the
next path.
• The stack data structure that works on the concept of Last In First Out
(LIFO) is used to implement the procedure.
 Depth-first Search: Example
• depth-first search follow the order as:
• Root node--->Left node ----> right
node.
• It will start searching from root node
S, and traverse A, then B, then D and
E, after traversing E, it will backtrack
the tree as E has no other successor
and still goal node is not found. After
backtracking it will traverse node C
and then G, and here it will terminate
as it found goal node.
Depth-first Search
• Completeness: complete within finite state space as it will expand every
node within a limited search tree.
• Time Complexity: equivalent to the node traversed by the algorithm. It is
given by:
• T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
• Where, m= maximum depth of any node and this can be much larger than d
(Shallowest solution depth)
• Space Complexity: DFS algorithm needs to store only single path from the
root node, hence space complexity of DFS is equivalent to the size of the
fringe set, which is O(bm).
• Optimal: DFS is non-optimal, as it may generate a large number of steps or
high cost to reach to the goal node.
Depth-first Search
Depth-Limited Search Algorithm

• Similar to DFS with a predetermined

limit.
• DLS can solve the drawback of the
infinite path in the DFS.
• The node at the depth limit will
treat as it has no successor nodes
further.
• DLS 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.
Depth-Limited Search Algorithm

• 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.
Depth-Limited Search Algorithm
Uniform-cost Search Algorithm
• A searching algorithm used for
traversing a weighted tree or graph.
• Comes into play when a different cost is
available for each edge.
• The primary goal of the UCS is to find a
path to the goal node which has the
lowest cumulative cost.
• UCS expands nodes according to their
path costs form the root node.
• A UCS algorithm is implemented by the
priority queue. It gives maximum
priority to the lowest cumulative cost.
Example: UCS
• Consider Figure, where the problem is to get
from Sibiu to Bucharest. The successors of
Sibiu are Rimnicu Vilcea and Fagaras, with
costs 80 and 99, respectively. The least-cost
node, Rimnicu Vilcea, is expanded next, adding
Pitesti with cost 80+97=117.
• The least-cost node is now Fagaras, so it is
expanded, adding Bucharest with cost
99+211=310
• Bucharest is the goal, but the algorithm tests
for goals only when it expands a node, not
when it generates a node, so it has not yet
detected that this is a path to the goal.
Example: UCS
• The algorithm continues on, choosing Pitesti
for expansion next and adding a second path
to Bucharest with cost 80+97+101=278. It
has a lower cost, so it replaces the previous
path in reached and is added to the frontier.
It turns out this node now has the lowest
cost, so it is considered next, found to be a
goal, and returned.
• Note that if we had checked for a goal upon
generating a node rather than when
expanding the lowest-cost node, then we
would have returned a higher-cost path (the
one through Fagaras).
Uniform-cost Search Algorithm
• Completeness:
• Uniform-cost search is complete, such as if there is a solution, UCS will find it.
• Time Complexity:
• Let C* is Cost of the optimal solution, and ε is each step to get closer to the goal
node. Then the number of steps is = C*/ε+1. Here we have taken +1, as we start from
state 0 and end to C*/ε.
• Space Complexity:
• The same logic is for space complexity so, the worst-case space complexity of
Uniform-cost search is O(b1 + [C*/ε]).
• Optimal:
• Uniform-cost search is always optimal as it only selects a path with the lowest path
cost.
Uniform-cost Search Algorithm
 Iterative deepening depth-first Search(IDDFS)

• It is a combination of both DFS

and BFS.
• It will find the best depth limit and
the limit is gradually increased
until a goal is found.
• The algorithm performs a depth-
first search to a certain depth limit
and this depth limit is increased
after each iteration until the goal
is reached.
Iterative deepening depth-first Search
• Completeness:
• This algorithm is complete is if the branching factor is finite.
• Time Complexity:
• Let's suppose b is the branching factor and depth is d then the worst-case
time complexity is O(bd).
• Space Complexity:
• The space complexity of IDDFS will be O(bd).
• Optimal:
• optimal if path cost is a non- decreasing function of the depth of the node.
Iterative deepening depth-first Search
Bidirectional Search Algorithm
• It performs two searches
simultaneously.
• One from the starting end is called
forward-search and the other from the
end is called backward search.
• One single graph is replaced with two
small subgraphs one from the initial
vertex and the other from the final
vertex.
• The searching procedure stops when
these two graphs intersect each other.
• It can use search techniques such as
BFS, DFS, DLS, etc.
Bidirectional Search Algorithm
• Completeness: Bidirectional Search is complete if we use BFS in both
searches.
• Time Complexity: Time complexity of bidirectional search using BFS
is O(bd).
• Space Complexity: Space complexity of bidirectional search is O(bd).
• Optimal: Bidirectional search is Optimal.
Bidirectional Search Algorithm
• Completeness: Bidirectional Search is complete if we use BFS in both
searches.
• Time Complexity: Time complexity of bidirectional search using BFS
is O(bd).
• Space Complexity: Space complexity of bidirectional search is O(bd).
• Optimal: Bidirectional search is Optimal.
Bidirectional Search Algorithm
Informed Searching Algorithms

• Read about

Also - Other Search Algorithms (Adversarial search)