I think I'm misunderstanding the description of IDA* and want to clarify.
IDA* works as follows (quoting from Wiki):
At each iteration, perform a depth-first search, cutting off a branch when its total cost exceeds a given threshold. This threshold starts at the estimate of the cost at the initial state, and increases for each iteration of the algorithm. At each iteration, the threshold used for the next iteration is the minimum cost of all values that exceeded the current threshold.
Suppose that we have the following tree:
- branching factor = 5
- all cost are different
Say we have expanded 1000 nodes. We pick the lowest cost of the nodes that we 'touched' but didn't expand. Since all costs are unique, there is now only one more node which satisfies this new cost bound, and so we expand 1001 nodes, and 'touch' 5 new ones. We now pick the smallest of these weights, and starting from the root expand 1002 nodes, and so on and so forth, 1003, 1004...
I must be doing something wrong here right? If not, the complexity is $n^2$, where n is the number of nodes with cost smaller than the optimum, compared to n for normal A*.
Someone pointing out my misunderstanding would be greatly appreciated.