Mumbai University > IT > Sem 7 > Intelligent System

Marks: 5M

Iterative Deepening A* (IDA) eliminates the memory constraints of A by keeping optimally of the solution.

In IDA* each iteration is a depth-first search with a threshold assigned to it. It keeps track of the cost, f(n)=g(n)+h(n), of each node generated. As soon as the cost of newly generated node exceeds a threshold for that iteration, the node will not be explored further and the search backtracks.

The threshold is initialized to the heuristic estimate of the initial state. It is increased in each successive iteration to the total cost of the lowest cost node that was pruned during the previous iteration. The algorithm terminates when a goal state is reached whose total cost does not exceed the current threshold.

Performance Evaluation:

Optimality: IDA* finds optimal solution, if the heuristic function is admissible.

Completeness: IDA*is complete. It always finds solution. It always finds solution if it exists within the threshold limit.

Time complexity: IDA* expands the same number of nodes, as A*. So, it has exponential time complexity.

Space Complexity: IDA* memory requirement is liner with respect to the maximum search depth.