5
$\begingroup$

In literature in general, are DFS and BFS considered to be special cases of best-first search?

Suppose the cost function is:

$f(n) = g(n) + h(n)$

Is it correct to reason that if and $g(n) = depth(n)$, then

If $\forall_n h(n) = 0$, we have a breadth-first search

If $h(n) = i$, where i is the number of nodes visited before visiting, we have depth-first search.

?

Are depth-first and breadth-first search usually considered special cases of best-first search?

Improve this question
$\endgroup$
6
  • $\begingroup$ Which literature have you checked? I don't know that any classic algorithms text even discussion "best-first", so the general answer is "no". Are you interested in literature from a specific area? $\endgroup$
    – Raphael
    Commented Sep 20, 2016 at 19:42
  • $\begingroup$ No, i am just checking because it was asked on a past exam and I am thinking about it and studying for the next exam. $\endgroup$
    – Rodrigo Stv
    Commented Sep 20, 2016 at 19:56
  • $\begingroup$ So, the question you actually have is if BFS and DFS can be expressed as best-first search? $\endgroup$
    – Raphael
    Commented Sep 20, 2016 at 20:13
  • $\begingroup$ No it, it was more like... if in teaching & literature surveys they are presented as special cases of best-first search. May be it is not an appropriate question. But sometimes exams pose that kind of question which asks more about what you've seen in university than about computing itself. Somewhat of a pedagogical question. $\endgroup$
    – Rodrigo Stv
    Commented Sep 20, 2016 at 20:17
  • $\begingroup$ I am assuming you're looking at this from a AI perspective? As best-first and the function you posted (although slightly different in its traditional context) appear most commonly AI. Yes/no? $\endgroup$
    – user40759
    Commented Sep 20, 2016 at 21:12

1 Answer 1

Reset to default
6
$\begingroup$

The answer to your question is, in both cases, No.

The reason is as follows: Both depth-first search and breadth-first search are uninformed search algorithms. A distinctive feature of these algorithms is that they stop once the goal node is generated.

Now, if all operators are given the same cost (so that you consider them to have the same cost equal to 1), then:

  1. Breadth-first search is guaranteed to find the solution, and also to deliver an optimal one. This is, it is both complete and admissible (some people refer to this also as been optimal).
  2. Depth-first search, however, is neither complete nor admissible because it is bounded by a maximum depth. It might well happen that the goal lies beyond it and thus, it cannot guarantee to find it.

Best-First search, on the other hand, uses an OPEN list where nodes are sorted in increasing order of $f(n)=g(n)+h(n)$ where: $g(n)$ is the cost of the current path from the start node to node $n$, and $h(n)$ is an estimate of the remaining effort to reach the goal from $n$. As such, $f(n)$ stands for an estimate of the best path from the start node to the goal that goes through node $n$. However, in contrast with the case of uninformed search algorithms, Best-first search algorithms halt only when the solution is about to be expanded! This makes a lot of sense. Under a number of assumptions (such as admissibility of the heuristic function), sorting nodes in ascending order guarantees that the true cost is above the estimation given by $f(n)$, so that only when expanding a goal you can ensure that all the other nodes stand for potential solutions with a cost greater or equal than the cost of the current solution.

Therefore, from your definitions of $f(n)$ (and assuming unit costs):

  1. Making $f(n)=\mathrm{depth}(n)$ would result in an algorithm that expands nodes in the same order than a breadth-first search algorithm (up to tie-breaking). In addition, it will expand more nodes than it since after generating the goal, it has to expand all nodes in the current level before expanding the goal ---in the next level.

  2. Your second choice, $f(n)=\mathrm{depth}(n) + i$, with $i$ been "the number of nodes visited before visiting" is rather confusing to me. I do not know what you might mean by "visited before visiting". In spite of it, however, note that a Best-First search algorithm would proceed further after generating the goal node much the same.

Your question makes a lot of sense. In case you want to access additional material related to it, please refer to Robert C. Holte. Common Misconceptions Concerning Heuristic Search". Symposium on Combinatorial Search SoCS 2010. Pages 46--51. See, specifically, the bottom of the left column in page 49.

Hope this helps,

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks to you Rodrigo for upvoting the question and also for marking it as been solved. Gracias! Espero volver a verte en stackexchange.com :) $\endgroup$
    – Carlos Linares López
    Commented Sep 21, 2016 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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