Breadth First Search -

Algorithm
BY
DR. WASEEM SHAHZAD
 Travelling Salesman
Problem

Start City

Goal City
Start City

Goal City
➢Declare an Array to store the possible paths
➢What should be the size of the Array?
➢Its length should be equal to at least the total number of cities (nodes) in the problem
➢Since the maximum possible theoretical solution would involve travelling through all the
cities

➢Expand the parent node into child nodes

➢Perform “goal test” i.e. check whether any of the child
nodes is the goal node (destination)
Parent node

Child nodes
 Start

create paths one less

Create path
than the no of children

Is this Copy the members of the

expand each child city first parent path to the new paths
NO iteration
YES
Add the first child
Expand Parent City to the existing path
Append the child city
to existing path Perform Goal Test Add the remaining
children to the new paths

check and remove NO Is the test

repeating cities true

YES
Append the Goal City
NO to the path
child
cities > 1
Stop Execution
YES
 Goal Test
➢Objective is to check whether the child nodes include the
destination city
➢Find the number of children
➢Parse the children one by one and compare with the destination
city
➢If the child is the destination city (i.e. the test is true) the algorithm
must
➢Return success status
➢Return the location of the child (usually an index) satisfying the condition in the data
(usually an array) representing the children
 ➢ For first iteration i.e. Level=1, more paths are added due
Arad Level = 0 to the child nodes
➢ For first iteration the algorithm will run only once (as
Level = 1 there is only parent city)
timisoara sibiu zernid ➢ The number of new paths that are added is one less than
the number of child cities
➢ Each new path that is added must start with the parent
path 1,1 = [arad] city
Level+1
➢ The child city is placed in the path immediately next to
the parent city
path 1, : = arad, timisoara ➢ We can automatically achieve this by placing the child
path 2, : = arad, sibiu city in the array at a location that is related to the current
path 3, : = [arad, zernid] Level
➢ As the number of paths increases, for the 2nd iteration,
the algorithm must run three times i.e. equal to the
number of paths
 Arad Level = 0
➢ At each level the children at the previous level become
Level = 1
the parents for the next level
timisoara zernid ➢ Expanding a child node at all levels other than level-0
sibiu
will result in repetition of the previous parent city as a
Level = 2
lugoj rimnicuvilcea fagaras oradea oradea child city e.g.
➢ Expanding sibiu will give arad, rimnicuvilcea and
fagaras as the child cities, though fagaras was the
parent city of sibiu at the previous level

path 1, : = arad, timisoara, lugoj ➢ Only one new path is added as the only city at level 2
path 2, : = arad, sibiu, rimnicuvilcea with more than one child city was “Sibiu”
path 3, : = [arad, zernid, oradea]
path 4, : = [arad, sibiu, fagaras]
➢ We have to be careful when adding the new path as it
path 5, : = [arad, sibiu, oradea] should have the same previous members
➢ Algorithm must keep updating (incrementing) the
number of paths
 Arad Level = 0 ➢One new path is added as only one parent city at level
3 has more than one child node
Level = 1 ➢As the level increases the search-space increases and
timisoara zernid the memory utilization of the algorithm also increases.
sibiu
Level = 2 Time Complexity
lugoj rimnicuvilcea fagaras oradea
➢If every state has ‘b’ successors i.e. every parent node
generates b children, then the first level will have b
Level = 3
nodes and the 2nd level will have 𝑏2 nodes and so on
mehadia craiova pitesti bucharest sibiu
➢If the solution is at depth d i.e. the last node at the
current level then the number of nodes generated is
path 1, : = arad, timisoara, lugoj, mehadia
path 2, : = arad, sibiu, rimnicuvilcea, craiova Space Complexity
path 3, : = [arad, zernid, oradea, sibiu] ➢Every node that is explored is stored in memory as the
path 4, : = [arad, sibiu, fagaras, bucharest] explored set
path 5, : = arad, sibiu, rimnicuvilcea, pitesti
➢There will always be O(𝑏 𝑑−1 )nodes in memory
➢ Breadth-First search is optimal if the path cost is (explored set) and O(𝑏 𝑑 )nodes in the frontier i.e. the
uniform or is non-decreasing function nodes to be explored at the current level d
Time & Space Complexity of Breadth-First
Algorithm
Uniform-Cost Search
(UCS)
➢A modified form of breadth-first search in which
the child node with the smallest path cost is
expanded first
Start City
➢This is accomplished by storing the frontier (child
nodes) as a priority que i.e. the child node with the
smallest path cost has the highest priority
➢There are two differences as compared to the
breadth-first search
➢The first is that the goal test is applied to a node
when it is selected for expansion rather than when it
is first generated
➢The second difference is that a test is added in case a Goal City
better path is found to a node currently on the
frontier (means that the algorithm does not stop if a
probable path is found since a better path may exist)
➢Expanding Sibiu gives two possible child
nodes
Rimnicu Vilcea – Path Cost 80
Fagaras – Path Cost 99 Start City

