1
$\begingroup$

In "Artificial Intelligence: A Modern Approach", the authors say that the space complexity of depth-first search is proportional to O(bm), considering b as the branching factor and m the maximum depth of the graph. But it is not obvious why, for me.

The algorithm for searching graphs involves storing the explored nodes in the explored set, and the nodes open, but not explored yet, are stored in the border set.

Let us consider the following graph, with the start node in green and the end node (the goal) in red. enter image description here

The solution is given by the red path.

But, in my perspective, in this scenario, in the worst case, the algorithm would try every path from the root to each leaf, and store all the nodes in the explored set.

Thus, if we consider this, the space complexity is, at least, proportional to $O(b^m)$.

Is there something wrong with this reasoning?

I'm including another image to represent better the searching process on a graph. enter image description here

Best regards.

$\endgroup$

1 Answer 1

0
$\begingroup$

If you have looked through an entire branch, you only need to mark off the top node for that branch.

$\endgroup$
6
  • 3
    $\begingroup$ Thanks for your contribution! Would you be able to elaborate your answer a bit more? Without further explanation, I'm afraid that your answer wouldn't really help to clarify things for anyone who would ask the question in the first place. $\endgroup$
    – Dennis Soemers
    Jan 12 at 10:20
  • $\begingroup$ But notice that the algorithm proposed in the book stores all the explored nodes, in order to avoid visiting them again. And notice that although my example is in a tree, we are interested in searching on graphs. $\endgroup$
    – Zaratruta
    Jan 12 at 16:49
  • $\begingroup$ To visit a node again, you have to visit the node's parent. If you're at the node's parent, you do need to mark off the node. But if not, you only need to mark off the parent. You can continue upwards: if you're not at the grandparent, you only have to mark off the grandparent. You end up only needing to mark off nodes adjacent to your path, which is $O(bm)$ in space. This works for any graph. $\endgroup$ Jan 13 at 12:07
  • $\begingroup$ @programjames This is not true if we are searching in a graph. In a graph, a given node can be a successor of several different nodes. I have included a novel image to represent the searching process on a graph. But, it is important to notice that the algorithm presented in the book that I have cited says explicitly that we need to store all the explored nodes. $\endgroup$
    – Zaratruta
    Jan 15 at 2:58
  • $\begingroup$ But you still only need to mark off a boundary, not every node in the area. $\endgroup$ Jan 15 at 13:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .