Answers.Body: <p>No misunderstanding. IDA* is indeed n^2 vs n for A* in certain situations.</p>
  <p>See
  <a href="https://pdfs.semanticscholar.org/388c/0a934934a9e60da1c22c050566dbcd995702.pdf" rel="nofollow noreferrer">https://pdfs.semanticscholar.org/388c/0a934934a9e60da1c22c050566dbcd995702.pdf</a>
  for a reference.</p>
  <p>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.</p>
  <p>IDA* will however, as noted, become exponential when all costs differ. Examples include continuous costs, or discrete values spanning a large range.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-02T05:16:42.843Z
Answers.Text: Note that there is a replacement for IDA*, [BTS](https://webdocs.cs.ualberta.ca/~nathanst/papers/sturtevant2020btsguide.pdf), which has much better worst-case performance: O(n log(C*)) where C* is the optimal solution cost.
Answers.UserDisplayName: Nathan S.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-20T16:57:56.300Z
Answers.LastActivityDate: 2020-06-20T16:57:56.300Z
Answers.UserDisplayName: Edward Garemo
Body: <p>I think I'm misunderstanding the description of IDA* and want to clarify.</p>
  <p>IDA* works as follows (quoting from Wiki):</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p>Suppose that we have the following tree:</p>
  <ul>
  <li>branching factor = 5</li>
  <li>all cost are different</li>
  </ul>
  <p>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...</p>
  <p>I must be doing something wrong here right? If not, the complexity is <span class="math-container">$n^2$</span>, where n is the number of nodes with cost smaller than the optimum, compared to n for normal A*.</p>
  <p>Someone pointing out my misunderstanding would be greatly appreciated.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-18T13:40:29.067Z
Comments.Text: 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](https://en.wikipedia.org/wiki/Iterative_deepening_A*#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).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-17T11:43:50.010Z
Comments.Text: @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.
Comments.UserDisplayName: xojfqa
Tags: <search><a-star><ida-star>
Title: Doesn't the number of explored nodes with IDA* increase linearly?
UserDisplayName: Edward Garemo
ThreadText: # Doesn't the number of explored nodes with IDA* increase linearly?
  
  (Asked by: username_0 on 2020-06-17)
  
  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.
  
  **Tags:** search, a-star, ida-star
  > **Comments:**
  > **username_1**: 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](https://en.wikipedia.org/wiki/Iterative_deepening_A*#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).  
  > **username_2**: @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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-06-20. Score: 0 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_3**: Note that there is a replacement for IDA*, [BTS](https://webdocs.cs.ualberta.ca/~nathanst/papers/sturtevant2020btsguide.pdf), which has much better worst-case performance: O(n log(C*)) where C* is the optimal solution cost.  
  
  ---
  
  