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)?

Thanks guys!

  • 1
    $\begingroup$ Welcome to AI.SE...If I remember correctly then DFS is not an optimal searching algo because the depth maybe infinite in the branch you are searching resulting in you not finding a solution. $\endgroup$ – DuttaA Sep 7 '18 at 13:33
  • 2
    $\begingroup$ Thanks DuttaA! Indeed, I was taught that it's not an optimal algorithm neither, but I didn't think in this "infinite way", I thought that was because it always halts at the first-found solution. Now that we know that should depend on what we need, I think your point makes more sense on explaining why it is not an optimal algorithm. 👍 $\endgroup$ – Hang Sep 8 '18 at 0:52

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.

  • 1
    $\begingroup$ Thank you, that's also what I think! It should depend on what we need for the solutions to alternate the operation. Yea! :D $\endgroup$ – Hang Sep 8 '18 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.