3
$\begingroup$

I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$.

While I am reading, at some points, I found GBFS similar to DFS. It expands the whole branches and goes after one according to the heuristic function. It doesn't expand the rest like BFS. Perceiving this as similar to what depth-first search does, I understand that the worst time complexity is $\mathcal{O}(b^m)$. But I don't understand the space complexity.

Shouldn't it be the same as DFS, $\mathcal{O}(bm)$, since it only will be expanding $b*m$ nodes during the search in one path?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

After spending some time on the problem, I concluded that it is due to the fact that we need to store the heuristic function evaluations for all nodes during the traversal. So, one might claim that it is the space complexity of the whole nodes which is simply $\mathcal{O}(b^m)$. I hope this is correct.

Also the one with having the space complexity of $\mathcal{O}(bm)$ is called recursive best-first search which is the one that is most similar to DFS implementation I descried in the question.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Have you any reference for this? $\endgroup$
    – keramat
    Commented Apr 24, 2022 at 14:41
1
$\begingroup$

I was struggling with the same question. This is what I came up with after thinking it through.

With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the parent of the parent when your parent has no more non-expanded children (and so on going up the tree)). So the space complexity is limited by your ancestors and the children of these ancestors. Which translates in m*b where m is the max path length (so max number of ancestors) and b is the branching factor (number of children per ancestor).

With greedy search when you backtrack you can jump to any evaluated but unexpanded node, you passed going down on paths earlier. So the algorithm, when backtracking, can make pretty random jumps throughout the tree leaving lots of sibling nodes unexpanded. You will have to remember the value of the evaluation function for all these unexpanded nodes though because possibly they are next up when backtracking occurs. So in a theoretical very worst-case scenario that could mean that almost the whole tree needs to be remembered. Hence O(b^m).

I know there are still gaps in the reasoning but intuitively this makes me understand it best.

Improve this answer
$\endgroup$

You must log in to answer this question.

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