Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Space 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 Cost and performance Which is better, depth-first or breadth-first? Method Time Space Path? find path? Depth-first b"m Breadth-first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian willams, Spring (36 Brian Williams, Spring 03 16 Cost and Performance Breadth-first Depth-first bm b*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 Which is better, depth-first or breadth-first? S D A B C G C G D C G C S B G A D Brian Williams, Spring 03 17 Cost and Performance Breadth-first b b*m No 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 Which is better, depth-first or breadth-first? S D A B C G C G D C G C S B G A D