Compressing Pattern Databases with Learning

摘要: A pattern database (PDB) is a heuristic function implemented as lookup table. It stores the lengths of optimal solutions for instances subproblems. Most previous PDBs had distinct entry in table each subproblem instance. In this paper we apply learning techniques to compress by using neural networks and decision trees thereby reducing amount memory needed. Experiments on sliding tile puzzles TopSpin puzzle show that our compressed significantly outperforms both uncompressed well compressing methods. Our full system reduced size needed factor up 63 at cost no more than 2 search effort.