Consider the sequence of graphs in Figure S13.38 and the application of variable elimination to each in order to compute P(X). For each, regardless of the elimination ordering, the largest factor produced in finding will have a table with 2² entries, assuming that all variables are Boolean.

Now draw a sequence of graphs such that, if you used the best elimination ordering for each graph, the largest factor table produced in variable elimination would have a constant number of entries, but if you used the worst elimination ordering for each graph, the number of entries in the largest factor table would grow exponentially as you move down the sequence. Provide 

(i) The sequence of graphs, 

(ii) The sequence of queries for which variable elimination is done, 

(iii) The best ordering, 

(iv) The worst ordering.

Figure S13.38

Transcribed Image Text:

OxᏅᏅx, ᎤᏅᏅ•x