➢UCS algorithm will select Rimnicu Vilcea as the possible

path because of low cost
➢Rimnicu Vilcea will be expanded next by adding Pitesti
Sibiu - Rimnicu Vilcea – Pitesti (80+97=177)
➢ The algorithm will now expand the 2nd low cost node at
level-1 which is Fagaras
Sibiu – Fagaras - Bucharest (99+211=310)
➢Although the algorithm has found a possible path Goal City
however it won’t stop at this
➢It will expand Pitesti
Sibiu - Rimnicu Vilcea – Pitesti – Bucharest
(80+97+101=278)
Optimality
➢UCS is optimal in general as it selects a node for expansion to which the optimal path has
already been found because “uniform-cost search expands nodes in order of their optimal path
cost”
➢Uniform-cost search does not care about the number of steps a path has, but only about their
total cost
Completeness
➢UCS is complete provided the cost of every step exceeds some small positive constant (zero path
cost can result in infinite loops)
➢When all step costs are the same, uniform-cost search is similar to breadth-first search, except
that the latter stops as soon as it generates a goal, whereas uniform-cost search examines all the
nodes at the goal’s depth to see if one has a lower cost; thus uniform-cost search does strictly
more work by expanding nodes at depth d unnecessarily
Time & Space Complexity

Where 𝜀 is a small positive number which the cost of each successive path increased from the
previous path and 𝐶 ∗ is the assumed cost of the optimal path
Depth First Search
(DFS)
 Depth First Search (DFS)
➢Depth-first search is a recursive algorithm for traversing a tree
➢Starts from the root node and follows each path to its greatest depth node
➢If a solution does not exist then it moves to the next path through Backtracking
➢DFS uses a LIFO (Last in First Out) structure for its implementation i.e. the node that
is generated last is expanded first
Advantages
➢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)
 Depth First Search (DFS)
Disadvantages
➢There is the possibility that many states keep re-occurring (i.e. the parent child
loop), 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
Completeness
➢DFS search algorithm is complete within finite state space as it will expand
every node within a limited search tree
Time Complexity
➢ Time complexity of DFS will be equivalent to the node traversed by the
algorithm
𝑇 𝑛 = 1 + 𝑛2 + 𝑛3 + ⋯ + 𝑛𝑚
Where m = maximum dept of any node
 Travelling Salesman
Optimality Problem
➢ DFS is not optimal as the algorithm will
expand the current tree to its maximum
depth and will return a solution if found
without considering the path cost. Start City
➢ Depth-first search is bound to fail in
infinite search space as the algorithm can
keep on following a path with no goal
➢ Depth-first tree search can be modified at
no extra memory cost so that it checks
new states against those on the path from
the root to the current node Goal City
➢ In case this check is not performed the
algorithm will be stuck in an infinite loop
 Depth First Search (DFS)
Space Complexity
➢DFS algorithm needs to store only single path from the root node, thus space
complexity of DFS algorithm is 𝑂(𝑏 × 𝑚)
Where b is the branching factor and m is the maximum depth
➢The depth first search consumes far less space as compared to the BFS algorithm
e.g. the depth first algorithm will require only 156 Kilobytes as compared to
10exabytes at depth d =16

Optimal
DFS search algorithm is non-optimal, as it may generate a large number of steps or
high cost to reach to the goal node.
Depth-Limited Search
(DLS)
➢A modified form of dept-first search
➢The depth to which the search can be made is limited by a dept limit l i.e. nodes
at depth l are treated as if they have no successors (children)
➢Depth limit solves the limitations of dept-first search in infinite search spaces
Disadvantages
➢Adds another source of incompleteness if we choose l < d i.e. the goal is beyond the depth
limit
➢Non-optimal if we choose l > d
➢Depth limits can be based on the knowledge of the problem e.g. in the given map the
maximum number of cities is 20, if there is a solution then it must be within this limit
i.e. l = 19. In fact a detailed analysis of the map yields that we can reach any city from
any other cities within 9 steps. This is know as the diameter of the search space.
Time and Space Complexity
➢The time and space complexity are given by O(𝑏 𝑙 ) and 𝑂(𝑏𝑙)
Iterative Deepening
Dept-First Search
➢A modified form of the depth-first search and dept-limit search
➢Depth limit is increased gradually i.e. initially 0, then 1, then 2 and so
on until a goal is found
➢Iterative deepening combines the benefits of both the depth-first and the
breadth-first algorithm
➢Its memory requirements are modest like depth first i.e. 𝑂(𝑏𝑑)
➢Complete like breadth-fist if the branching factor is finite
➢Optimal when the path cost is a non-decreasing function of the depth of
the node
➢Iterative deepening search may seem wasteful because states are generated multiple
times. However this isn’t too costly as the most of the nodes are at the bottom of the
search tree so it doesn’t matter that the upper levels are generated multiple times
➢The nodes at the bottom level are generated once, those on the next-to-bottom level are
generated twice and so on. Mathematically

