# When does IDA* consider the goal has been found?

I was reading about IDA* and I found this link explaining IDA* and providing an animation for it.

Here is a picture of the solution.

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:

when the threshold is 7, 11 will not be expanded so we will never get (13)

So, what is the correct solution?

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.

• Thank you, I though that the animation was misleading, I needed a confirmation which you gave it to me – yaminoyuki Nov 20 '20 at 14:25