Mini-Bucket Heuristics for Improved Search
This work addresses search efficiency in constraint satisfaction and optimization problems, such as coding and medical diagnosis, but is incremental as it builds on prior work in the series.
The paper tackles the problem of generating search heuristics mechanically using mini-bucket elimination, extending it to Best-First search and evaluating it on coding and medical diagnosis problems. The results show that Best-First search outperforms Branch-and-Bound when provided with good heuristics and sufficient memory, enabling a controlled tradeoff between preprocessing and search.
The paper is a second in a series of two papers evaluating the power of a new scheme that generates search heuristics mechanically. The heuristics are extracted from an approximation scheme called mini-bucket elimination that was recently introduced. The first paper introduced the idea and evaluated it within Branch-and-Bound search. In the current paper the idea is further extended and evaluated within Best-First search. The resulting algorithms are compared on coding and medical diagnosis problems, using varying strength of the mini-bucket heuristics. Our results demonstrate an effective search scheme that permits controlled tradeoff between preprocessing (for heuristic generation) and search. Best-first search is shown to outperform Branch-and-Bound, when supplied with good heuristics, and sufficient memory space.