Next: Example Previous: Optimality of A*

IDA*

Note: this material is optional. It is not covered in lecture.

What is it? Series of Depth-First Searches - designed to protect against high memory use in A*

Like Iterative Deepening Search, except use A* cost threshold instead of depth threshold

Ensures optimal solution

queueing-fn is enqueue-at-front if f(child) $\leq$ threshold

Threshold is h(root) for first pass

Next threshold is f(min_child),
where min_child is cutoff child with minimum f value

This conservative increase ensures cannot look past optimal cost solution