Page 27 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 2: Problems, Problem Spaces and Search

Provided a branching factor b and graph depth d the asymptotic space complexity is the number Notes
of nodes at the deepest level, O(bd). When the number of vertices and edges in the graph are
recognized ahead of time, the space complexity can also be articulated as O(|E| + |V|) where
|E|is the cardinality of the set of edges (the number of edges), and |V| is the cardinality of the
set of vertices. In the worst case the graph has a depth of 1 and all vertices must be amassed.

Notes As it is exponential in the depth of the graph, breadth-first search is often
unreasonable for large problems on systems with bounded space.
Time Complexity

Since in the worst case breadth-first search has to regard all paths to all probable nodes the time
complexity of breadth-first search is 1 + b + b + b + . . . +b which is O(bd). The time complexity
2
d
3
can also be articulated as O(|E| + |V|) as every vertex and every edge will be discovered in the
worst case.
Completeness

Breadth-first search is complete. This shows that if there is a solution, breadth-first search will
find it in spite of the type of graph. Though, if the graph is infinite and there is no solution
breadth-first hunt will depart.

Proof of Completeness

If the shallowest objective node is at some restricted depth say d, breadth-first search will sooner
or later find it after increasing all shallower nodes (given that the branching factor b is finite).

Optimality
For unit-step cost, breadth-first search is best possible. Usually breadth-first search is not best
possible as it always returns the consequence with the fewest edges among the start node and
the goal node. If the graph is a weighted graph, and as a result has costs connected with each step,
a goal next to the beginning does not have to be the cheapest objective obtainable. This problem
is solved by enhancing breadth-first search to uniform-cost search which considers the path
costs. Nonetheless, if the graph is not weighted, and consequently all step costs are equal,
breadth-first search will discover the nearest and the finest solution.
Bias towards Nodes of High Degree

It has been empirically noticed (and analytically exposed for random graphs) that incomplete
breadth-first search is prejudiced towards nodes of high degree. This makes a breadth-first
search model of a graph very tricky to understand.

Example: For example, a breadth-first sample of 1 million nodes in Facebook (less than
1% of the complete graph) overvalues the average node degree by 240%.

2.3.3 Applications

Breadth-first search can be utilized to explain many problems in graph theory, for instance:
 Locating all nodes within one connected component

 Copying Collection, Cheney’s algorithm

LOVELY PROFESSIONAL UNIVERSITY 21