Iterative Deepening A*(IDA*)

Iterative Deepening A* 

It turns out A* is not optimal with respect to the number of nodes to be expanded. Better algorithms exist which take this fact into account. One such algorithm is iterative deepening A* (IDA*) algorithm.

The search technique. Depth_first Iterative Deepening can be used along with heuristic estimating functions, Here we make use of a cost cut off instead of depth cut off  to obtain an algorithm which increments the cost cut off in a step by step style. This algorithm, IDA*, uses an admissible heuristic as used in A*, and hence the name Iterative deepening A*.

IDA* deploys the depth first iterative deepening search to keep the Space requirement to a minimum and also uses a cost cut off strategy. It works iteratively, at each iteration it performs a depth first search, cutting of node n as soon as its estimated cost of the function f(n) exceeds a specified threshold.

The threshold is initialized to the estimate of the cost of the initial state. After each iteration, the threshold used for the next iteration is set to the minimum estimated cost threshold. The pseudo algorithm is given as under. 

Algorithm of IDA*

{ 

begin 

solution : = 0;

C : f'(root)

repeat

CDFS < root, c>;  ("Cost defined depth first search")

if solution : = (FAILURE) then

C : min f'(m)    ("a backtrack was applied at node m in the last application of CDFS")

until solution C > 0: (success)

end;

}

It may be noted that the first solution found by this algorithm is an optimal cost solution provided the estimate is admissible.