Finding a single solution. We can easily modify the algorithm to find a single solution. The main difference is that the 0/1 𝑣 values of internal nodes are propagated using Boolean summation and product instead of regular operators. If there is a solution, the algorithm terminates as soon as the value of the root node is updated to 1. The solution sub tree can be generated by following the pointers of the latest solution subtree. This, of course, is a very naive way of computing a single consistent solution as would be discussed in the context of mixed networks in Section 6.6.
Finding posterior marginals. To find posterior marginal of the root variable, we only need to keep the computation at the root of the search graph and normalize the result. However, if we want to find the belief (i.e., posterior marginal) for each variable we would need to make a more significant adaptation of the search scheme.
Optimization tasks. General AND/OR algorithms for evaluating the value of a root node for any reasoning problem using tree or graph AND/OR search spaces are identical to the above algorithms when product is replaced by the appropriate combination operator (i.e., product or summation) and marginalization by summation is replaced by the appropriate marginalization operator. For optimization (e.g., mpe) all we need is to change line 30 of the algorithm from summation to maximization. Namely, we should have 𝑣(𝑝) ← 𝑚𝑎𝑥{𝑣(𝑝), 𝑣(𝑛)}. Clearly, this will yield a base-line scheme that can be advanced significantly using heuristic search ideas. To compute marginal map query we will use marginalization by sum of max based on the variable identity to which the marginalization operator is applied.
Depth-first vs Best-first searches This could be the right place to make a clear distinction between searching the AND/OR space depth-first of best-first for optimization tasks. Best-first cannot exploit dead-caches, but must cache all nodes in the explicated graph. For this reason DFS can have far better memory utilization even when both scheme search an AD/OR graph.
general and/or search 𝐴𝑂(𝑖)
Click here to expand...
as two extreme cases in a parameterized collection of algorithms that trade space for time via a controlling parameter 𝑖. We denote this class of algorithms as 𝐴𝑂(𝑖) where 𝑖 determines the size of contexts that the algorithm caches. Algorithm 𝐴𝑂(𝑖) records nodes whose context size is 𝑖 or smaller
for any intermediate 𝑖 we get an intermediate level of caching, which is space exponential in 𝑖 and whose execution time will increase as 𝑖 decreases
another algorithm
Click here to expand...
// returns: conditional plan or failure AND_OR_graph_search(Problem problem) { OR_search(problem.initial-state, [])}// returns: conditional plan or failureOR_search(State state, List path) { if (state is goal) return empty plan if (state is in path) return failure for (action in state.possibleActions) { List resulting-states = results(state, action) plan = AND_search(resulting-states, problem, [state|path]) if (plan != failure) return [action|plan] } return failure}// returns: conditional plan or failureAND_search(State states, List path) { for (state-i in states) { plan-i = OR_search(state-i, path) if (plan-i == failure) return failure } return [if state-1 then plan-1 elif state-2 then plan-2 ... else plan-n];}
-seach-space---tree---graph/and／or-search-spaces/and／or-search-space---algorithms/temp-ao-counting-and-belief-updating-algorithm-description.png)
-seach-space---tree---graph/and／or-search-spaces/and／or-search-space---algorithms/temp-ao-counting-and-belief-updating-algorithm.png)