Iterative Deepening A* (IDA*)[Korf, R. E., ``Depth-First Iterative-Deepening: An Optimal Admissible Tree Search'', Artificial Intelligence, vol. 27, no. 1 (Sept. 1985).] combines a depth-first, iterative-deepening style of search with the use of heuristic functions as in A*.

1. Initially, set threshold = h(start) .

2. Perform a depth-first search, failing at any node n for which g(n) + h(n) > threshold .

3. If no solution is found, increase threshold to the minimum value of g(n) + h(n) that was over threshold in the previous search, and retry.

Adv.:

• Low storage requirement: O(depth) .

• Makes use of heuristic information: fast.

• Optimal solution if h(n) is admissible.

Dis.:

• Redo search work that was done previously.

• If there are multiple paths to a node, IDA^* will re-search the successors of that node (A^* would not).

Contents    Page-10    Prev    Next    Page+10    Index