Abstract
This paper presents a parallel algorithm for searching massive state spaces by exploiting the underlying algebraic structure of problems like the knapsack problem and Rubik's Cube. By parallelizing the classic Schroeppel and Shamir algorithm, the authors achieve a time complexity of $O(N^{1/4}/P)$ and a space complexity of $O(N^{1/4})$, effectively allowing researchers to double the searchable depth of complex problems on massively parallel machines.
Introduction
State-space search is a cornerstone of Artificial Intelligence, used for everything from planning to game playing. However, most methods (like IDA*) rely heavily on heuristics to prune the search tree. When good heuristics are unavailable or the state space is astronomical, these methods fail.
While parallel computing offers a way out, simply throwing more processors at the problem often leads to a "space bottleneck." If an algorithm requires $O(N^{1/2})$ space to achieve a significant speedup, it quickly outstrips the memory available on even the largest supercomputers. The authors seek to bridge this gap by creating an algorithm that is both time-efficient and space-efficient, specifically targeting "monotonic and decomposable" problems.
Methodology
The authors build upon the Schroeppel and Shamir algorithm, a sequential technique that solves the knapsack problem by partitioning the input into four lists ($A, B, C, D$) and looking for intersections of sums (e.g., $A+B$ vs. $C+D$).
Parallel Generation and Data Structures
Instead of generating sums one by one using a priority queue (which is inherently sequential), the authors propose a method to generate $2^{n/4}$ elements in parallel. They use an array called TEMP to track candidate elements and iteratively "filter" them to find the smallest set of candidates.
In the knapsack problem, addition is monotonic ($b < b' \implies a+b < a+b'$). However, in permutation groups (like Rubik's Cube), this doesn't hold. The authors introduce a Trie-based data structure where interior nodes are reordered based on the specific permutation being applied. This allows them to maintain a lexicographical order even when the operators are complex.
Computational Model
The algorithm is described using the CREW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) model, which simplifies the description by hiding communication costs, though the authors acknowledge the practical challenges of this assumption.
Benchmarks and Key Insights
As a theoretical algorithmic paper, it evaluates the approach against canonical computational benchmarks including the Knapsack Problem and Permutation Groups (specifically the Shortest Word Problem, which generalizes puzzles like Rubik’s Cube).
- The Power of Four: By splitting a problem into four parts rather than two (the standard "meet-in-the-middle" approach), the space requirement drops from $O(N^{1/2})$ to $O(N^{1/4})$. This is the difference between a problem being impossible to fit in RAM and being trivial.
- Algebraic Leverage: The paper argues that we shouldn't just rely on "blind" search or heuristics. If a problem has an algebraic structure (like being a group or a groupoid), that structure can be used to mathematically decompose the search.
- Parallelizing the Priority Queue: The "aha moment" in the parallel implementation is replacing the sequential priority queue with a parallel filtering process in the
TEMParray, allowing multiple processors to contribute to the generation of the next batch of states simultaneously.
Results and Future Work
The algorithm achieves a time complexity of $O(N^{1/4}/P)$ using $O(N^{1/4})$ space, where $N$ is the size of the state space and $P$ is the number of processors. The authors claim this approach can effectively double the depth of the search that current technology can perform for this class of problems.
While theoretically sound, the authors admit the CREW PRAM model is unrealistic for actual hardware because it ignores the high cost of communication. Future directions include applying compression techniques, such as Binary Decision Diagrams (BDDs), to further reduce the memory footprint and refining implementation-dependent parameters to improve performance on actual hardware like the CM-5.
Summary updated