A Novel Technique for Compressing Pattern Databases in the Pancake Sorting Problems

Abstract

In this paper we present a lossless technique to compress pattern databases (PDBs) in the Pancake Sorting problems. This compression technique together with the choice of zero-cost operators in the construction of additive PDBs reduces the memory requirement for PDBs in these problems to a great extent, thus making otherwise intractable problems able to be efficiently handled. Also, using this method, we can construct some problem-size independent PDBs. This precludes the necessity of constructing new PDBs for new problems with different numbers of pancakes. In addition to our compression technique, by maximizing over the heuristic value of additive PDBs and the modified version of the gap heuristic, we have obtained powerful heuristics for the burnt pancake problem.