Intelligent Systems Lecture Notes

14 September 2011 • Basic State-Space Search


DFS explores one path at a time. The only way it could exploit cost information is to choose the cheapest available path when backtracking. While choosing the cheapest next step is better than choosing a more expensive one, the cheapest overall path is a global property, and DFS makes only local decisions.

In contrast, BFS explores all potential paths (up to some depth) at once, and choosing the cheapest path among all available paths is a (relatively) global decision, leading more directly to a cheapest overall path.


This page last modified on 2006 January 24.