Does depth-first search always stop when it has found the leftmost solution?

Question

I'm a fresh learner of AI. I was told that depth-first search is not an optimal searching algorithm since "it finds the 'leftmost' solution, regardless of depth or cost". Therefore, does it mean that in practice, when we implement DFS, we should always have a checker to stop the search when it finds the first solution (also the leftmost one)?

Answer 1

One of the more standard assumptions when first introducing new students to search algorithms (like Depth-First Search, Breadth-First Search which you've also likely heard about or will hear about soon, etc.) is indeed that our goal is to find some sort of solution, and only find one.

If our intention is to find just a single solution, then yes, you will need to check at every node whether that is a solution node, and you can stop the search process once you've found one.

In practice, there can be all kinds of variants of this idea. Maybe in a different case you are interested in finding all solutions, rather than a single one; in such a case you would naturally not stop the search process after finding the first one, but continue searching.

So, to conclude, it really depends on exactly what you want, why are you using a search algorithm. If you only care about finding a solution, you can stop when you have one.