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.

Improve this question
$\endgroup$
2
  • $\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, 2020 at 13:40
  • $\begingroup$ @nbro I believe they were saying that the search starts from the root every time you expand a node because each node has a different cost. If you choose each new bound to be the minimum cost of the nodes that were cut off, and no node has the same cost, each restart only results in one extra node being expanded: in effect, we restart from the root every time we expand a node. $\endgroup$
    – xojfqa
    Oct 17, 2022 at 11:43

1 Answer 1

Reset to default
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$
1
  • $\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, 2020 at 5:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .