Minimizing Disk I/O in Two-Bit Breadth-First Search

Richard E. Korf

We present a breadth-first search algorithm, two-bit breadth-first search (TBBFS), which requires only two bits for each state in the problem space. TBBFS can be parallelized in several ways, and can store its data on magnetic disk. Using TBBFS, we perform complete breadth-first searches of the original pancake problem with 14 and 15 pancakes, and the burned pancake problem with 11 and 12 pancakes, determining the diameter of these problem spaces for the first time. We also perform the first complete breadth-first search of the subspace of Rubik's Cube determined by the edge cubies.

Subjects: 15.7 Search; 15. Problem Solving

Submitted: Apr 15, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.