1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – nbro Jun 18 at 13:40
0
$\begingroup$

No misunderstanding. IDA* is indeed n^2 vs n for A* in certain situations.

See https://pdfs.semanticscholar.org/388c/0a934934a9e60da1c22c050566dbcd995702.pdf for a reference.

IDA* only works in certain (not uncommon) situations. If there are many states with the same costs, and this number grows exponentially with the cost, then IDA* will be O(n). An example of such a problem is the 8 sliding piece puzzle.

IDA* will however, as noted, become exponential when all costs differ. Examples include continuous costs, or discrete values spanning a large range.

If you really wanted to apply IDA* to e.g. a map, a workable approach would likely be to round all values - or perform a log+floor operation.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Note that there is a replacement for IDA*, BTS, which has much better worst-case performance: O(n log(C*)) where C* is the optimal solution cost. $\endgroup$ – Nathan S. Jul 2 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.