Abstract
We present a simple combination of A* and IDA*,
which we call A*+IDA*. It runs A* until memory is almost exhausted, then runs IDA* below
each frontier node without duplicate checking. It is
widely believed that this algorithm is called MREC,
but MREC is just IDA* with a transposition table.
A*+IDA* is the first algorithm to run significantly
faster than IDA* on the 24-Puzzle, by a factor of
almost 5. A complex algorithm called dual search
was reported to significantly outperform IDA* on
the 24-Puzzle, but the original version does not.
We made improvements to dual search and our version combined with A*+IDA* outperforms IDA*
by a factor of 6.7 on the 24-Puzzle. Our disk-based
A*+IDA* shows further improvement on several
hard 24-Puzzle instances. We also found optimal
solutions to a subset of random 27 and 29-Puzzle
problems. A*+IDA* does not outperform IDA* on
Rubik’s Cube, for reasons we explain