Applications with bad initial cost-bounds and many alternatives
in the decision trees are solved with heuristic search algorithms
like A* [11,13] and IDA* [7].
One such example is the
N N--puzzle [7,11,13].
Here, a given initial configuration of tiles in a squared tray of
size N
N must be
re-arranged with the fewest number of moves into a given goal configuration.
No effective upper cost-bounds are known for this problem,
and hence it cannot be solved with DFBB.
Even the relatively small 15-puzzle (N=4) has a
search space of
states.
While it would seem easy to obtain any solution, finding an optimal
(=shortest) solution is
-complete [16].
In general, it takes some hundred million node expansions to solve
a random problem instance of the 15-puzzle, using the Manhattan distance
(the sum of the minimum displacement of each tile from its goal position)
as a heuristic estimate function.
Iterative-deepening A* (IDA*) [7]
simulates a best-first search by a series of depth-first searches
with successively increased cost-bounds.
Its low space overhead of makes it feasible in applications where
A* [11] cannot be used due to memory limitations.
With a non-overestimating heuristic estimate function,
IDA* is guaranteed to find an optimal (shortest) solution [7].
In contrast to DFBB, IDA* halts after finding a first solution, because
optimality is guaranteed by the iterative approach with the minimal
cost-bound increments [7].