Why is the complexity of A* exponential in memory?
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
A* is just a guided version of breadth-first search, which is exponential in memory complexity with respect to the length of the solution.
When using a constant heuristic, A* will become a normal breadth-first search; uniform cost search to be exact.
When using the optimal heuristic, A* will be O(n) in both space and time complexity if we disregard the complexity of the heuristic calculation itself. Again n is the length of the solution path.