Search Methods

• Search can be characterized as finding a path through a graph or tree structure

• This requires moving from node to node after successively expanding &
generating connected nodes.

• The process of generating all of the children of a parent is also known as

expanding the node

• A search procedure is a strategy for selecting the order in which nodes are
generated & a given path selected

• Search problems can be classified by the information used to carry out a given
strategy
฀ blind or uninformed search
฀ informed or directed search
8/25/2020 1
 Search Strategies
• A strategy is defined by picking the order of node expansion

• Strategies are evaluated along the following dimensions:

฀Completeness: does it always find a solution, if one exists?
฀Time complexity: number of nodes generated/expanded
฀Space complexity: maximum number of nodes in memory
฀Optimality: does it always find a least-cost solution?

• Time and space complexity are measured in terms of

• b - maximum branching factor of the search tree
• d - depth of the least-cost solution
• m - maximum depth of the state space (may be ∞)
8/25/2020 2
 Uninformed or Blind Search
• Breadth-first search

• Uniform-cost search

• Depth-first search

• Depth-limited search

• Iterative deepening search

8/25/2020 3
 Breadth – first Search (BFS)
• Algorithm
• begin
• put start node in OPEN, found = false;
• while OPEN not empty & not(found) do
• begin
• remove top-most node n from OPEN & put n in CLOSED;
• expand n generating all its successors;
• put those successors (in no particular order) at the end of OPEN except the
successor already appearing in OPEN or CLOSED; // can happen for graphs
• direct a backward pointer to n from each successor ni;
• if any of the successor is a goal node then
• found = true;
• else if any of ni is a dead end then
• remove it from OPEN ;
• end
• if OPEN is empty then
• output failure message;
• else
• output solution path by tracing back thru pointers;
• end

8/25/2020 4
 Breadth – first Search (BFS)
Example
S
OPEN CLOSED
S
m1 m2 S S

m3 m1m2 S m1

m2 m3 m4 S m1 m2

m3 m4 m5 S m1 m2 m3

m4 m5 S m1 m2 m3 m4
m4 m5 m5 m6 r

m6 r m3 m6
Note that m6 is a dead end m1 m4 r
But it is there in OPEN S
As FOUND is true already m2 m5
8/25/2020 5
 Remarks
• OPEN holds nodes generated in the explicit graph, but not yet expanded.
CLOSED holds list of expanded nodes in the graph

• Complete? Yes (if b is finite)

• Time? 1 + b + b2 + b3 + : : : + bd = (bd+1 – 1) / (b – 1) = O(bd),
• If the goal test is applied when selected for expansion, rather than when
generated, in the worst-case the whole layer at depth d may get expanded
before the goal is tested and in that case complexity will become O(bd+1)
• Space - O(bd) (keeps every node in memory)
• Is it Optimal? - Yes (if cost = 1 per step); not optimal in general

• Advantages
• BFS guarantees to find goal node if one exists. But the solution may not be
optimal in terms of cost, if the cost of exploring each edge is not same.
• BFS produces faster solution in certain graphs.
• Disadvantages
• Higher memory required.
• More house-keeping work, more overhead & relatively difficult to implement.
• Not suitable for human problem solving approach.
8/25/2020 6
 Uniform cost search

• Uniform cost search modifies the breadth-first strategy by always

expanding the lowest-cost node on the fringe (as measured by the
path cost g(n)), rather than the lowest-depth node, where g(n):
cost of currently known best path from start node s to n

• It is easy to see that breadth-first search is just uniform cost search

with g(n) = DEPTH(n)

• When certain conditions are met, the first solution that is found is
guaranteed to be the cheapest solution, because if there were a
cheaper path that was a solution, it would have been expanded
earlier, and thus would have been found first
8/25/2020 7
• begin
Uniform cost search algorithm
• g(s) = 0; put s in OPEN; found = false;
• while OPEN not empty & not(found) do
• begin
• select a node n from OPEN with minimum g-value(resolve ties arbitrarily but in
• favor of a goal node);
• remove n from OPEN & put n in CLOSED;
• if n is a goal node then found = true;
• else begin
• expand n generating all its immediate successors ni (if any);
• for each ni do
• begin
• g = g(n) + c(n, ni);
• if ni is not already in OPEN or CLOSED then
• begin
• g(ni) = g; put ni in OPEN;
• direct backward pointer from ni to n;
• end
• else if ni is in OPEN and g(ni) > g then
• begin
• g(ni) = g;
• redirect backward pointer from ni to n;
• end
• end
• end
• end
• if (found) then output g(n) & solution path thru pointers;
• else output failure message;
• 8/25/2020
end 8
Uniform cost search – typical example
S = v0
2 g(s) = 0
1 g(v4) = 2
v1 g(v1) = 2
v2 g(v2) = 1
g(v5) = 4
2 g(v6) = 7
5 3 g(v3) = 7
g(v6) = 5

v3 v4 v5
5
2
1

v6 v7
 Remarks
