# Doesn't the number of explored nodes with IDA* increase linearly?

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.

• I think you only restart the search from the root note if you have reached the bound and not found the goal node. I think this can be seen from the pseudocode. I am not sure if this answers your question (and if this is completely correct, because it's been a while since I had to do something with IDA*), but it seems like you are assuming that you restart the search from the root everytime you expand a node. Anyway, I will maybe give you a more complete answer later (if I don't forget about this).
– nbro
Jun 18, 2020 at 13:40