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.
