Delayed Duplicate Detection: Extended Abstract

Abstract

Best-first search is limited by the memory needed to store nodes in order to detect duplicates. Disks can greatly expand the amount of storage available, but randomly accessing a disk is impractical. Rather than checking newly-generated nodes as soon as they are generated, we append them to a disk file, then sort the file, and finally scan the sorted file in one pass to detect and remove duplicate nodes. This also speeds up such searches that fit entirely in memory, by improving cache performance. We implement this idea for breadth-first search, performing the first complete searches of the 2×7 sliding-tile puzzle, and the 18-disk, 4-peg Towers of Hanoi puzzle.