  We present a new algorithm for finding maximum a-posterior) (MAP) assignments
of values to belief networks. The belief network is compiled into a network
consisting only of nodes with boolean (i.e. only 0 or 1) conditional
probabilities. The MAP assignment is then found using a best-first search on
the resulting network. We argue that, as one would anticipate, the algorithm is
exponential for the general case, but only linear in the size of the network
for poly trees.
