why DFS is not optimal but BFs is optimal

Question

I have this question in my mind for long but never got reasonable answer for that :

Usually in artifitial intelligent course when it comes to search it is always said that BFS is optimal but DFS is not but I can come up with many example that shows with DFS we can even get the answer faster. So can anyone explain it ? Am I missing something?

Solution 1

Optimal as in "produces the optimal path", not "is the fastest algorithm possible". When searching a state space for a path to a goal, DFS may produce a much longer path than BFS. Note that BFS is only optimal when actions are unweighted; if different actions have different weights, you need something like A*.

Solution 2

This is because by optimal strategy they mean the one whose returned solution maximizes the utility.

Regarding this, nothing guarantees that the first solution found by DFS s optimal. Also BFS is not optimal in a general sense, so your statement as-is is wrong.

The main point here is about being guaranteed that a certain search strategy will always return the optimal result. Any strategy might be the best in a given case, but often (especially in AI), you don't know in what specific case you are, at most you have some hypothesis on that case.

However, DFS is optimal when the search tree is finite, all action costs are identical and all solutions have the same length. However limitating this may sound, there is an important class of problems that satisfies these conditions: the CSPs (constraint satisfaction problems). Maybe all the examples you thought about fall in this (rather common) category.

Comments

[barak manos]

Optimal in terms of time-complexity (execution performance) or space-complexity (memory usage)? Or in the actual quality of the output, when the best possible solution is very hard to calculate (such as in the case of a greedy algorithm for example)?

[Stefano Sanfilippo]

@barakmanos usually, in the context of AI, optimality refers to the solution, not to the strategy. I guess this is what the OP means.

[HMdeveloper]

Thanks for your great answer. What about this scenario: The goal is in the left most branch of tree. Which one is optimal in this situation?

[user2357112]

@HamedMinaee: If you know the goal is in the left-most branch of the tree, you don't need a search algorithm at all. Just take the first action in the list every time. It's not a particularly common case, so it's not useful to optimize for that case.

[Stefano Sanfilippo]

You neeed a specific heuristic to use A*. If you can't find one, then Uniform Cost Search (a modified BFS) might help.

[user2357112]

@StefanoSanfilippo: Well, you can usually at least get something to use as a heuristic. If you've already written A* and you can't come up with a heuristic, the "Are We There Yet?" function will get you UCS with a bit of overhead.

[Anton Menshov]

Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference.