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 55 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 . .