1
$\begingroup$

I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$ nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor.

Why isn't it $b^d$?

Why are $1+b+b^2+···+b^{d-1}$ (the previously searched depths) maintained in memory?

If it's a matter of completeness, then (a complete implementation of) DFS would suffer from the same problem.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Can you give some pointers? $\endgroup$ – Yuval Filmus Jun 2 '19 at 18:02
  • $\begingroup$ @YuvalFilmus What do you mean? $\endgroup$ – Tobi Jun 2 '19 at 18:13
  • $\begingroup$ You write "I read that...". Where did you read it? $\endgroup$ – Yuval Filmus Jun 2 '19 at 18:17
  • 2
    $\begingroup$ Then I suggest asking the lecturer. $\endgroup$ – Yuval Filmus Jun 2 '19 at 18:21
  • 1
    $\begingroup$ Yuval is absolutely right and the main argument indeed is that the difference he refers to is not large at all ---in particular for large values of the branching factor. I detailed the answer below. I loved by the way the reply "Then I suggest asking the lecturer" :) :) Please, Tobi, note that in Stack Exchange we encourage all users to provide information as much self-contained as possible as this question might be viewed by other people in the future. Providing "pointers" is more than a suggestion. Indeed, I find it hard to believe that you read such thing in a manual or textbook $\endgroup$ – Carlos Linares López Jun 4 '19 at 9:08
1
$\begingroup$

That's not entirely correct Tobi. Breadth-First search requires to store in memory only those nodes awaiting for expansion. Thus, it only requires to store in memory $b^d$ nodes in the worst case, i.e., if the solution is found at the rightmost child at depth $d$. That is the number of nodes required to be stored in memory because when the solution is found at depth $d$, that is precisely the number of nodes awaiting for expansion.

Indeed! You could actually remove any node after expanding it. So far, you are correct when you are guessing that you could actually remove all nodes expanded in the previous depths whose sum gets so far as $b^0+b^1+b^2+b^3+...+b^{d-1}$. Now, here comes the question:

  1. Why would you do it? Why would you actually remove those nodes? If you do not remove them, you could easily implement a duplicate detection mechanism: if a node $n$ is found at depth $d_1$ it is stored in memory. If it is found again at depth $d_2$, $d_2>d_1$ then its expansion can be skipped because a shortest path to it was already found ---given that the edge costs are all the same.
  2. Oh yeah! you might be thinking that this idea is not worthy as it requires to store in memory a rather large number of nodes: $b^0+b^1+b^2+...b^{d-1}$, isn't it? So that while duplicate detection seems desirable it might be too costly.

Note however that the sum of the terms of the geometric progression $b^0+b^1+b^2+...+b^{d-1}$ equals $\frac{b^d-1}{b-1}$ so that adding duplicate detection requires only a small fraction ($b-1$) of the nodes actually required to be stored in memory ($b^d$).

In other words, we say that the memory requirements of Breadth-First Search are dominated by the number of nodes awaiting to be expanded, $b^d$. Additional memory can be used as the total number of nodes in memory, $b^d+\frac{b^d-1}{b-1}=\frac{b^{d+1}-1}{b-1}$ (in case that duplicate detection is implemented), is much smaller than the number of nodes required to store the nodes in the subsequent level, $b^{d+1}$.

Test these numbers, even if $b=2$, note that with duplicate detection, the number of nodes in memory is $2^{d+1}-1$ which is smaller than $2^{d+1}$, the number of nodes required to store in memory for exploring an additional level without duplicate detection. The situation worsens significantly if you consider larger branching factors. For example, with $b=10$, the number of nodes required with duplicate detection is $\frac{10^{d+1}-1}{9}$, which is only 11% of the nodes required to be stored in memory for exploring the subsequent depth without duplicate detection, $10^{d+1}$ ...

Hope this helps,

Improve this answer
$\endgroup$
3
  • $\begingroup$ If it's a matter of completeness, then (a complete implementation of) DFS would suffer from the same problem. Completeness $\leftarrow$ duplicate detection. Without duplicate detection it's not complete. $\endgroup$ – Tobi Jun 4 '19 at 23:41
  • $\begingroup$ What I've taken from this answer is "yes, it's probably for the sake of having a complete implementation" but you haven't answered the other question $\endgroup$ – Tobi Jun 4 '19 at 23:43
  • $\begingroup$ No, it is not a matter of completeness (let me know what I could to improve my answer to make that clear). Without duplicate detection you will still find the optimal solution but you will then invest a larger effort. That is indeed what I meant when I said that duplicate detection is desirable, but not mandatory! In DFS, duplicate detection is much more complex $\endgroup$ – Carlos Linares López Jun 5 '19 at 11:54

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.