Why is the complexity of A* exponential in memory?

Question

Wikipedia says on A* complexity the following (link here):

More problematic than its time complexity is A*’s memory usage. In the worst case, it must also remember an exponential number of nodes.

I fail to see this is correct because:

Say we explore node A, with successors B, C, and D. Then we add B, C, and D to the list of open nodes, each accompanied by a reference to A, and we move A from the open nodes to the closed nodes.

If at some time we find another path to B (say, via Q), that is better than the path through A, then all that is needed is to change B's reference to A to point to Q and update its actual cost, g (and logically f).

Therefore, if we store in a node its name, its referring node name, and its g, h, and f scores, then the maximum amount of nodes stored is the actual amount of nodes in the graph, isn't it? I really cannot see why at any time the algorithm would need to store an amount of nodes in memory that is exponential to the length of the optimal (shortest) path.

Could someone please explain?

---

edit As I understand now reading your answers, I was reasoning from the wrong viewpoint of the problem. I took for granted a given graph, whereas the exponential complexity refers to a an conceptual graph that is defined solely by a "branching factor".

Answer 1

I think the exponential-ness comes into play when you backtrack to node B to expand it, but then backtrack to node C to expand it, and then backtrack to node D. Now we have to keep track of all the children of nodes A, B, C, and D.

The backtracking is based on the cost of the edges to move to the next node, so this is a real possibility, but is the worse case.

If each node has exactly 2 children off of it, and each node has the same cost, then the equation is 2^n, where n is the depth of the search so far.

For example, you start off with node 0. 0 has 2 children 00 and 01. 00 has 2 children 000 and 001. At the worse case with a depth of 4 the equation is 2^4, where 2 is the number of children each node has and 4 is the depth of the search.

Answer 2

A* is just a guided version of breadth-first search, which is exponential in memory complexity. Especially using a constant heuristic for A* will result in normal breadth-first search. Having an optimal heuristic, A* will be O(n) in both space and time complexity if we disregard the complexity of the heuristic calculation.