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 a number of nodes in memory that is exponential to the length of the optimal (shortest) path.
Could someone please explain?