➢Thus the time complexity is O 𝑏 𝑑 asymptotically, which is the same as the breadth
first search
➢If b = 10 and d = 5, then

➢Generally speaking, iterative deepening is the preferred uninformed search method

when the search space is large and the depth of the solution in not known
Bidirectional Search
➢Bidirectional means a search that runs in two directions and consist of two
simultaneous searches
➢The first one is forward and starts from the initial node
➢The 2nd one is backward and it starts from the goal node
➢The searches end when the two searches meet in the middle i.e. when the
intersection of the two frontiers results in a common node
➢Implemented by replacing the Goal test with a check to see whether the frontiers
of two searches intersect
➢The resulting solution may not be optimal even if the two searches are utilizing
the breadth first approach
➢ The time and space complexity is given by
Comparison
Informed Search
➢Uses problem-specific knowledge
➢Finds solutions more quickly
➢Generally uses the best-first approach i.e. a node is selected for expansion based
on an evaluation function, 𝒇(𝒏)
➢Most the evaluation function is constructed as a cost estimate
➢Node with the lowest evaluation is expanded first
➢The best-first cost search is identical to that for uniform-cost search
➢Most best-first algorithms include as a component of 𝒇(𝒏) a heuristic function,
denoted 𝒉(𝒏)
➢𝒉 𝒏 = estimated cost of the cheapest path from the state at node n to a goal
state
➢𝒉 𝒏 takes a node as input, but it depends only on the state at that node
➢For example, in Romania, one might estimate the cost of the cheapest path from
Arad to Bucharest via the straight-line distance from Arad to Bucharest
➢Heuristic functions are the most common form in which additional knowledge
of the problem is imparted to the search algorithm
➢If n is a goal node, then 𝒉 𝒏 = 𝟎
Greedy best-first Search
➢Greedy best-first search tries to expand the node that is closest to the goal, on
the grounds that this is likely to lead to a solution quickly i.e. it evaluates nodes
just by using the heuristic function, 𝒇 𝒏 = 𝒉 𝒏
➢Straight-line-distance heuristic, 𝒉𝑺𝑳𝑫 , i.e. the shortest distance between two
points is a straight line
➢The value of 𝒉𝑺𝑳𝑫 is not given in the problem itself
➢𝒉𝑺𝑳𝑫 is useful in solving the problem because it is correlated with the actual
distances
➢Start State – Arad Goal State – Bucharest
➢Path = Arad, Sibiu, Fagaras, Bucharest
➢Search Cost is optimal but solution isn’t
optimal
➢Shorter Path = Arad, Sibiu, Rimnicu Vilcea,
Pitesti, Bucharest
➢“Greedy” as it tries to get as close as
possible to destination
➢Incomplete even in finite space
➢Consider a path from Lasi to Fagaras
➢Neamt will be expanded first as it is
closest to Fagaras, but it is a dead end
➢The solution is to go first to Vaslui—a
step that is actually farther from the goal
according to the heuristic—and then to
continue to Urziceni, Bucharest, and
Fagaras.
➢The algorithm will never find this
solution, however, because expanding
Neamt puts Iasi back into the frontier, Iasi
is closer to Fagaras than Vaslui is, and so
Iasi will be expanded again, leading to an
infinite loop.
➢However, our node repetition check will
solve that issue
➢The worst-case time and space complexity for the tree version is O(bm), where
m is the maximum depth of the search space
➢A good heuristic function can substantially reduce the complexity
 A* Search: Minimizing the total estimated Solution
Cost
➢A modified form of best-first search is called A∗ search (pronounced “A-star
search”)
➢evaluates nodes by combining
➢g(n), the cost to reach the node,
➢and h(n), the cost to get from the node to the goal

