2
$\begingroup$

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.

enter image description here

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

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

So, what is the correct solution?

$\endgroup$
0
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.