AND／OR Search Trees (AOT)

AND/OR Search Tree - Definition

given:

• graphical model 𝒢 = ⟨𝐗, 𝐃, 𝐒, 𝐅, 𝐂⟩
• primal graph 𝐺 of 𝒢
• guiding pseudo tree 𝑇 of 𝐺

the associated AND/OR Search Tree 𝑆_𝑇(𝒢):

• has alternating levels of AND and OR nodes:
• its structure is based on the underlying pseudo tree 𝑇:
  • its root is an OR node labeled by the root of 𝑇
  • its parent-child relationship between nodes in the search space are defined as follows:
    • an OR node 𝑂 has a child AND node 𝐴, iff it is consistent with the assignment from root node to node 𝐴 (consistency is defined relative to the constraints when we have a constraint problem)
    • an AND node 𝐴 has a child OR node 𝑂, iff 𝑂 is a child of 𝐴 in the guiding pseudo tree 𝑇

AND/OR Search Tree - Examples

Click here to expand...

• (a) is a primal graph
• (b) is a pseudo tree
• (c) is a pseudo tree
• (d) is a chain pseudo tree

assume each variable {1, 2, 3, 4, 5, 6, 7} has domain {a, b, c} the graphs below shows the resulting AND/OR Search Trees based on its guiding pseudo tree

• (top) is guided by pseudo tree (b)
• (bot) is guided by pseudo tree (c)

the size of AND/OR Search Tree is determined by the height of the guiding pseudo tree:

• smaller pseudo tree height → smaller AND/OR tree size
• larger pseudo tree height → larger AND/OR tree size

an AND/OR search tree becomes an OR search tree when its pseudo tree is a chain

AND/OR Search Tree - Complexity

Click here to expand...

given:

• graphical model 𝒢 = ⟨𝐗, 𝐃, 𝐒, 𝐅, 𝐂⟩ with domain sizes of each variable bounded by 𝑘
• primal graph 𝐺 of 𝒢
• guiding pseudo tree 𝑇 of 𝐺 whose height is 𝘩 and having 𝑙 leaves

memory-space complexity is:

• memory-space complexity = 𝑂(𝑛) # a solution of an AND/OR Search Tree is its subtree where each of the 𝑛 variables has been assigned a value

search-space-size/time complexity is:

• search-space-size/time complexity = 𝑂(𝑙·𝑘^𝘩) # start at bottom with 𝑙 leaves, it scales by a factor of 𝑘 each time we traverse up the pseudo tree 
• search-space-size/time complexity = 𝑂(𝑛·𝑘^𝘩) # number of leaves 𝑙 in 𝑇 is always less than total number of variables 𝑛
• search-space-size/time complexity = 𝑂((𝑏𝑘)^𝘩) # when 𝑏 bounds the branching degree of 𝑇 and 𝑛 bounds the number of nodes

using tree-decomposition as guiding pseudo tree:

a tree decomposition of a primal graph 𝐺 can be used as a guiding pseudo tree 𝑇

given:

• tree decomposition of treewidth 𝑤, then the height 𝘩 satisfies 𝘩 ≤ 𝑤·𝑙𝑜𝑔(𝑛)

search-space-size/time complexity is:

• search-space-size/time complexity = 𝑂(𝑛·𝑘^{𝑤·𝑙𝑜𝑔(𝑛)})

AND/OR Search Tree - Other Stuff

• AOT & AOG - Finding Good Pseudo Tree
• AOT & AOG - Solving Probabilistic Inference Queries
• AOT & AOG - Using Tree Decomposition as Guiding Pseudo Tree

AND/OR Search Tree - To AND/OR Search Graph

It is often the case that a search space that is a tree can become a graph if nodes that root identical search subspaces, or correspond to identical subproblems, are identified. Any two such nodes can be merged, yielding a graph and thus reducing the size of the search space

see: OR Search Graphs (AOG)