Search Strategies CMPT 420 / CMPG 720 Uninformed Search Strategies Uninformed search strategies use only the information available in the problem definition Breadth-first search Uniform-cost search
Depth-first search Depth-limited search Iterative deepening search Breadth-first search Expand shallowest unexpanded node 4 Breadth-first search Expand shallowest unexpanded node
5 Breadth-first search Expand shallowest unexpanded node 6 Breadth-first search Expand shallowest unexpanded node Examine siblings before children
7 Breadth-first search Expand shallowest unexpanded node Implementation: o Frontier is a FIFO queue, i.e., new successors go at end 8 Example: Romania
11 Graph Representation Adjacency list representation of G = (V, E) o An array of V lists, one for each vertex in V o Each list Adj[u] contains all the vertices v such that there is an edge between u and v Adj[u] contains the vertices adjacent to u (in arbitrary order) o Can be used for both directed and undirected graphs
1 2 3 5 4 Undirected graph
1 2 5 2 1 5
3 2 4 4 2
5 3 5 4 1 2
/ 4 3 / / 12
Graph Representation Adjacency matrix representation of G = (V, E) o Assume vertices are numbered 1, 2, V o The representation consists of a matrix A V x V : o aij = 1 if (i, j) E 0 1
otherwise 2 3 5 4 Undirected graph
1 2 3 4 5
1 0 1 0 0 1
2 1 0 1 1
1 3 0 1 0 1
0 4 0 1 1
0 1 5 1 1 0
1 0 For undirected graphs matrix A is symmetric: aij = aji
A = AT 13 Breadth-first search Is BFS guaranteed to find a solution if one exists? Breadth-first search Is BFS guaranteed to find a solution if one
exists? Problem? Breadth-first search Guaranteed to find a solution if one exists Problem: it might take a very long time to find a solution! o note how much of tree is expanded that doesn't contribute towards goal
Properties of breadth-first search Complete? o Yes Optimal? Time? Space? 17
Properties of breadth-first search Complete? o Yes Optimal? o Yes (if cost = 1 per step) Time? Space? 18
Properties of breadth-first search Complete? o Yes Optimal? o Yes (if cost = 1 per step) Time? o 1+b+b2+b3+ +bd = O(bd) o exponential in d
Space? 19 Properties of breadth-first search Complete? o Yes Optimal? o Yes (if cost = 1 per step)
Time? o 1+b+b2+b3+ +bd = O(bd) o exponential in d Space? o O(bd) (O(bd-1) nodes in the explored set and O(bd) nodes in the frontier) 20
Uniform-cost search Expand the node with the lowest path cost g(n) (Cheapest search) Implementation: 21 Uniform-cost search Expand the node with the lowest path cost g(n) (Cheapest search) Implementation:
o Frontier = priority queue ordered by path cost g(n) 22 Example: Romania 23 Properties of uniformcost search Equivalent to breadth-first if step costs all equal
Complete? o Yes Optimal? o Yes nodes expanded in increasing order of path cost Time? o O(bd) Space?
o O(bd) Depth-first search Expand deepest unexpanded node 25 Depth-first search Expand deepest unexpanded node
26 Depth-first search Expand deepest unexpanded node Examine children before siblings 27 Depth-first search Expand deepest unexpanded node Examine children before siblings
28 Depth-first search Expand deepest unexpanded node Examine children before siblings 29 Depth-first search Expand deepest unexpanded node
Examine children before siblings 30 Depth-first search Expand deepest unexpanded node Examine children before siblings 31 Depth-first search
Expand deepest unexpanded node Examine children before siblings 32 Depth-first search Expand deepest unexpanded node Examine children before siblings 33
Depth-first search Expand deepest unexpanded node Examine children before siblings 34 Depth-first search Expand deepest unexpanded node Examine children before siblings 35
Depth-first search Expand deepest unexpanded node Implementation: o Frontier = LIFO queue 36 Depth-first search
Example More efficient (in some cases) than breadth-first search o Problem: what if some branch is very long: can spend a lot of time searching useless cases Properties of depth-first search Complete? o Yes (if every branch has finite number of
states) Optimal? o No 39 search Complete? o Yes (if every branch has finite number of states) Optimal?
o No Time? o O(bm): terrible if m is much larger than d o but if solutions are dense, may be much faster than breadth-first 40 Comparing Uninformed Search Strategies
Time and space complexity are measured in o b maximum branching factor of the search tree o m maximum depth of the state space o d depth of the least cost solution search Complete? o Yes (if every branch has finite number of states) Optimal? o No
Time? o O(bm): terrible if m is much larger than d o but if solutions are dense, may be much faster than breadth-first Space? o O(bm), i.e., linear space! 42
Depth-limited search Depth-first search with depth limit l, i.e., nodes at depth l have no successors 20 cities in map of Romania o l =19 Any city can be reached from any other city in at most 9 steps. o Diameter gives a better depth limit. Properties of
Depth-limited search Complete? o Yes (if the goal is within the limit) Optimal? o No Time? o O(bl) Space? o O(bl)
44 Properties of Depth-limited search Depth-first search can be viewed as a special case with l = infinity Main advantage that the search process can't descend forever (in a branch without solution). However, it will not find a solution if all
solutions require a depth greater than the limit. o (This is likely when l is unknown.) How to overcome this and maintain the advantages of depth limited search? Iterative deepening search Gradually increases the limit 0, 1, 2, If don't find solution, increase depth and
try again Combines the benefits of depth-first and breadth-first search. Iterative deepening search l =0 48 =1
49 =2 50 =3 51 Properties of iterative
deepening search Complete? o Yes Optimal? o Yes, if step cost = 1 Space? o O(bd), linear space Time?
o d b1 + (d-1)b2 + + (1)bd = O(bd) 52 Time consuming?? Can show this doesn't really increase the number of examined nodes by much over depth-first search: o For large graphs, "most" of the nodes are at the outermost edge
o If branching factor is b, then there are b2 nodes in the 2nd layer, b3 in the 3rd, bn in the nth o Thus number of nodes at depth d is 1 + b + b2 + b3 + ... + bd o If d =4, b =10, get 1 + 10 + 102 + 103 + 104 = 11,111 nodes o For iterative deepening, need to consider some nodes more than once: b(d) + b2(d - 1) + b3(d - 2) + ... + bd o d = 4, b = 10 gives 1*(4 + 1) + 10 * 4 + 102 * 3 + 103 * 2 + 104 =
12,345 visitations: a 10% increase o in general, if branching factor is 10, visit nodes 11% more often by iterative deepening Properties of iterative deepening search Combines the benefits of depth-first search o Memory space O(bd) o linear!
breadth-first search o Always complete and optimal Search Start the process simultaneously from the initial start and backwards from the goal state whether the frontiers of the two intersect To reduce the complexity
bd/2 + bd/2 < bd
