Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Time Path? find path? Breadth- first es Worst case time ts proportional to number-ef nodes visited Worst case space is proportional to maximal length of Q Sian willams, Spring o3 Cost and performance 6. 034 Style What the Electronic Tutor Thinks Which is better, depth-first or breadth-first? cG assumes d= m in the worst case and calls both d Takes the conservative estimate: bd+1=O(b+1) Search Shortest Method Path? Depth-first Yes for finite graph Breadth-first Yes uit ho Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian willams, Spring 03 1212 Brian Williams, Spring 03 28 Cost and Performance b Yes unit lngth Yes d+1 b Breadth-first d+1 b b*m No Yes for finite graph Depth-first m 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 A B 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 b Yes unit lngth Yes d b Breadth-first d+1 b b*d No Yes for finite graph Depth-first d+1 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 A B 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: bd + … 1 = O(bd+1)