Large-Scale Parallel Breadth-First Search

Recently, best-first search algorithms have been introduced that store their nodes on disk, to avoid their inherent memory limitation. We introduce several improvements to the best of these, including parallel processing, to reduce their storage and time requirements. We also present a linear-time algorithm for bijectively mapping permutations to integers in lexicographic order. We use breadth-first searches of sliding-tile puzzles as testbeds. On the 3x5 Fourteen Puzzle, we reduce both the storage and time needed by a factor of 3. 5 on two processors. We also performed the first complete breadth-first search of the 4x4 Fifteen Puzzle, with over 1013 states.

Authors

• Richard E. Korf

Keywords

No keywords are indexed for this paper.