Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Path? find path? Yes for finite graph 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 Growth for best First Search b= 10; 10,000 nodes/sec, 1000 bytes/node Memo secon I megabyte 1ll,10 11 second 19 minute 10 gigabytes 10 129 days 101 terabytes 12 1013 35 years 10 petabytes 3.52 Brian willams, Spring 0311 Brian Williams, Spring 03 26 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 27 Growth for Best First Search b = 10; 10,000 nodes/sec; 1000 bytes/node 10 3,523 years 1 exabyte 15 14 10 35 years 10 petabytes 13 12 10 129 days 101 terabytes 11 10 10 31 hours 1 terabyte 9 8 10 19 minutes 10 gigabytes 7 6 4 111,100 11 seconds 106 megabytes 2 1,100 .11 seconds 1 megabyte Depth Nodes Time Memory