Analyzing the Performance of Pattern Database Heuristics

Richard E. Korf

We introduce a model for predicting the performance of IDA* using pattern database heuristics, as a function of the branching factor of the problem, the solution depth, and the size of the pattern databases. While it is known that the larger the pattern database, the more efficient the search, we provide a quantitative analysis of this relationship. In particular, we show that for a single goal state, the number of nodes expanded by IDA* is a fraction of $(\log_bs+1)/s$ of the nodes expanded by a brute-force search, where $b$ is the branching factor, and $s$ is the size of the pattern database. We also show that by taking the maximum of at least two pattern databases, the number of node expansions decreases linearly with $s$ compared to a brute-force search. We compare our theoretical predictions with empirical performance data on Rubik's Cube. Our model is conservative, and overestimates the actual number of node expansions.

Subjects: 15.7 Search; Please choose a second document classification

Submitted: Apr 24, 2007


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.