Analysis of Uninformed Search methods Brian C Williams 16410-13 Slides adapted from Sept.17,2003 6.034 Tomas Lozano perez, Russell and Norvig AIMA Sian willams, Spring o3 Outline Analysis Depth-first search Breadth-first search · Iterative deepening williams, Spring a3
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
Elements of Algorithmic analysis · Soundness is a solution returned by the algorithm guaranteed to be Completeness is the algorithm guaranteed to find a solution when there is Time complexity how long does it take to find a solution? Space complexity how much memory does it need to perform search? Sian willams, Spring o3 Characterizing Search algorithms Level o Level 1 Level 2 b= maximum branching factor, number of children d= depth of the shallowest goal node m= maximum length of any path in the state space williams, Spring a3
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
Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Path? find path? Breadth- first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Sian willams, Spring o3 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Level 0 Level 2 ○○(db*b Sado doodad williams, Spring a3
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 A B 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 Tdfs = bm + … b + 1 Level 1 Level 2 Level 0 b*1 b*b b*bm-1 . . . Level m 1
Cost Using Order notation Worst case time T is proportional to number of nodes visited evel 1 b*1 b*b Level 2 Order Notation ·T=Oe)ifT≤c* e for some constant c Ts=[bm+…b+lcds O(bm) for large b O(bm+) more conservatively Sian willams, Spring o3 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Level 0 Level 2 ○○(db*b Sado doodad b* Tas=bmt Tas=[bm-1][b-1]*c where caf is time per node williams, Spring a3
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*bm-1 . . . Order Notation • T = O(e) if T ≤ c * e for some constant c Tdfs = [bm + … b + 1]*cdfs = O(bm) for large b = O(bm+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 Tdfs = bm + … b + 1 b * Tdfs = bm+1 + bm + … b Solve recurrence [b – 1] * Tdfs = bm+1 – 1 Tdfs = [bm+1 – 1] / [b – 1] *cdfs where cdfs is time per node Level 1 Level 2 Level 0 b*1 b*b b*bm-1 . . . Level m 1
Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Path? find path? b Breadth- first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Sian willams, Spring o3 Worst Case Space for Depth-first Worst case space Sas is proportional to maximal length of Q Level m 0○b1 If a node is queued its parent and parents siblings have been queued Ss≥(b-1)*m+1 The children of at most one sibling is expanded at each level 少Sa5=(b-1)m+1 Sat =o(b*m) williams, Spring a3 5
5 Brian Williams, Spring 03 14 Cost and Performance Breadth-first b Depth-first m 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 A B 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 Sdfs is proportional to maximal length of Q • If a node is queued its parent and parent’s siblings have been queued. Î Sdfs ≥ (b-1)*m+1 The children of at most one sibling is expanded at each level. Î Sdfs = (b-1)*m+1 • Sdfs = O(b*m) Level 1 Level m Level 0 b-1 b-1 b . .