Lecture 5
Chapter 3: Brute Force and
Exhaustive Search (II)
Today Lecture
Brute Force Algorithms
▪ Tree search terminology
▪ Tree-search algorithm
▪ Graph-search algorithm
b
▪ Measuring problem-solving performance
▪ Uniformed search strategies
▪ Breadth First Search (BFS) (Shortest
path first)
▪ Depth First Search (DFS) (Longest path
first)
Tree Search Terminology
Tree search terminology
• Root : no parent.
• Leaf: no child. Root
• Hight: distance from root to leaf (maximum Level 0
number of edges in path from root Level 1 Successor
• Level (depth): number of edge in the path from Level 2
the root to that node.
• Branch: Internal node, neither the root nor theLevel 3
leaf. Hight = 3
• Successor nodes of a node: its children Leaf
• Predecessor node of a node: its parent
• Path: Sequence of nodes along the edges of a tree
Tree-Search Algorithm
Tree-search algorithm
• There is designated node at the top of the
tree known as a root of the tree.
• The remaining data items are divided into
disjoint subsets refer to as subtree. function TREE-SEARCH(problem) returns a
solution, or failure
• The tree is expanded in height towards the initialize the frontier using the initial state of
bottom. problem
loop do
• A tree must be connected which means there if the frontier is empty then return failure
must be a path from one root to all other else choose a leaf node and remove it from
nodes. the frontier
if the node contains a goal state then return
• It does not contain any loops. the corresponding solution
else expand the chosen node, adding the
• A tree has n-1 edges. resulting nodes to the frontier
Tree-search algorithm (Cont.)
• Frontier: The set of all leaf nodes
available for expansion at any given
point (nodes in memory)
• The path from Arad to Sibiu and back
to Arad again is called a loopy path
• Redundant paths which exist
whenever there is more than one way
to get from one state to another.
• For example: Arad–Sibiu (140 km long) and Arad–
Zerind–Oradea–Sibiu (297 km long).
Nodes that have been expanded are shaded.
Nodes that have been generated but not yet expanded are
• Explored set: which remembers every outlined in bold.
expanded node. Nodes that have not yet been generated are shown in faint
dashed lines.
Graph Search Algorithm
Graph-search algorithm
• The graphs are classified into various
function GRAPH-SEARCH(problem) returns a
categories such as directed, non-directed,
solution, or failure
connected, non-connected, simple and
initialize the frontier using the initial state of
multi-graph ( multiple edges).
problem
initialize the explored set to be empty
• A vertex in a graph can be connected to any
loop do
number of other vertices using edges.
if the frontier is empty then return failure
else choose a leaf node1 and remove it from
• An edge can be bidirected or directed.
the frontier
if the node contains a goal state then return
• An edge can be weighted.
the corresponding solution
else add the node to the explored set
• A graph can have loops and self-loops.
expand the chosen node, adding the
resulting nodes to the frontier only if
• In the graph, there is no predefined number
not in the frontier or explored set
of edges, and it depends on the graph.
Measuring Problem-Solving Performance
Measuring problem-solving performance
We need to consider the criteria that might be used to choose among algorithms.
• Completeness: Is the algorithm
guaranteed to find a solution when
there is one? Goal
• Optimality: Does the strategy find the
optimal solution? Goal
• Time complexity: How long does it
take to find a solution? ∞
• Space complexity: How much memory
is needed to perform the search?
The differences between Tree and Graph
Uninformed Search Strategies
Uniformed search strategies
• The uninformed search (also called
blind search).
• Breadth-first search
• Blind search means that the strategies
have no additional information about • Uniform-cost search
states beyond that provided in the
problem definition. • Depth-first search
• All search strategies are distinguished • Depth-limited search
by the order in which nodes are
expanded. • Iterative deepening depth-first
search
• Bidirectional search
Breadth First Search (BFS) (Shortest Path First)
Breadth First Search (BFS) (Shortest path first)
• Breadth-first search is a simple strategy in https://en.wikipedia.org/wiki/Breadth-
first_search
which the root node is expanded first,
then all the SEARCH successors of the function BREADTH-FIRST-SEARCH(problem) returns a solution, or
failure
root node are expanded next, then their node ←a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
successors, and so on. if problem.GOAL-TEST(node.STATE) then return
SOLUTION(node)
frontier ←a FIFO queue with node as the only element
• In general, all the nodes are expanded at a explored ←an empty set
loop do
given depth in the search tree before any if EMPTY?( frontier) then return failure
nodes at the next level are expanded. node←POP( frontier ) /* chooses the shallowest node in frontier */
add node.STATE to explored
for each action in problem.ACTIONS(node.STATE) do
• The shallowest unexpanded node is child ←CHILD-NODE(problem, node, action)
chosen for expansion. This is achieved if child .STATE is not in explored or frontier then
if problem.GOAL-TEST(child .STATE) then return
very simply by using a FIFO queue for the SOLUTION(child )
frontier. frontier ←INSERT(child , frontier )
Breadth First Search (BFS) (Shortest path first) (Cont.)
function BREADTH-FIRST-SEARCH(problem) returns a solution, or
failure
node ←a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
if problem.GOAL-TEST(node.STATE) then return
SOLUTION(node)
frontier ←a FIFO queue with node as the only element
explored ←an empty set
loop do
if EMPTY?( frontier) then return failure
node←POP( frontier ) /* chooses the shallowest node in frontier */
add node.STATE to explored
for each action in problem.ACTIONS(node.STATE) do
child ←CHILD-NODE(problem, node, action)
if child .STATE is not in explored or frontier then
if problem.GOAL-TEST(child .STATE) then return
SOLUTION(child )
frontier ←INSERT(child , frontier )
Time and space complexity of BFS
• Time Complexity
– assume (worst case) that there is 1 goal leaf at the RHS d=0
so BFS will expand all nodes
d=1
=1+b+ b2+ ......... +
bd
= O (bd) d=2
• Space Complexity G
– how many nodes can be in the queue (worst-case)?
– at depth d there are bd unexpanded nodes in the Q = d=0
O (bd)
d=1
• If the algorithm were to apply the goal test to nodes when
selected for expansion, rather than when generated, the d=2
whole layer of nodes at depth d would be expanded G
before the goal was detected and the time complexity
would be O (b^(d+1))
Examples of Time and Memory Requirements for Breadth-First
Search
• The numbers shown assume branching Depth of Expanded Time Memory
factor b = 10; 1 million nodes/second; solution nodes
1000 bytes/node. 2 110 0.11 107
milliseconds kilobytes
• The memory requirements are a bigger 4 11.110 11 10.6
milliseconds megabytes
problem for breadth-first search than is
6 104 1.1 seconds 1 gigabyte
the execution time.
8 108 2 minutes 103
gigabytes
• Exponential-complexity search problems
10 1010 3 hours 10
cannot be solved by uninformed
terabytes
methods for any but the smallest
12 1012 13 days 1 petabyte
instances
14 1014 3.5 years 99
petabytes
16 1016 350 years 10 exabytes
Characteristics of BFS
• Complete? yes in tress search if b is finite 1
• Optimal solution ? yes (if step cost are
2
identical) 3
• Search Time: O(bd) 4 5 6 7
• Memory Required: O(bd)
8 9 10 11 12 13 14 15
Depth First search (DFS) (Longest Path First)
Depth First Search (DFS) (Longest path first)
• Depth-first search always expands the https://commons.wikimedia.org/wiki/File:Depth-First-
Search.gif
deepest node in the current frontier of
the search tree. function DEPTH-FIRST-SEARCH(problem) returns a solution, or failure
node ←a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
if problem.GOAL-TEST(node.STATE) then return
SOLUTION(node)
• The search proceeds immediately to frontier ←a LIFO queue with node as the only element
the deepest level of the search tree, explored ←an empty set
loop do
where the nodes have no successors. if EMPTY?( frontier) then return failure
node←POP( frontier ) /* chooses the deepst node in frontier */
add node.STATE to explored
• As those nodes are expanded, they are for each action in problem.ACTIONS(node.STATE) do
child ←CHILD-NODE(problem, node, action)
dropped from the frontier, so then the if child .STATE is not in explored or frontier then
search “backs up” to the next deepest if problem.GOAL-TEST(child .STATE) then return
SOLUTION(child )
node that still has unexplored frontier ←INSERT(child , frontier )
successors.
Depth First Search (DFS) (Longest path first)(Cont.)
function DEPTH-FIRST-SEARCH(problem) returns a solution, or failure
node ←a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
if problem.GOAL-TEST(node.STATE) then return
SOLUTION(node)
frontier ←a LIFO queue with node as the only element
explored ←an empty set
loop do
if EMPTY?( frontier) then return failure
node←POP( frontier ) /* chooses the deepst node in frontier */
add node.STATE to explored
for each action in problem.ACTIONS(node.STATE) do
child ←CHILD-NODE(problem, node, action)
if child .STATE is not in explored or frontier then
if problem.GOAL-TEST(child .STATE) then return
SOLUTION(child )
frontier ←INSERT(child , frontier )
Time and space complexity of DFS
Time Complexity d=0
Assume (worst case) that there is 1 goal
leaf at the RHS d=1
so DFS will expand all nodes d=2
(m is maximum depth of any node) G
=1 + b + b2+ ......... + b^m
= O (b^m) d=0
Space Complexity d=1
How many nodes can be in the queue
(worst-case)? d=2
at depth m < d we have b-1 nodes d=3
at depth d we have b nodes
total = (m-1)*(b-1) + b = O(bm) d=4
Time and space complexity of DFS (Cont.)
• Explored nodes with no
descendants in the frontier are
removed from memory.
• Nodes at depth 3 have no
successors and M is the only goal
node.
• Once a node has been expanded, it
can be removed from memory as
soon as all its descendants have
been fully explored.
Characteristics of DFS
• Complete? No, Incomplete unless there is a
depth bound
• Optimal solution ? No
• Search Time: O(bm)
• Memory Required: O(bm)
Questions?
That’s
all
folks!
