Answers.Body: <p><a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="noreferrer">A*</a> is a <a href="https://en.wikipedia.org/wiki/Best-first_search" rel="noreferrer">best-first search algorithm</a>, which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by <span class="math-container">$g(n)$</span>, and an <a href="https://en.wikipedia.org/wiki/Admissible_heuristic" rel="noreferrer">admissible heuristic function</a>, denoted by <span class="math-container">$h(n)$</span>, which estimates the distance to the goal node, for each node <span class="math-container">$n$</span>. There are other best-first search algorithms, which differ only in the definition of their "evaluation function", denoted by <span class="math-container">$f(n)$</span>. For example, the evaluation function of A* is <span class="math-container">$f(n) = g(n) + h(n)$</span>, where <span class="math-container">$h$</span> is admissible.</p>
  
  <p>A* is <strong>optimal</strong>, that is, it finds the optimal path between the starting and goal nodes or states. The optimality of A* is due to the use of an admissible heuristic function, which is a heuristic function which always underestimates the distance to the goal. A* is also <strong>complete</strong>, that is, it eventually finds this optimal path. However, the problem with A*, in many real-world situations, is that it has an <strong>exponential space complexity</strong>; more specifically, its space complexity is <span class="math-container">$\mathcal{O}(b^m)$</span>, where <span class="math-container">$b$</span> is the (maximum) branching factor and <span class="math-container">$m$</span> is the maximum depth of the search tree. It also has a time complexity of <span class="math-container">$\mathcal{O}(b^m)$</span>, but, in practice, it tends to find the solutions quite "fast" (for relatively small search spaces).</p>
  
  <p><a href="https://en.wikipedia.org/wiki/Iterative_deepening_A*" rel="noreferrer">IDA*</a> combines A* and <a href="https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search" rel="noreferrer">IDDFS (or IDS)</a>. It does it "well", so it gets the advantages of both algorithms. It can be thought of as the IDDFS which uses, instead of the depth, the evaluation function <span class="math-container">$f(n) = g(n) + h(n)$</span> as the "cost threshold" or "cutoff". In the IDA* algorithm, a child <span class="math-container">$c$</span> of a node <span class="math-container">$n$</span> is added to the <a href="https://ai.stackexchange.com/q/5949/2444">frontier (or fringe or border)</a> if <span class="math-container">$f(c) &lt; T$</span>. This threshold <span class="math-container">$T$</span> is, at the beginning of the algorithm, the estimate of the distance to the goal from the starting node <span class="math-container">$s$</span>, that is, <span class="math-container">$T = h(s)$</span>. <span class="math-container">$T$</span> increases at each iteration of the algorithm (See the <a href="https://en.wikipedia.org/wiki/Iterative_deepening_A*#Pseudocode" rel="noreferrer">pseudocode of the IDA* algorithm</a> for the details).</p>
  
  <p>IDA* is also <strong>complete</strong> and <strong>optimal</strong>, but, as opposed to A*, it has a <strong>polynomial space complexity</strong>, more specifically, <span class="math-container">$\mathcal{O}(bd)$</span>, where <span class="math-container">$b$</span> is the (maximum) branching factor and <span class="math-container">$d$</span> is the maximum depth fo the tree. IDA* still has an exponential time complexity of A*.</p>
  
  <p>To conclude, IDA* has a better memory usage than A*. As in A* and unlike IDDFS, it concentrates on exploring the most promising nodes, and thus does not go to the same depth everywhere in the search tree (whereas ordinary IDDFS does). A* can be thought of as a dynamic programming algorithm. IDA* often ends up exploring the same nodes many times (as IDDFS), but, asymptotically, both A* and IDA* have the same exponential time complexity, that is, <span class="math-container">$\mathcal{O}(b^m)$</span>.</p>
  
  <p>So, which one is the best one? A* becomes impractical when the search space is huge, because of the memory constraints. So, in those cases, IDA* is definitely more appropriate. In general, IDA* is one of the very best optimal state space
  search techniques around. However, A* is conceptually simpler than IDA*. As a consequence, in practice, A* may be easier to implement than IDA*, but, in real-world scenarios, this is not really a problem, as they are both relatively easy to implement (anyway).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-10T14:44:12.973Z
