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

Could someone please explain?

Answer 1

The time complexity of A* depends on the heuristic function. In the worst case of an unbounded search space, the number of nodes expanded is exponential in the depth of the solution (the shortest path) d: O(bd), where b is the only branching factor (the average number of successors per state). This assumes that a goal state exists, and is reachable from the start state; if it is not, and the state space is infinite, the algorithm will not terminate.

A* is just a guided version of the 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.

If you want to make your career in Artificial Intelligence then go through this video: