Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

At each failed step, the cost bound is incremented to that of the node that exceeded the prior cost bound by the least amount.

If the heuristic h is admissible, the solution found by IDA* is optimal.

DFS Storage Requirements and Data Structures

• At each step of DFS, untried alternatives must be stored for backtracking.

• If m is the amount of storage required to store a state, and d is the maximum depth, then the total space requirement of the DFS algorithm is O(md).

• The state-space tree searched by parallel DFS can be efficiently represented as a stack.

• Memory requirement of the stack is linear in depth of tree.

DFS Storage Requirements and Data Structures

• Representing a DFS tree: (a) the DFS tree; Successor nodes shown with dashed lines have already been explored; (b) the stack storing untried alternatives only; and (c) the stack storing untried alternatives along with their parent. The shaded blocks represent the parent state and the block to the right represents successor states that have not been explored.