1 Brian Williams, Spring 03 1 Analysis of Uninformed Search Methods Brian C. Williams 16.410-13 Sept. 17, 2003 Slides adapted from: 6.034 Tomas Lozano Perez, Russell and Norvig AIMA Brian Williams, Spring 03 7 Outline ?Analysis – Depth-first search – Breadth-first search ? Iterative deepening 2 Brian Williams, Spring 03 8 Elements of Algorithmic Analysis ? Soundness: – is a solution returned by the algorithm guaranteed to be correct? ? Completeness: – is the algorithm guaranteed to find a solution when there is one? ? Time complexity: – how long does it take to find a solution? ? Space complexity: – how much memory does it need to perform search? Brian Williams, Spring 03 9 Characterizing Search Algorithms d = 1 Level 1 Level 2 Level 0 b = 3 b = maximum branching factor, number of children d = depth of the shallowest goal node m = maximum length of any path in the state space m = 1 3 Brian Williams, Spring 03 10 Cost and Performance Breadth-first Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Which is better, depth-first or breadth-first? Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D BA C G C G D C G C S B G A D Brian Williams, Spring 03 11 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited T dfs = b m + … b + 1 Level 1 Level 2 Level 0 b*1 b*b b*b m-1 . . . Level m 1 4 Brian Williams, Spring 03 12 Cost Using Order Notation Worst case time T is proportional to number of nodes visited Level 1 Level 2 Level 0 b*1 b*b b*b m-1 . . . Order Notation ?T = O(e) if T ≤ c * e for some constant c T dfs = [b m + … b + 1]*c dfs = O(b m )for large b = O(b m+1 ) more conservatively 1 Brian Williams, Spring 03 13 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited T dfs = b m + … b + 1 b * T dfs = b m+1 + b m + … b Solve recurrence [b – 1] * T dfs = b m+1 –1 T dfs = [b m+1 – 1] / [b – 1] *c dfs where c dfs is time per node Level 1 Level 2 Level 0 b*1 b*b b*b m-1 . . . Level m 1 5 Brian Williams, Spring 03 14 Cost and Performance Breadth-first b m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Which is better, depth-first or breadth-first? Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D BA C G C G D C G C S B G A D Brian Williams, Spring 03 15 Worst Case Space for Depth-first Worst case space S dfs is proportional to maximal length of Q ? If a node is queued its parent and parent’s siblings have been queued. ? S dfs ≥ (b-1)*m+1 The children of at most one sibling is expanded at each level. ?S dfs = (b-1)*m+1 ?S dfs = O(b*m) Level 1 Level m Level 0 b-1 b-1 b . . . 6 Brian Williams, Spring 03 16 Cost and Performance Breadth-first b*mb m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? S D BA C G C G D C G C S B G A D Brian Williams, Spring 03 17 Cost and Performance Breadth-first Nob*mb m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? S D BA C G C G D C G C S B G A D 7 Brian Williams, Spring 03 18 Cost and Performance Breadth-first Yes for finite graphNob*mb m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? S D BA C G C G D C G C S B G A D Brian Williams, Spring 03 19 Cost and Performance Breadth-first Yes for finite graphNob*mb m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method S D BA C G C G D C G Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? C S B G A D 8 Brian Williams, Spring 03 20 Worst Case Time for Breadth-first Worst case time T is proportional to number of nodes visited Level 1 Level d Level 0 T bfs = [b d+1 + b d + … b + 1 - b]*c bfs = O(b d+1 ) Level d+1 b b d+1 -b . . . 1 b d Brian Williams, Spring 03 21 Cost and Performance b d+1 Breadth-first Yes for finite graphNob*mb m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D BA C G C G D C G Which is better, depth-first or breadth-first? C S B G A D 9 Brian Williams, Spring 03 22 Worst Case Space for Breadth-first Level 1 Level d Level 0 S bfs = [b d+1 - b + 1]*c bfs = O(b d+1 ) Level d+1 b b d+1 -b . . . 1 b d Worst case space S dfs is proportional to maximal length of Q Brian Williams, Spring 03 23 Cost and Performance b d+1 b d+1 Breadth-first Yes for finite graphNob*mb m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D BA C G C G D C G Which is better, depth-first or breadth-first? C S B G A D 10 Brian Williams, Spring 03 24 Breadth-first Finds Shortest Path G Level 1 Level d Level 0 G Level d+1 First reached Nodes visited earlier can’t include G Assuming each edge is length 1, other paths to G must be at least as long as first found Brian Williams, Spring 03 25 Cost and Performance Yes unit lngthb d+1 b d+1 Breadth-first Yes for finite graphNob*mb m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D BA C G C G D C G Which is better, depth-first or breadth-first? C S B G A D 11 Brian Williams, Spring 03 26 Cost and Performance YesYes unit lngthb d+1 b d+1 Breadth-first Yes for finite graphNob*mB m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D BA C G C G D C G Which is better, depth-first or breadth-first? C S B G A D Brian Williams, Spring 03 27 Growth for Best First Search b = 10; 10,000 nodes/sec; 1000 bytes/node 1 exabyte3,523 years10 15 14 10 petabytes35 years10 13 12 101 terabytes129 days10 11 10 1 terabyte31 hours10 9 8 10 gigabytes19 minutes10 7 6 106 megabytes11 seconds111,1004 1 megabyte.11 seconds1,1002 MemoryTimeNodesDepth 12 Brian Williams, Spring 03 28 Cost and Performance YesYes unit lngthb d+1 b d+1 Breadth-first Yes for finite graphNob*mb m Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D BA C G C G D C G Which is better, depth-first or breadth-first? C S B G A D Brian Williams, Spring 03 29 Cost and Performance 6.034 Style: What the Electronic Tutor Thinks YesYes unit lngthb d b d+1Breadth-first Yes for finite graphNob*db d+1Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D BA C G C G D C G Which is better, depth-first or breadth-first? C S B G A D ? Assumes d = m in the worst case, and calls both d. ? Takes the conservative estimate: b d + … 1 = O(b d +1) 13 Brian Williams, Spring 03 30 Outline ?Analysis ? Iterative deepening Brian Williams, Spring 03 31 Iterative Deepening (IDS) S D BA C G C G D C G Level 1 Level 2 Level 0 Level 3 Idea: ? Explore tree in breadth-first order, using depth-first search. ?Search tree to depth 1, …. 14 Brian Williams, Spring 03 32 Iterative Deepening (IDS) S D BA C G C G D C G Level 1 Level 2 Level 0 Level 3 Idea: ? Explore tree in breadth-first order, using depth-first search. ?Search tree to depth 1, then 2, …. Brian Williams, Spring 03 33 Iterative Deepening (IDS) S D BA C G C G D C G Idea: ? Explore tree in breadth-first order, using depth-first search. ?Search tree to depth 1, then 2, then 3…. Level 1 Level 2 Level 0 Level 3 15 Brian Williams, Spring 03 34 Cost of Iterative Deepening ?T ids = d + 1 + (d)b + (d - 1)b 2 +. . . b d = O(b d ) ?T bfs = 1+b + b 2 + . . . b d + (b d+1 –b) = O(b d+1 ) ?Iterative deepening performs better than breadth-first! S D BA C G C G D C G d*b 1*b d . . . d+1 2*b d-1 Level 1 Level 2 Level 0 Level d Brian Williams, Spring 03 35 Summary ? Most problem solving tasks may be encoded as state space search. ? Basic data structures for search are graphs and search trees. ? Depth-first and breadth-first search may be framed, among others, as instances of a generic search strategy. ? Cycle detection is required to achieve efficiency and completeness. ? Complexity analysis shows that breadth-first is preferred in terms of optimality and time, while depth-first is preferred in terms of space. ? Iterative deepening draws the best from depth-first and breadth-first search.