why DFS is not optimal but BFs is optimal

Question

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

Usually in an artificial intelligence 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 examples that show with DFS we can even get the answer faster. So can anyone explain it? Am I missing something?

Answer 1

As far as the optimality of the solution is concerned, the BFS algorithm stops at the shallowest goal found. The shallowest goal node need not compulsorily be the optimal goal node. BFS is optimal if the path cost is a non-decreasing function of d(depth). Normally, BFS is applied when all the actions have the same cost.

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

If you are looking to learn more about Artificial Intelligence then visit this Artificial Intelligence Course which will cover topics like Simulated annealing algorithm Euclidean distance, Pearson correlation coefficient, Brute force search algorithms, Backtracking, Traveling salesman problem, NeuroEvolution of augmenting topologies, Fitness function, Resolution algorithm,k-nearest neighbors algorithm, Markov model, Genetic algorithm, deep first iterative deeping and many more.