A general scheme for automatic generation of search heuristics from specification dependencies

The paper presents and evaluates the power of a new scheme that generates s earch heuristics mechanically for problems expressed using a set of functio ns or relations over a finite set of variables. The heuristics are extracte d from a parameterized approximation scheme called Mini-Bucket elimination that allows controlled trade-off between computation and accuracy. The heur istics are used to guide Branch-and-Bound and Best-First search. Their perf ormance is compared on two optimization tasks: the Max-CSP task defined on deterministic databases and the Most Probable Explanation task defined on p robabilistic databases. Benchmarks were random data sets as well as applica tions to coding and medical diagnosis problems. Our results demonstrate tha t the heuristics generated are effective for both search schemes, permittin g controlled trade-off between preprocessing (for heuristic generation) and search. (C) 2001 Elsevier Science B.V. All rights reserved.