Depth-First versus Breadth-First
{"Image DocumentName": "Depth-First versus Breadth-First", "Image ImageDescription": "Breadth-First always examines all the nodes at level n before proceeding to level n + 1, breadth-first search always finds the shortest path to a goal node. In a problem where it is known that a simple solution exists, this solution will be found. Unfortunately, if there is a bad branching factor, i.e., states have a high average number of descendants, the combinatorial explosion may prevent the algorithm from finding a solution using the available space. This is due to the fact that all unexpanded nodes for each level of the search must be kept on open. For deep searches, or state spaces with a high branching factor, this can become quite cumbersome. The space utilization of breadth-first search, measured in terms of the number of states on open, is an exponential function of the length of the path at any time. If each state has an average of B children, the number of states on a given level is B times the number of states on the previous level. This gives Bn states on level n. Breadth-first search would place all of these on open when it begins examining level n. This can be prohibitive if solution paths are long. Institute of Computing, Bahauddin Zakariya University, Multan.", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}