Memory intensive AND/OR search for combinatorial optimization in graphical models |
| |
Authors: | Radu Marinescu Rina Dechter |
| |
Affiliation: | 1. Cork Constraint Computation Centre, University College Cork, Ireland;2. Donald Bren School of Information and Computer Science, University of California, Irvine, CA 92697, USA |
| |
Abstract: | In this paper we explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation (MPE) in belief networks and solving Weighted CSPs (WCSP). In an extensive empirical evaluation we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|