➢Since g(n) gives the path cost from the start node to node n, and h(n) is the
estimated cost of the cheapest path from n to the goal, therefore
➢f(n) = estimated cost of the cheapest solution through n
➢To find the cheapest solution, a reasonable thing to try first is the node with the
lowest value of g(n) + h(n)
➢A∗ search is both complete and optimal
➢Identical to UNIFORM-COST-SEARCH except that A∗ uses g + h instead of g
Conditions for optimality: Admissibility and consistency
➢A* requires two conditions for optimality
1. h(n) has to be an admissible heuristic
An admissible heuristic is one that never overestimates the cost to reach the goal
Admissible heuristics are by nature optimistic because they think the cost of

solving the problem is less than it actually is e.g. straight-line distance 𝒉𝑺𝑳𝑫

Straight-line distance is admissible because the shortest path between any two

points is a straight line, so the straight line can’t be any overestimate

Conditions for optimality: Admissibility and consistency
2. The 2nd condition for optimality is called consistency (or sometimes
monotonicity)
A heuristic h(n) is consistent if, for every node n and every successor n’ of n
generated by any action a, the estimated cost of reaching the goal from n is
no greater than the step cost of getting to n plus the estimated cost of 𝑐(𝑛, 𝑎, 𝑛′ )

reaching the goal from n i.e.

h(n)
ℎ(𝑛′ )

Where 𝑐(𝑛, 𝑎, 𝑛′ ) is the cost of reaching from 𝑛 to 𝑛′ and ℎ(𝑛′ )is the
estimated cost of reaching from 𝑛′ to goal.
This fact is also know as triangle inequality
 Optimality of A*
➢ A* is optimal if ℎ(𝑛) is consistent
➢The consistency of ℎ(𝑛) can be proved if we establish the fact that: if h(n) is consistent, then the
values of f(n) along any path are nondecreasing
𝑓 𝑛′ = 𝑔 𝑛′ + ℎ(𝑛′ )
i.e. the estimated cost of a path through a node 𝑛′ is equal to the actual path of the cost to reach
node 𝑛′ and the estimated cost of reaching the goal from 𝑛′ . However,
𝑔 𝑛′ = 𝑔 𝑛 + 𝑐(𝑛, 𝑎, 𝑛′ )
i.e. the cost of reaching node 𝑛′ is equal to the actual cost of reaching node 𝑛 and the cost of going
from node 𝑛 to 𝑛′ trough some action a. Obviously, this cost should be greater or equal to (in the
worst case) 𝑔 𝑛 + ℎ 𝑛 = 𝑓(𝑛)

𝑓 𝑛′ = 𝑔 𝑛 + 𝑐(𝑛, 𝑎, 𝑛′ ) + ℎ(𝑛′ ) ≥ 𝑔 𝑛 + ℎ 𝑛
𝑓 𝑛′ = 𝑔 𝑛 + 𝑐(𝑛, 𝑎, 𝑛′ ) + ℎ(𝑛′ ) ≥ 𝑔 𝑛 + ℎ 𝑛
Start City 𝑓 𝑆𝑖𝑏𝑖𝑢 = 𝑔 𝑆𝑖𝑏𝑖𝑢 + ℎ(𝑆𝑖𝑏𝑖𝑢)

𝑓 𝑆𝑖𝑏𝑖𝑢 = 140 +253

Goal City
➢It is obvious that the sequence of nodes expanded by A∗ is in
nondecreasing order of f(n)
➢the first goal node selected for expansion must be an optimal
solution because f is the true cost for goal nodes (which have h
= 0) and all later goal nodes will be at least as expensive
➢We can draw contours in state space to geometrically illustrate
f(n)
➢ For uniform-cost search (A∗ search using h(n) = 0), the bands
will be “circular” around the start state
➢With more accurate heuristics, the bands will stretch toward
the goal state and become more narrowly focused around the
optimal path
➢If C* is the cost of the optimal solution path then:
➢A∗ expands all nodes with f(n) < C∗
➢A∗ might then expand some of the nodes right on the “goal
contour” (where f(n) = C∗) before selecting a goal node
 Completeness
➢Completeness requires that there be only finitely many nodes with cost less than
or equal to C∗, a condition that is true if all step costs exceed some finite 𝜖 and if
b is finite
➢A∗ expands no nodes with f(n) > C∗ e.g. Timisoara isn’t expanded even though
it is a child of the root
➢The subtree below Timisoara is pruned because ℎ𝑆𝐿𝐷 is admissible
➢The concept of pruning—eliminating possibilities from consideration without
having to examine them—is important for many areas of AI
➢ A∗ is optimally efficient for any given consistent heuristic i.e. no other optimal
algorithm is guaranteed to expand fewer nodes than A∗ (except possibly through
tie-breaking among nodes with f(n) = C∗)