Michael's Wiki

OR Tree

The tree has depth equal to the number of variables. Each level enumerates all values for a variable. A solution in this tree is a path from the root to a leaf.


For a variable ordering $d$, define a tree based on VEC over each variable in order $d$. The tree alternates between OR levels and AND levels. Levels of the tree in which a variable is conditioned over its values are called AND levels. OR levels are those which contain free variables.

The AND-OR tree is smaller than a basic OR tree.

One way to learn an ordering $d$ is by depth-first search over the original graph.

And-OR Graphs

When a pseudo-tree has back-edges which don't go very far, the sub-tree can be collapsed to form a more concise graph. (slide 37) This takes advantage of independence assumptions present in the graph. For search purposes, it is important to treat this as a graph and avoid repetetively searching the same node. The tree width determines how many leaf nodes will have to be cached during a search.