• Uniform cost works with g(n) values of node. It doesn’t use any
information about the cost of the remaining path from a node to a
goal node. So, in many problems the uniform cost method tends to
expand too many nodes
• It is possible to cut down the no. of node expansion by using the
estimate of the cost of the remaining path from a node to a goal
node
• Note that we do not test whether it is a goal node, when we
generate the node but only when we expand. Why? – Because
otherwise we may miss the best path to reach it.
• Complete?? Yes, if step cost ≥ ∈
• Time?? # of nodes with g ≤ cost of optimal solution, O(b⌈C*/ ∈⌉)
where C* is the cost of the optimal solution
• Space?? # of nodes with g ≤ cost of optimal solution, O(b⌈C*/ ∈⌉)
• Optimal?? Yes - nodes expanded in increasing order of g(n)
8/25/2020 10
 Depth First Search (DFS) algorithm
• begin
• put start node s into OPEN;
• found = false;
• while OPEN not empty & not(found) do
• begin
• remove top most node n from OPEN & put it in CLOSED;
• if depth of n = depth bound then // depth bound is set very high, say infinity
• CLEAN-UP CLOSED;
• else begin
• expand n generating all its successors;
• put these successors (in no particular order) on top of OPEN
• except the successor already appearing in CLOSED;
• Direct backward pointer to n for each succ. ni;
• If any of ni is a goal node then
• Found = true;
• Else if any ni is a dead end then
• Remove it from OPEN & CLEAN-UP CLOSED;
• end
• end
• if OPEN is empty then
• output “solution path not found”;
• else
• output the solution by tracing back thru pointers;
•8/25/2020
end { End of Algorithm } 11
 Depth First Search (DFS)
Example
S OPEN CLOSED
S

m1 m2 S S

m3 m1m2 S m1

m3m4m2 S m1 m3

m4 m5 m4 m2 S m1 m3 m4

m6 r m5 m4 m2
m4 m5
m4 m6
m6 r m3 r
m1 m5
S m4
m2
8/25/2020 12
 Depth First Search (DFS)
Example

A OPEN CLOSED
A
B F BF A

C D G CDF AB

DF AB

EF ABD Due to CLEAN-UP

E H F A

G AF
I H AFG

I AFGH

8/25/2020 13
 Remarks
• CLEAN-UP operation means removing of all the nodes from CLOSED that don’t have any child in
OPEN

• CLOSED will contain only the expanded nodes in the current path, reduces size of CLOSED & save
memory.

• CLOSED list forms a single path from the start node to the currently expanded node with CLEAN-
UP operations. This restricts maximum storage which is: depth bound * branching factor

• Complete?? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states
along path
-฀ complete in finite spaces

• Time?? O(bm): terrible if m is much larger than d

but if solutions are dense, may be much faster than breadth-first
• Space?? O(bm), i.e., linear space!

• Optimal?? No

8/25/2020 14
 Depth-limited Search
• Depth-limited search is a depth-first search with depth limit l, i.e.,
nodes at depth l have no successors
• The drawback of DFS is that it can make a wrong choice & get
stuck going down a very long (or even infinite) path when a
different choice would lead to a solution near the root of the
search tree
• The depth limit solves the infinite-path problem
• The problem of unbounded trees can be alleviated by supplying
depth-first search with a predetermined depth limit l, i.e. nodes
at depth l are treated as if they have no successors
• But, it also introduces an additional source of incompleteness if
we choose l < d, i.e., the shallowest goal is beyond the depth limit
• Time needed: O(bl), Space needed: O(bl)
• DFS viewed as a special case of depth-limited search with l = ∝
8/25/2020 15
 Iterative deepening depth-first search

• This is a general strategy, often used in combination with depth-

first search, that finds the best depth limit

• It does this by gradually increasing the limit – first 0, then 1, then

2, & so on – until a goal is found

• This will occur when the depth limit reaches d, the depth of the
shallowest goal node

• Iterative deepening combines the benefits of DFS & BFS

8/25/2020 16
8/25/2020 17
8/25/2020 18
8/25/2020 19
8/25/2020 20
 Remarks
• Complete?? Yes
• Time - (d)b1 + (d -1)b2 + : : : + (1)bd = O(bd) (See next slide)
• Space - O(bd)
• Optimal? Yes, if step cost = 1
• Can be modified to explore uniform-cost tree
• Numerical comparison for b = 10 and d = 5, solution at far right
leaf:
• N(IDS) = 50 + 400 + 3,000 + 20,000 + 100,000 = 123, 450
• N(BFS) = 1+10 + 100 + 1, 000 + 10, 000 + 100, 000 = 1, 11,111
• an iterative deepening search from depth 1 all the way down to
depth d expands only about 11 % more nodes than a single
breadth-first or depth-limited search to depth d, when b = 10
8/25/2020 21
 Time Complexity of Iterative Deepening –
Arithmetico Geometric Progression
• Let S = (d)b1 + (d -1)b2 + ……………… + (1)bd
• bS = (d)b2 + (d-1)b3 + ……………… +(1)bd+1
S = (d)b1 + (d -1)b2 + ……………………+ (1)bd
• So bS – S = (b2 + b3 +......+ bd) + bd+1 – db
• S(b – 1) = b2 (bd- 1)/(b – 1) – db (a polynomial
of degree d + 1)
• S = O (bd) (a polynomial of degree d)