**Abstract**
Traditional search algorithms work on problems that can be modeled in a tree-like shape, this is, solving a problem
corresponds to traversing the tree from the root to one of the leaves of the tree that represents a solution. Each
one of the edges can be seen as a transition between different states of the problem where each state depends on
the previous and the decision taken.
There’s a subset of these problems where we can identify subproblems which are independent from each other, in
other words, the solutions of one don’t depend on the other. Sometimes we can also identify equivalent subproblems
that can be solved interchangeably. Consequently, it’s interesting to have a graph than can model these relations
and, later, algorithms that exploit them to solve the given problems. The models that capture these independencies
are called AND/OR trees (or graphs depending on their connectivity) and yield solutions in the form of a sub-tree.
An example modeled with a common search tree (which corresponds to an OR tree) has inherently larger size than
an AND/OR tree since the later as it takes into account the subproblems’ independency. Intuitively we can think
that an OR tree solves subproblems in a chain-like manner while AND/OR trees branches them out yielding a tree
with a smaller height.
As it’ll be seen later, these graphs can be used to model inference problems (graphical models, in general) and
exact and approximated algorithms have been implemented used to obtain the answers compute the answers to
the most common queries. The modeling, solution and complexity of finding solutions to these problems are the
subject of study of the present work. Orderings of variables and pseudo-trees, the underlying structures needed to
construct the problem’s space, will be studied as well due to their impact in the complexity of said algorithms. The
new contributions of this work are the analysis of the trade-offs between the width and height of the pseudo-trees
and the implementation of AND/OR Beam Search and Anytime AND/OR Beam Search as an attempt to tackle
the weaknesses of some of the state-of-the-art algorithms.

**[pdf]**