Access Restriction

Author Korf, Richard E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword External memory ♦ Rubik's Cube ♦ Towers of Hanoi ♦ Magnetic disk storage ♦ Permutation encodings ♦ Sliding-tile puzzles
Abstract Many search algorithms are limited by the amount of memory available. Magnetic disk storage is over two orders of magnitude cheaper than semiconductor memory, and individual disks can hold up to a terabyte. We augment memory with magnetic disks to perform brute-force and heuristic searches that are orders of magnitude larger than any previous such searches. The main difficulty is detecting duplicate nodes, which is normally done with a hash table. Due to long disk latencies, however, randomly accessed hash tables are infeasible on disk, and are replaced by a mechanism we call delayed duplicate detection. In contrast to previous work, we perform delayed duplicate detection without sorting, which runs in time linear in the number of nodes in practice. Using this technique, we performed the first complete breadth-first searches of the 2 × 7, 3 × 5, 4 × 4, and 2 Ø× 8 sliding-tile Puzzles, verifying the radius of the 4 × 4 puzzle and determining the radius of the others. We also performed the first complete breadth-first searches of the four-peg Towers of Hanoi problem with up to 22 discs, discovering a surprising anomaly regarding the radii of these problems. In addition, we performed the first heuristic searches of the four-peg Towers of Hanoi problem with up to 31 discs, verifying a conjectured optimal solution length to these problems. We also performed partial breadth-first searches of Rubik's Cube to depth ten in the face-turn metric, and depth eleven in the quarter-turn metric, confirming previous results.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-12-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 55
Issue Number 6
Page Count 40
Starting Page 1
Ending Page 40

Open content in new tab

   Open content in new tab
Source: ACM Digital Library