Answers.LastActivityDate: 2018-11-10T15:08:16.640Z
Answers.LastEditDate: 2018-11-10T15:08:16.640Z
Answers.UserDisplayName: nbro
Body: <p>The iterative deepening A* search is an algorithm that can find the shortest path between a designated start node and any member of a set of goals. </p>
  
  <p>The A* algorithm evaluates nodes by combining the cost to reach the node and the cost to get from the node to the goal. How is iterative deepening A* better than the A* algorithm?</p>
  
Tags: <search><comparison><a-star><ida-star>
Title: How is iterative deepening A* better than A*?
UserDisplayName: Huma Qaseem
ThreadText: # How is iterative deepening A* better than A*?
  
  (Asked by: username_0 on 2018-11-07)
  
  The iterative deepening A\* search is an algorithm that can find the shortest path between a designated start node and any member of a set of goals.
  
  The A\* algorithm evaluates nodes by combining the cost to reach the node and the cost to get from the node to the goal. How is iterative deepening A\* better than the A\* algorithm?
  
  **Tags:** search, comparison, a-star, ida-star
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-11-10. Score: 12 | Accepted answer
  
  [A\*](https://en.wikipedia.org/wiki/A*_search_algorithm) is a [best-first search algorithm](https://en.wikipedia.org/wiki/Best-first_search), which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by $g(n)$, and an [admissible heuristic function](https://en.wikipedia.org/wiki/Admissible_heuristic), denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$. There are other best-first search algorithms, which differ only in the definition of their "evaluation function", denoted by $f(n)$. For example, the evaluation function of A\* is $f(n) = g(n) + h(n)$, where $h$ is admissible.
  
  A\* is **optimal**, that is, it finds the optimal path between the starting and goal nodes or states. The optimality of A\* is due to the use of an admissible heuristic function, which is a heuristic function which always underestimates the distance to the goal. A\* is also **complete**, that is, it eventually finds this optimal path. However, the problem with A\*, in many real-world situations, is that it has an **exponential space complexity**; more specifically, its space complexity is $\mathcal{O}(b^m)$, where $b$ is the (maximum) branching factor and $m$ is the maximum depth of the search tree. It also has a time complexity of $\mathcal{O}(b^m)$, but, in practice, it tends to find the solutions quite "fast" (for relatively small search spaces).
  
  [IDA\*](https://en.wikipedia.org/wiki/Iterative_deepening_A*) combines A\* and [IDDFS (or IDS)](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search). It does it "well", so it gets the advantages of both algorithms. It can be thought of as the IDDFS which uses, instead of the depth, the evaluation function $f(n) = g(n) + h(n)$ as the "cost threshold" or "cutoff". In the IDA\* algorithm, a child $c$ of a node $n$ is added to the [frontier (or fringe or border)](https://ai.stackexchange.com/q/5949/2444) if $f(c) < T$. This threshold $T$ is, at the beginning of the algorithm, the estimate of the distance to the goal from the starting node $s$, that is, $T = h(s)$. $T$ increases at each iteration of the algorithm (See the [pseudocode of the IDA\* algorithm](https://en.wikipedia.org/wiki/Iterative_deepening_A*#Pseudocode) for the details).
  
  IDA\* is also **complete** and **optimal**, but, as opposed to A\*, it has a **polynomial space complexity**, more specifically, $\mathcal{O}(bd)$, where $b$ is the (maximum) branching factor and $d$ is the maximum depth fo the tree. IDA\* still has an exponential time complexity of A\*.
  
  To conclude, IDA\* has a better memory usage than A\*. As in A\* and unlike IDDFS, it concentrates on exploring the most promising nodes, and thus does not go to the same depth everywhere in the search tree (whereas ordinary IDDFS does). A\* can be thought of as a dynamic programming algorithm. IDA\* often ends up exploring the same nodes many times (as IDDFS), but, asymptotically, both A\* and IDA\* have the same exponential time complexity, that is, $\mathcal{O}(b^m)$.
  
  So, which one is the best one? A\* becomes impractical when the search space is huge, because of the memory constraints. So, in those cases, IDA\* is definitely more appropriate. In general, IDA\* is one of the very best optimal state space
  search techniques around. However, A\* is conceptually simpler than IDA\*. As a consequence, in practice, A\* may be easier to implement than IDA\*, but, in real-world scenarios, this is not really a problem, as they are both relatively easy to implement (anyway).
  
  
  ---
  
  