The Relationship Between AND/OR Search and Variable Elimination
This work provides a unifying framework for understanding and comparing existing algorithms in graphical models, which is incremental but clarifies relationships between methods.
The paper compares search and inference in graphical models by introducing the AND/OR search framework, showing how it encompasses algorithms like Variable Elimination, Recursive Conditioning, and Value Elimination.
In this paper we compare search and inference in graphical models through the new framework of AND/OR search. Specifically, we compare Variable Elimination (VE) and memoryintensive AND/OR Search (AO) and place algorithms such as graph-based backjumping and no-good and good learning, as well as Recursive Conditioning [7] and Value Elimination [2] within the AND/OR search framework.