Menu
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".
924
The time complexity of A* depends on the heuristic. 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 branching factor (the average number of successors per state).
Exponential Time Complexity: O(2^n) Algorithms with this time complexity are usually used in situations where you don't know that much about the best solution, and you have to try every possible combination or permutation on the data. Exponential time complexity is usually seen in Brute-Force algorithms.
A* is an informed search algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.).
O(N) - reading a book. O(N log N) - sorting a deck of playing cards (using merge sort) O(N^2) - checking if you have everything on your shopping list in your trolley. O(infinity) - tossing a coin until it lands on heads.
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.
87
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.
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
