Graphical Model Problem Example

each variable have domain {1, 2, 3}
each node should be assigned a value such that adjacent nodes have different values

OR Search Tree	AND/OR Search Tree

Solution

a solution in an:

OR Search Space is a consistent path from root to a leaf
AND/OR Search Space is a subtree that contains the root node and where all of the following is satisfied:
- for every OR node, it contains one of its child nodes
- for every AND node, it contains all its child nodes
- all its leaf nodes are consistent

OR Tree & AND/OR Tree Complexity

given:

graph 𝐺 that is a balanced binary tree:
- 𝘩 = 𝑙𝑜𝑔₂𝑛 = height of 𝐺
- 𝑏 = 2 = branching factor of 𝐺
- 𝑛 is the number of variables
- 𝑘 is the domain size

search-space-size/time complexity is:

OR Search Tree
- 𝑂(𝑘^𝑛)
AND/OR Search Tree
- 𝑂((𝑏𝑘)^𝘩)
- 𝑂((2𝑘)^𝘩) # branching factor 𝑏 = 2 because 𝐺 is a balanced binary tree
- 𝑂((2𝑘)^{𝑙𝑜𝑔₂𝑛}) # height 𝘩 = 𝑙𝑜𝑔₂𝑛 because 𝐺 is a balanced binary tree
- 𝑂(𝑛^{𝑙𝑜𝑔₂(2𝑘)})
- 𝑂(𝑛^{𝑙𝑜𝑔₂2 + 𝑙𝑜𝑔₂𝑘})
- 𝑂(𝑛^{1 + 𝑙𝑜𝑔₂𝑘})

Subpages