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

DFBB does not explore paths that are guaranteed to lead to solutions worse than current best solution.

On termination, the current best solution is a globally optimal solution.

Iterative Deepening Search

• Often, the solution may exist close to the root, but on an alternate branch.

• Simple backtracking might explore a large space before finding this.

• Iterative deepening sets a depth bound on the space it searches (using DFS).

• If no solution is found, the bound is increased and the process repeated.

Iterative Deepening A* (IDA*)

• Uses a bound on the cost of the path as opposed to the depth.

• IDA* defines a function for node x in the search space as l(x) = g(x) + h(x). Here, g(x) is the cost of getting to the node and h(x) is a heuristic estimate of the cost of getting from the node to the solution.

•