Answers.Body: <p>According to <a href="https://rads.stackoverflow.com/amzn/click/com/0134610997" rel="nofollow noreferrer" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach 4th edition</a> in IDA* the cutoff is the <span class="math-container">$f$</span>-cost(<span class="math-container">$g+h$</span>); at each iteration, the cutoff value is the smallest <span class="math-container">$f$</span>-cost of any node that exceeded the cutoff on the previous iteration.</p>
  <p>In other words, each iteration exhaustively searches an <span class="math-container">$f$</span>-contour, finds a node just beyond that contour, and uses that node's <span class="math-container">$f$</span>-cost as the next contour.</p>
  <p>And we must test if the node is a goal node when it was selected for expansion, otherwise, the algorithm is not optimal anymore (the proof is similar to that one in A*).</p>
  <p>I think the animation that the site provided is misleading because in the code which is written in the last of the same site we have that:</p>
  <pre><code>function Search(node, g, threshold)              //recursive function
  {
  
    f = g + heuristic(node);
    if(f &gt; threshold)             //greater f encountered
           return f;
    if(node == Goal)               //Goal node found
           return FOUND;
    integer min = MAX_INT;     //min = Minimum integer
    foreach(tempnode in nextnodes(node))
    {
  
       //recursive call with next node as current node for depth search
       integer temp=search(tempnode, g + cost(node, tempnode), threshold);  
       if(temp == FOUND)            //if goal found
         return FOUND;
       if(temp &lt; min)     //find the minimum of all 'f' greater than threshold encountered                                
         min = temp;
  
       }
       return min;  //return the minimum 'f' encountered greater than threshold
  }
  </code></pre>
  <p>And in the previous code, we test if the node is the goal node only when it was selected for expansion.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-20T14:25:46.620Z
Answers.Text: Thank you, I though that the animation was misleading, I needed a confirmation which you gave it to me
Answers.UserDisplayName: yaminoyuki
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-19T23:07:13.160Z
Answers.LastActivityDate: 2020-11-21T11:49:06.617Z
Answers.LastEditDate: 2020-11-21T11:49:06.617Z
Answers.UserDisplayName: Kais Hasan
Body: <p>I was reading about IDA* and I found this <a href="https://algorithmsinsight.wordpress.com/graph-theory-2/ida-star-algorithm-in-general/" rel="nofollow noreferrer">link</a> explaining IDA* and providing <a href="https://algorithmsinsight.files.wordpress.com/2016/03/ida-star.gif?w=1326" rel="nofollow noreferrer">an animation</a> for it.</p>
  <p>Here is a picture of the solution.</p>
  <p><a href="https://i.sstatic.net/paLIe.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/paLIe.png" alt="enter image description here" /></a></p>
  <p>I know what is the cutoff condition (it depends on F), and the search is like DFS if the value of (f) of the node is less or equal to the cutoff, and like IDF it is iterative</p>
  <p>My question is:</p>
  <p>In the animation, when the threshold is 7 and after expanding the parent of the goal (14), they stated that a solution has been found, so, if we found the goal after expanding a node which is &lt;= the cutoff value, can we consider it the solution without applying any condition-test on it? (it's F &lt;= threshold): for example, if there was another level where there is a goal and it can be found with value 13 (less than 14), like the following pic:</p>
  <p><a href="https://i.sstatic.net/vvLpV.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vvLpV.png" alt="enter image description here" /></a></p>
  <p>when the threshold is 7, 11 will not be expanded so we will never get (13)</p>
  <p>So, what is the correct solution?</p>
  
Tags: <search><ida-star><stopping-conditions>
Title: When does IDA* consider the goal has been found?
UserDisplayName: yaminoyuki
ThreadText: # When does IDA* consider the goal has been found?
  
  (Asked by: username_0 on 2020-11-17)
  
  I was reading about IDA\* and I found this [link](https://algorithmsinsight.wordpress.com/graph-theory-2/ida-star-algorithm-in-general/) explaining IDA\* and providing [an animation](https://algorithmsinsight.files.wordpress.com/2016/03/ida-star.gif?w=1326) for it.
  
  Here is a picture of the solution.
  
  [![enter image description here](https://i.sstatic.net/paLIe.png)](https://i.sstatic.net/paLIe.png)
  
  I know what is the cutoff condition (it depends on F), and the search is like DFS if the value of (f) of the node is less or equal to the cutoff, and like IDF it is iterative
  
  My question is:
  
  In the animation, when the threshold is 7 and after expanding the parent of the goal (14), they stated that a solution has been found, so, if we found the goal after expanding a node which is <= the cutoff value, can we consider it the solution without applying any condition-test on it? (it's F <= threshold): for example, if there was another level where there is a goal and it can be found with value 13 (less than 14), like the following pic:
  
  [![enter image description here](https://i.sstatic.net/vvLpV.png)](https://i.sstatic.net/vvLpV.png)
  
  when the threshold is 7, 11 will not be expanded so we will never get (13)
  
  So, what is the correct solution?
  
  **Tags:** search, ida-star, stopping-conditions
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-11-19. Score: 1 | Accepted answer
  
  According to Artificial Intelligence: A Modern Approach 4th edition in IDA* the cutoff is the $f$-cost($g+h$); at each iteration, the cutoff value is the smallest $f$-cost of any node that exceeded the cutoff on the previous iteration.
  In other words, each iteration exhaustively searches an $f$-contour, finds a node just beyond that contour, and uses that node's $f$-cost as the next contour.
  And we must test if the node is a goal node when it was selected for expansion, otherwise, the algorithm is not optimal anymore (the proof is similar to that one in A*).
  I think the animation that the site provided is misleading because in the code which is written in the last of the same site we have that:
  function Search(node, g, threshold)              //recursive function
  {
  
    f = g + heuristic(node);
    if(f > threshold)             //greater f encountered
           return f;
    if(node == Goal)               //Goal node found
           return FOUND;
    integer min = MAX_INT;     //min = Minimum integer
    foreach(tempnode in nextnodes(node))
    {
  
       //recursive call with next node as current node for depth search
       integer temp=search(tempnode, g + cost(node, tempnode), threshold);  
       if(temp == FOUND)            //if goal found
         return FOUND;
       if(temp < min)     //find the minimum of all 'f' greater than threshold encountered                                
         min = temp;
  
       }
       return min;  //return the minimum 'f' encountered greater than threshold
  }
  
  And in the previous code, we test if the node is the goal node only when it was selected for expansion.
  
  > **Comments:**
  > **username_0**: Thank you, I though that the animation was misleading, I needed a confirmation which you gave it to me  
  
  ---
  
  