Abstract
While computing resources have continued to
grow, methods for building and using large heuristics have not seen significant advances in recent years. We have observed that directionoptimizing breadth-first search, developed for and
used broadly in the Graph 500 competition, can
also be applied for building heuristics. But, the algorithm cannot run efficiently using external memory – when the heuristics being built are larger than
RAM. This paper shows how to modify directionoptimizing breadth-first search to build externalmemory heuristics. We show that the new approach
is not effective in state spaces with low asymptotic branching factors, but in other domains we
are able to achieve up to a 3x reducing in runtime
when building an external-memory heuristic. The
approach is then used to build a 2.6TiB Rubik’s
Cube heuristic with 5.8 trillion entries, the largest
pattern database heuristic ever built